술어 논리(Predicate Logic)

술어(Predicate)

$P(x)$
• 단항 술어로서 속성을 나타낸다.

$P(x, y)$
• 이상 술어로서 관계를 나타낸다.

술어에서 명제로 변환

$P(x)$ 의미 : $x$는 $P$이다.

• $P(x)$는 변수를 갖는 명제
• 객체가 변수 $x$에 대치되면, 명제가 되어 참 또는 거짓 중 하나의 값을 갖는다.
• 도메인(domain) : $x$에 입력할 객체의 집합

한정사(Quantifier)

$∀$ 전칭 한정사 (Universal Quantifier)
• 모두를 나타낼 때 사용
• $∀x. P(x)$
• $D=${$s1, s2, s3$} 일 때, $∀x.P(x)$ 의미는 $P(s1)∧P(s2)∧P(s3)$이다.
• 하나라도 거짓이면 $∀x.P(x)$는 거짓

$∃$ 존재 한정사 (Existential Quantifier)
• 존재하다를 나타낼 때 사용
• $∃x. P(x)$
• $D=${$s1, s2, s3$} 일 때, $∃x.P(x)$ 의미는 $P(s1)∨P(s2)∨P(s3)$이다.
• 모두 거짓일 때, $∃x.P(x)$가 거짓

한정사 중첩

⩥ $x, y$의 도메인은 모든 실수라 가정.
• $∀x\ ∀y\ (x+y=y+x)$

• $∀x\ ∃y\ (x+y=0)$

• $∀x\ ∀y\ ∀z\ (x+(y+z))=((x+y)+z)$


한정사 순서에 관계없이 아래 두 표현은 동일하다.
• $∀x\ ∀y\ (x+y=y+x)$ (true)
• $∀y\ ∀x\ (x+y=y+x)$ (true)


한정사 순서에 따라 진리값이 서로 다른 경우도 존재
• $∀x\ ∃y\ (x+y=0)$ (true)
• $∃x\ ∀y\ (x+y=0)$ (false)

술어 논리식의 부정

드모르강의 법칙
• $¬∀x.P(x)≡∃x.¬P(x)$
• $¬∃x.P(x)≡∀x.¬P(x)$

술어 논리의 증명

술어 논리를 위한 자연 연역(natural deduction)의 네 규칙

• ∀ 제거 규칙 (Universal Instantiation)

$\frac{∀xP(x)}{∴\ P(c)}$ $(c$는 임의의 객체$)$

• ∀ 도입 규칙 (Universal Generalization)

$\frac{P(c)}{∴\ ∀x.P(x)}$ $(c$는 임의의 객체$)$

• ∃ 제거 규칙 (Existential Instantiation)

$\frac{∃xP(x)}{∴\ P(c)}$ $(c$는 특정 객체$)$

• ∃ 도입 규칙 (Existential Generalization)

$\frac{P(c)}{∴\ ∃x.P(x)}$ $(c$는 특정 객체$)$