Chapter 1.3 술어와 한정기호

술어(Predicate), 명제 함수(Propositional Function)

---

• Q(x, y) = "x = y + 3"

• R(x, y, z) = "x + y = z"

• 일반적으로 n개의 변수 $x_1, x_2, x_3, ⋯, x_n$을 포함하는 명제 함수는

  $P(x_1, x_2, x_3, ⋯, x_n)$

  으로 표기한다.

• $P(x_1, x_2, x_3, ⋯, x_n)$ 형태의 문장은 명제함수 P의 n-튜플$(x_1, x_2, x_3, ⋯, x_n)$에서의 값이며, P를 n-변수 술어(n-place predicate) 또는 n-항 술어(n-ary predicate)이라고도 한다.

  명제함수는 명제가 아니다. 명제함수에 변수의 어떤 값을 할당하는 순간 명제가 된다.

사실 명제함수(propositional function)와 술어(predicate)는 동일한 의미로 많이 사용된다.

- 예제 1

• R(x, y, z)가 “x + y = z” 를 나타내는 명제 함수라 하자
  • 그럼 R(1, 2, 3), R(0, 0, 1)의 진리 값은 무엇인가?
• sol) R(x, y, z) = “x + y = z”
  • R(1, 2, 3) = True
  • R(0, 0, 1) = False
  • R은 3-항 술어이다.

- 예제 2

• 다음 선언문을 생각해보자

  • if x > 0 then x := x + 1
    단, P(x)는 x>0 를 나타낸다고 하자

• 컴퓨터 프로그램에서는 어떻게 될까?

  • 변수 x의 값이 “ x > 0 ”을 나타내는 P(x)에 할당되고,

    • If P(x) is true,

      x := x + 1이 실행되어 x값 1증가

    • If P(x) is false,

      x := x + 1이 실행 안됨, x값 변경 안됨

한정 기호(Quantifiers)

---

• 명제 함수를 명제로 만드는 방법
  • 변수에 특정 값을 할당
  • 한정(quantification)을 적용

1. 변수에 특정 값을 할당하는 방법
   • P(x) = "x > 3"
   • 만일 x = 4라면 P(x)는 true가 되고, x = 2라면 P(x)는 false가 된다.
2. 한정(Quantification)을 적용하는 방법
   • P(x) = "x > 3"
   • x의 정의역(domain)이 "4 이상인 모든 실수"라면, P(x)는 true가 된다.

변수 x가 취할수 있는 값의 집합을 정의역(domain) 이라고 한다.

- 전칭 한정 ∀

• 정의 1 : 전칭한정

  • P(x)의 Universal Quantification 이란?
    • “정의역(domain)에 속하는 x의 모든 값에 대하여 P(x)이다.”라는 명제임
  • 전칭한정 기호(Universal Quantifier ∀)의 표기 및 읽기
    • 표기: ∀xP(x)
    • 읽기: "for all x P(x)" 혹은 "for every x P(x)"

• 전칭 한정 ∀의 개념적 이해

  • 정의역의 모든 값을 $x_1, x_2, x_3, ⋯, x_n$으로 나열할 수 있다면, ∀xP(x)는 다음과 동일 $P(x_1)∧P(x_2)∧⋯∧P(x_n)$

• 전칭 한정 ∀의 사용 예제

  • 예 1: P(x)가 $x < 2$이고 domain이 모든 실수라 할 때, ∀xP(x)의 진리 값은?
    • False
  • 예 2: Q(x)가 $0 ≤ x^2$이고 domain이 모든 실수라 할 때, ∀xQ(x)의 진리 값은?
    • True

• 반례(counterexample)

  • P(x)가 명제 함수라 할 때, ∀xP(x)가 거짓임을 보이기 위해서는 정의역에 속하는 값 중 단지 하나의 값이라도 P(x)를 거짓으로 만드는 예를 보이면 된다.

  • 이와 같이 P(x)를 거짓으로 만드는 예를 반례(counterexample)이라 한다.

  • 사용 예)

    • P(x)가 $x^2 > 0$이고 정의역이 모든 실수라 할 때, ∀xP(x)의 반례는?
      • x = 0이면 $x^2 =0$이 되어, $x^2 > 0$를 만족하지 않음
      • 따라서, ∀xP(x)가 거짓이 되고, 이때 x = 0을 반례라 한다.

- 존재 한정 ∃

• 정의 2 : 존재 한정
  • P(x)의 Existential Quantification 이란?
    • “정의역(domain)에 속하는 적어도 하나의 값에 x에 대하여 P(x)이다.”라는 명제임
  • 존재한정 기호(Existential Quantifier ∃)의 표기 및 읽기
    • 표기: ∃xP(X)
    • 읽기: "for some x P(x)" 혹은 "at least one x such that P(x)"

"어떠어떠한 x가 존재한다" 라고 생각하면 받아들이기 쉽다.

• 존재 한정 ∃의 개념적 이해

  • 정의역의 모든 값을 $x_1, x_2, x_3, ⋯, x_n$으로 나열할 수 있다면, ∃xP(x)는 다음과 동일

    $P(x_1)∨P(x_2)∨⋯∨P(x_n)$

• 존재 한정 ∃의 사용 예제

  • 예 1: P(x)가 “x >3”이고 정의역이 모든 실수라 할 때, ∃xP(x)의 진리 값은?

    • True

  • 예 2: Q(x)가 “x = x+1”이고 정의역이 모든 실수라 할 때, ∃xQ(x)의 진리 값은?

    • False

  • 예 3: P(x)가 $x^2 < 10$라고 하는 명제함수이고, 정의역은 “4를 초과하지 않는 양의 정수”라고 할 때 ∃xP(x)의 진리 값은?

    • Sol) $P(1)∨P(2)∨P(3)∨P(4)$

      정의역 중 명제함수 $P(x_n)$가 하나만 참이어도 ∃xP(x)가 참이다.

      P(1)은 $1^2 < 10$로서 True이다 → 따라서 ∃xP(x) is True

  • 예 4: P(x)가 $x^2 > 10$라고 하는 명제함수이고, 정의역은 “4를 초과하지 않는 양의 정수”라고 할 때 ∃xP(x)의 진리 값은?

    • Sol) $P(1)∨P(2)∨P(3)∨P(4)$

      정의역 중 명제함수 $P(x_n)$가 하나만 참이어도 ∃xP(x)가 참이다.

      P(4)은 $4^2 > 10$로서 True이다 → 따라서 ∃xP(x) is True

- 한정기호 개념 요약

선언문	언제 참인가?	언제 거짓인가?
∀xP(x)	P(x)가 모든 x에 대해 참일 때	P(x)가 거짓인 x가 존재할 때
∃xP(x)	P(x)가 참인 x가 존재할 때	P(x)가 모든 x에 대해 거짓일 때

• 유일한정기호(The Uniqueness Quantifier $∃!$ or $∃_1$)
  • 예) P(x)가 “x-1=0”인 명제함수 일때
  • ∃!xP(x) 는 다음을 의미함
    - P(x)가 참인 유일한 x가 존재한다.
    
    

구속변수(Binding Variables)

• 구속변수(Binding Variables) vs. 자유변수(Free Variables)
  • 구속 변수: 변수 x에 한정기호가 적용되거나 특정 값이 할당되는 경우
  • 자유 변수: 변수 x에 한정기호가 적용되지 않거나 특정 값이 할당되지 않는 경우
  • 한정기호의 범위(scope): 한정기호가 적용되는 부분

한정사 부정 표현

• 한정사 부정 표현(Negating Quantified Expressions) 예제

  • x = 학생, P(x) = "ㄱ반의 x는 미적분학 강의를 수강했다."

  • ∀xP(x) = "ㄱ반의 모든 학생은 미적분학 강의를 수강했다."

  • ¬∀xP(x)

    ⇔ "ㄱ반의 모든 학생은 미적분학 강의를 수강했다는 것은 사실이 아니다."

    ⇔ "ㄱ반에 미적분학을 수강하지 않은 학생이 존재한다."

    ⇔ ∃x¬P(x)

    즉, ¬∀xP(x) ≡ ∃x¬P(x)

• 한정사 부정 관련 법칙

  • ¬∀xP(x) ⇔ ∃x¬P(x)
  • ¬∃xP(x) ⇔ ∀x¬P(x)

• 예제)

  • $∀x(x^2 > x)$의 부정

    ⇔ $¬∀x(x^2 > x)$

    ⇔ $∃x¬(x^2 > x)$

    ⇔ $∃x(x^2 ≤ x)$

  • $∃x(x^2 = 2)$의 부정

    ⇔ $¬∃x(x^2 = 2)$

    ⇔ $∀x¬(x^2 = 2)$

    ⇔ $∀x(x^2 ≠ 2)$

응용: 시스템 명세에 한정기호 사용하기

• 다음 시스템 명세를 술어와 한정기호를 사용하여 표현하시오.

  • "1MB보다 큰 모든 메일 메시지는 압축될 것이다."

    • sol)

      명제함수 S(m, y)를 "메일 메시지 m은 y MB 보다 크다" 라고 두고

      명제함수 C(m)을 "메일 메시지 m은 압축될 것이다."라고 두자.

      그럼 위의 시스템 명세 "1MB보다 큰 모든 메일 메시지는 압축될 것이다."는 ∀m(S(m,1)→C(m))으로 표현될 수 있다.

  • "만약 한명의 유저가 접속한다면, 적어도 하나의 네트워크 링크가 이용가능할 것이다."

    • sol)

      명제함수 A(u)를 "만약 한명의 u가 접속한다면," 으로 두고

      명제함수 S(n, x)를 "네트워크 링크 n이 x 상태에 있다."라고 두자.

      그럼 위의 시스템 명세 "만약 한명의 유저가 접속한다면, 적어도 하나의 네트워크 링크가 이용가능할 것이다."는 ∃uA(u)→∃nS(n, available)으로 표현될 수 있다.

시스템 명세(System specification)가 일관되다(consistent)라는 말은 그 시스템 명세가 참이라는 뜻이다.