[ 이산수학 ] 8. 술어 논리와 한정기호

명제함수(조건)와 술어

명제함수란 '조건'이라고도 하는데 명제 안에 포함된 변수의 값에 따라 참과 거짓이 달라지는 명제를 뜻한다. 

예를 들어, "n은 짝수이다." 라는 명제를 명제함수 P(n) 이라고 할 수 있는 것이다.

 

술어란 주어에 대한 서술을 의미한다.

예를 들어, "x는 10보다 크다.( =x is greater than 10)" 이라는 명제함수 q(x)가 있다고 하자. 이 명제함수에서 "~는 10보다 크.(= is greater than 10)" 라는 문장이 술어가 되는 것이다.

이러한 술어에 대해서 '한정기호'라는 것을 사용하여 나타낸 것을 '술어 논리'라고 한다.

 

술어 논리(함수 논리 또는 양화 논리)

주어와 술어의 구조로부터 주어가 될 수 있는 대상에 대해 한정기호를 사용하는 논리를 말한다.

 

※술어 한정 기호

1) 전칭 한정기호(universal quantifier) : ∀ = for all = for every ~ = 모든 ~ (것)에 대하여

ex) ∀xP(x) : 모든 x에 대하여 P(x)이다. = ("for all x, P(x)")

(여기서 P(x)가 거짓이 되는 원소를 ∀xP(x)의 반례라고 부른다.)

 

2) 존재 한정기호(existential quantifier) : ∃ = there exist. = for some = for at least one = there is = …

ex) ∃xP(x) : 어떤 x에 대하여 P(x)이다. (for some x, P(x))

 = 최소 하나의 x에 대하여 P(x)이다. (for at least one x, P(x)) 

= P(x)가 성립하는 x가 존재한다. (There is an x such that P(x))

 

3) 유일 한정기호 : ∃ ! 또는 ∃₁ = there exists a nunique = there is exactly one = there is one and only one = …

존재 한정기호와 비슷하지만 유일하다는 의미를 지닌다. 

 

※ 한정기호가 붙은 항변수를 속박변수라고 부르고, 그 밖의 항변수를 자유변수라고 부른다.

 

※ 한정기호의 우선순위

- 한정 기호는 명제 논리와 어떠한 논리 연산자보다 최우선의 우선순위를 가진다.

 

※ 한정기호와 분배적인 논리 동치

전칭한정은 논리곱에 대하여 분배적이며, 존재한정은 논리합에 대하여 분배적이다.

반대로 전칭한정은 논리합에 대하여 분배적이지 않으며, 존재한정은 논리곱에 대하여 분배적이지 않다.