Q(x, y) = "x = y + 3"
R(x, y, z) = "x + y = z"
일반적으로 n개의 변수 을 포함하는 명제 함수는
으로 표기한다.
형태의 문장은 명제함수 P의 n-튜플에서의 값이며, P를 n-변수 술어(n-place predicate) 또는 n-항 술어(n-ary predicate)이라고도 한다.
명제함수는 명제가 아니다. 명제함수에 변수의 어떤 값을 할당하는 순간 명제가 된다.
사실 명제함수(propositional function)와 술어(predicate)는 동일한 의미로 많이 사용된다.
다음 선언문을 생각해보자
컴퓨터 프로그램에서는 어떻게 될까?
변수 x의 값이 “ x > 0 ”을 나타내는 P(x)에 할당되고,
If P(x) is true,
x := x + 1이 실행되어 x값 1증가
If P(x) is false,
x := x + 1이 실행 안됨, x값 변경 안됨
변수 x가 취할수 있는 값의 집합을 정의역(domain) 이라고 한다.
정의 1 : 전칭한정
전칭 한정 ∀의 개념적 이해
전칭 한정 ∀의 사용 예제
반례(counterexample)
P(x)가 명제 함수라 할 때, ∀xP(x)가 거짓임을 보이기 위해서는 정의역에 속하는 값 중 단지 하나의 값이라도 P(x)를 거짓으로 만드는 예를 보이면 된다.
이와 같이 P(x)를 거짓으로 만드는 예를 반례(counterexample)이라 한다.
사용 예)
"어떠어떠한 x가 존재한다" 라고 생각하면 받아들이기 쉽다.
존재 한정 ∃의 개념적 이해
정의역의 모든 값을 으로 나열할 수 있다면, ∃xP(x)는 다음과 동일
존재 한정 ∃의 사용 예제
예 1: P(x)가 “x >3”이고 정의역이 모든 실수라 할 때, ∃xP(x)의 진리 값은?
예 2: Q(x)가 “x = x+1”이고 정의역이 모든 실수라 할 때, ∃xQ(x)의 진리 값은?
예 3: P(x)가 라고 하는 명제함수이고, 정의역은 “4를 초과하지 않는 양의 정수”라고 할 때 ∃xP(x)의 진리 값은?
Sol)
정의역 중 명제함수 가 하나만 참이어도 ∃xP(x)가 참이다.
P(1)은 로서 True이다 → 따라서 ∃xP(x) is True
예 4: P(x)가 라고 하는 명제함수이고, 정의역은 “4를 초과하지 않는 양의 정수”라고 할 때 ∃xP(x)의 진리 값은?
Sol)
정의역 중 명제함수 가 하나만 참이어도 ∃xP(x)가 참이다.
P(4)은 로서 True이다 → 따라서 ∃xP(x) is True
선언문 | 언제 참인가? | 언제 거짓인가? |
---|---|---|
∀xP(x) | P(x)가 모든 x에 대해 참일 때 | P(x)가 거짓인 x가 존재할 때 |
∃xP(x) | P(x)가 참인 x가 존재할 때 | P(x)가 모든 x에 대해 거짓일 때 |
한정사 부정 표현(Negating Quantified Expressions) 예제
x = 학생, P(x) = "ㄱ반의 x는 미적분학 강의를 수강했다."
∀xP(x) = "ㄱ반의 모든 학생은 미적분학 강의를 수강했다."
¬∀xP(x)
⇔ "ㄱ반의 모든 학생은 미적분학 강의를 수강했다는 것은 사실이 아니다."
⇔ "ㄱ반에 미적분학을 수강하지 않은 학생이 존재한다."
⇔ ∃x¬P(x)
즉, ¬∀xP(x) ≡ ∃x¬P(x)
한정사 부정 관련 법칙
예제)
의 부정
⇔
⇔
⇔
의 부정
⇔
⇔
⇔
다음 시스템 명세를 술어와 한정기호를 사용하여 표현하시오.
"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)라는 말은 그 시스템 명세가 참이라는 뜻이다.