[이산수학] 1.3 술어와 한정기호

술어는 글로 표현하기보다는 보여주겠습니다.

 

"x is greater than 3" 이라는 문장이 있으면, x는 변수이고, is greater than 3 은 술어 입니다.

 

P(x) = x is greater than 3 에서 P(x)는 명제 함수 입니다.

 

예를 들어 P(x) = x ＞ 3 일때, P(7) 와 P(2)의 진리값을 물으면,

 

P(7) 은 7 ＞ 3 이기때문에 참이고 P(2)은 2 ＞ 3 이기때문에 거짓입니다.

 

 

 

인제 전조건과 후조건입니다.

 

전조건은 어떤 프로그램을 수행하기  전에 입력 받아야 하는것이고, 후조건은 프로그램을 수행했을때 나와야하는 결과 입니다.

 

만약 프로그램이 x 와 y 를 바꾸는 프로그램이면 x 와 y 에 전조건으로 값을 입력받아야 합니다.

 

그리고 후조건은 x 와 y를 바꾼 값이겠지요. 허헣

 

 

 

한정기호 입니다.

 

한정은 술어가 원소들의 어떤 영역에서 참이 되는 범위를 표현한거입니다.

 

한정기호는 전칭한정과 존재한정으로 나누어지는데 한정이라는 개념의 이해가 힘들면 전칭한정과 존재한정을 아는것으로 이해에 도움이 될 수 있습니다.

 

전칭한정은 정의역에 속하는 모든 x에 대하여 P(x)다 라는 뜻인데요.

 

이 말의 뜻은 정의역에 속하는 모든 x를 P(x)에 넣었을때 항상 참이라는 뜻입니다.

 

P(x)의 전칭한정을 ∀xP(x) 라고 표기합니다.

 

영어로는 for all, for every 등등 으로 표현합니다.

 

전칭한정이 거짓이 되려면 P(x)가 거짓이 되는 x 가 정의역에 있으면 됩니다.

 

존재한정은 정의역에 속하는 적하도 하나의 값 x에 대하여 P(x)다 라는 뜻입니다.

 

풀어서 말하면 P(x)가 참이 되도록 하는 x가 정의역에 하나라도 있으면 된다는 겁니다.

 

P(x)의 존재한정을 ∃xP(x) 라고 표기합니다.

 

영어로는 There is an x such that, There is at least one x such that P(x), For some x P(x) 등등으로 표현합니다.

 

한정기호는 모든 논리연산자보다 더 높은 우선순위를 가져서 항상 먼저 따져야됩니다.

 

한정기호도 논리적 동치가 될 수 있습니다.

 

예를 들어서, ∀x(P(x)∧Q(x)) 와 ∀xP(x)∧∀Q(x) 가 논리적 동치를 보여라.

 

이말이 맞다면 전칭한정이 분배적임을 뜻하겠죠.

 

그리고 이걸 증명하려면 '∀x(P(x)∧Q(x))가 참이면, ∀xP(x)∧∀Q(x)가 참이다' 와 '∀xP(x)∧∀Q(x)가 참이면 ∀x(P(x)∧Q(x))' 를 설명하면 됩니다.

 

만약 ∀x(P(x)∧Q(x))가 참이라 가정한다. a가 정의역에 속하면 P(a)∧Q(a) 가 참이고 다시 P(a)와 Q(a) 가 참이 됩니다. 

 

a를 정의역에 속하는 임의의 값이라 했기때문에 a에 뭐가 오든간에 위에서 한말은 참이 됩니다.

 

그러므로 정의역에 속하는 모든 원소에 대하여 P(a) 와 Q(a) 가 참이기 때문에 ∀xP(x)∧∀Q(x)는 참입니다.

 

그리고 ∀xP(x)∧∀Q(x)가 참이라고 가정한다.  그럼 ∀xP(x) 와 ∀Q(x) 가 참입니다.

 

그래서 위에 설명한것처럼 a 가 정의역에 속하면 P(a) 와 Q(a)도 참입니다.

 

P(a)와 Q(a)가 참이므로 P(x)∧Q(x)도 참입니다. 그러므로 ∀x(P(x)∧Q(x)) 도 참이 됩니다.

 

설명이 좀 어려운데 그럴수 밖에 없는거 같아요.. 저도 이해 안갔는데 계속 싸매고 하다보니까 이해가 되네요.

 

 

 

마지막으로, 한정 표현의 부정입니다.

 

이거 좀 햇갈릴 수도 있어요.

 

1. ￢∃xQ(x) ≡ ∀￢xQ(x)

2. ￢∀xP(x) ≡ ∃￢xP(x)

 

이렇게 동치입니다.

 

1번은 정의역에 있는 모든 x에 대하여 Q(x)가 거짓일때 참입니다. 그리고 만약 참이되는 x가 하나라도 있으면 거짓입니다.

 

2번은 정의역에 있는 x 중 P(x)가 거짓이 되도록하는 x가 있으면 참입니다. 그리고 만약 모든 x에 대하여 P(x)가 참일때 거짓입니다.

 

 

 

끝