Chapter 1.3 술어와 한정기호

MoonLight·2021년 6월 13일
0

컴퓨터수학1

목록 보기
3/8
post-thumbnail
post-custom-banner


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


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

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

  • 일반적으로 n개의 변수 x1,x2,x3,,xnx_1, x_2, x_3, ⋯, x_n을 포함하는 명제 함수는

    P(x1,x2,x3,,xn)P(x_1, x_2, x_3, ⋯, x_n)

    으로 표기한다.

  • P(x1,x2,x3,,xn)P(x_1, x_2, x_3, ⋯, x_n) 형태의 문장은 명제함수 P의 n-튜플(x1,x2,x3,,xn)(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)"
  • 전칭 한정 ∀의 개념적 이해

    • 정의역의 모든 값을 x1,x2,x3,,xnx_1, x_2, x_3, ⋯, x_n으로 나열할 수 있다면, ∀xP(x)는 다음과 동일 P(x1)P(x2)P(xn)P(x_1)∧P(x_2)∧⋯∧P(x_n)
  • 전칭 한정 ∀의 사용 예제

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

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

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

    • 사용 예)

      • P(x)가 x2>0x^2 > 0이고 정의역이 모든 실수라 할 때, ∀xP(x)의 반례는?
        • x = 0이면 x2=0x^2 =0이 되어, x2>0x^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가 존재한다" 라고 생각하면 받아들이기 쉽다.

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

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

      P(x1)P(x2)P(xn)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)가 x2<10x^2 < 10라고 하는 명제함수이고, 정의역은 “4를 초과하지 않는 양의 정수”라고 할 때 ∃xP(x)의 진리 값은?

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

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

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

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

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

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

        P(4)은 42>104^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∃_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(x2>x)∀x(x^2 > x)의 부정

      ¬x(x2>x)¬∀x(x^2 > x)

      x¬(x2>x)∃x¬(x^2 > x)

      x(x2x)∃x(x^2 ≤ x)

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

      ¬x(x2=2)¬∃x(x^2 = 2)

      x¬(x2=2)∀x¬(x^2 = 2)

      x(x22)∀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)라는 말은 그 시스템 명세가 참이라는 뜻이다.

profile
hello world :)
post-custom-banner

0개의 댓글