[이산수학] 술어 논리 (predicate logic)

술어 (Predicate)

• 명제에 관한 논제들은 참과 거짓이 명확히 결정되었습니다. 그러나 앞으로 볼 명제들은 변수의 값에 따라서 참이 될 수도 있고 거짓이 될 수도 있습니다.

술어 (Predicate): 특정 값이 변수에 따라 대체될 때 명제가 되는 유한한 숫자의 변수를 포함하는 문장. 술어 변수의 정의역(domain)은 변수로 대체될 수 있는 모든 값의 집합이다.

• $x^2 + 5x + 6 = 0$이라는 명제는 $x$의 값이 -2 또는 -3일 경우에는 참의 값을 가지고 그렇지 않으면 거짓의 값을 가집니다. 이런 경우 ‘식을 만족시키는 변수가 있다’고 합니다.
• 이와 같은 형태의 명제를 $p(x)$로 표시하고 $p(x)$를 변수 $x$에 대한 명제 술어(propositional predicate)라 합니다.
• 명제 논리와 구분하여 명제 술어에 대한 논리를 술어 논리(predicate logic)라 합니다.

 

진리 집합 (Truth Set)

만약 $P(x)$가 술어이고 $x$가 $D$의 정의역(domain)을 가지고 있으면, $P(x)$의 진리 집합(Truth Set)은 $x$를 $p(x)$로 치환할 때 참으로 만드는 $D$의 모든 원소의 집합이다.

 

술어 한정자 (Predicate Quantifier)

술어 한정자 (Predicate Quantifier): 술어를 나타내는 방법 중 변수의 범위를 한정시키는 것.

• 술어 한정자에는 ‘모든 것에 대하여 (for All, $\forall$)’ 와 ‘존재한다 (there Exists, $\exists$ )’ 의 두 가지가 있습니다.

 

전체 한정자 (Universal Quantifier)

전체 한정자 (Universal Quantifier), $\forall$
'모든 $x$에 대하여 $p(x)$는 참이다.’

• $p(x)$에 대한 전체 한정자는 $\forall$$x\ p(x)$로 나타냅니다.
• $\forall$$x\ p(x)$가 참이 되기 위한 필요충분조건(iff; if and only if)은 술어 $p(x)$가 $x$의 전체 집합 $U$에 대하여 성립해야 합니다.
• 거짓임을 증명하기 위해서 적어도 하나의 반례(counterexample)를 찾아내면 됩니다.

 

존재 한정자 (Existential Quantifier)

존재 한정자 (Existential Quantifier), $\exists$
’어떤 $x$에 대하여 $p(x)$가 참인 $x$가 존재한다.’

• $p(x)$에 대한 존재 한정자는 $\exists$$x\ p(x)$로 나타냅니다.
• $\exists$$x\ p(x)$가 참이 되기 위한 필요충분조건(iff; if and only if, $\iff$)은 전체 집합 $U$ 안에 $p(x)$를 만족시키는 $x$가 적어도 한 개 존재해야 합니다.
• ‘모든 $x$에 대하여 $p(x)$가 성립한다.’의 부정: ‘$p(x)$가 성립하지 않는 $x$가 존재한다.’ → 논리 기호로 나타내면: $\sim(\forall x \ p(x)) \iff \exists x(\sim p(x))$