제목없음

술어 논리

1. 술어와 한정기호

이제까지 우리는 명제를 기초로 한 논리를 이용하여 사실의 기술이나 추론을 행하였다. 명제는 "우리 나라의 역사는 깊다."등과 같은 문장을 기호화한 것으로, 기본적으로 그 자체를 분석하는 것은 불가능하다. 합성명제인 경우 각 명제 간을 연결하는 연결사를 이용한 분석만이 가능할 뿐이다. 예를 들면, 다음과 같은 명제가 있다고 하자.

모든 꽃은 아름답다.

국화는 꽃이다.

그러므로 국화는 아름답다.

이 추론은 직관이나 상식에 의하면 타당하지만, 만일 기호화하여 보면

∴P

과 같이 되어 우리가 이제까지 배운 바에 의하면 타당한 추론이라고 할 수 없다.

사실 이추론은 타당하며, 이 경우에 타당성은 명제논리에서와 같이 추론의 형색에 의존하는 것이 아니라. 각 명제의 내용 혹은 그 구성요소 간의 관계에 따른다. 즉, 일반적으로 단순한 서술문인 경우 주어와 술어로 구성된다. 이 때, 술어(predicate)는 어떤 속성을 나타내며, 그 속성의 주체는 주어로서 주어진다. 술어논리(predicate logic)이란, 이와 같이 명제의 술어에 대한 분석에 기초하고 있다. 위의 예에서 "국화"는 주어로서 x(소문자)로 표현하고 "꽃이다."는 술어로서 P(대문자)로 표현하면, "국화는 꽃이다." 라는 문장은 P(x)의 형태로 표기될 수 있다.

S를 술어 "걸을 수 있다."라고 할 때, S(x) 는 "x는 걸을 수 있다"를 의미한다.

여기서 x는 일종의 변수로서 S(x) 자체는 명제가 아니지만, s를 적절한 대상의 이름으로 치환하면 결과적으로 명제가 된다. 예를 들면, a가 타조라고 하면 S(a) 는 명제이다. 따라서 S(x)는 명제함수로서 술어기호화 변수로서 구성되는 식이라 할 수 있다. 명제논리에서와 마찬가지로 명제함수는 기본명제함수와 합성명제함수로 나뉘어지며, 후자는 전자를 연결사에 의해 연결한 명제함수이다.

예)

B(x) : x는 자연수이다.

C(x) : x는 정수이다.

B(x) → C(x) : B(x) 이면 C(x)이다.

D(x, y) : x는 y를 포함한다. (2자리 술어)

E(X1, X2, ... , Xn) : X1 < X2< ... <Xn(n자리 술어)

한편 앞에서 예시한 "모든 꽃은 아름답디"를 기호화하는 데 있어 "모든"이라는 단어에 대한 기호를 만들 필요가 있다. 또 "포유동물 중에 육지에 살지 않는 것이 몇몇 존재한다."라는 명제는" 포유동물에 대하여 육지에 살지 않는 것이 적어도 하나 존재한다" 라고 다시 기술 할 수 있다. 이 경우 "몇몇"이나 혹은 "적어도 하나 존재한다."라는 의미를 갖는 기호가 필요하다. 일반적으로 서술문에서 양(量)을 나타내는 단어를 한정기호(限定記號, quantifier) 라고 하며, 다음과 같이 정의된다.

정의) x를 변수라 할 때 한정기호는 다음과 같다.

전칭기호(全稱記號) ∀x : 모든 x에 대하여, 영문으로 for all x.

존재기호(存在記號) ∃x : 어떤 x에 대하여 ... 인 x 가 적어도 하나 존재한다. 영문으로는 for some x, there exist at least ome x such that ...

예) 위의 예에서 보인 명제함수를 이용하면

∀x(B(x) → C(x)) 모든 x에 대하여 x가 자연수이면 x는 정수이다.

∃x(B(x) ∧ C(x)) 어떤 x에 대하여 자연수이면서 정수인 x가 적어도 하나 존재한다.

위의 예에서 ∀x와 ∃x다음에 위치하는 괄호 안의 술어가 이들 한정기호의 범위에 속한다는 것을 의미한다. 이 경우, B(x) 나 C(x)의 x는 ∀x나 ∃x에 의해 한정되므로 속박변수(bound variable)라 하고, 그렇지 않은 경우를 자유변수(free variable)라 부른다.

2. 술어계산

술어논리의 명제함수에서 각 변수들이 가질 수 있는 값(혹은 대상)의 집합을 논의영역(universe of discourse) 혹은 대상영역이라 부른다. 엄밀하게 말하면, 모든 명제함수는 논의영역을 명시하여야 하지만, 묵시적으로 남겨 두는 경우가 흔하다.

만일 동물이 논의의 대상이라면 논의영역은 동물이고, "x는 회사에 근무한다" 라는 명제에서 논의영역은 묵시적으로 사람을 나타낸다고 할 수 있다.

예) 다음의 술어를 이용하여 "x는 y의 어머니의 아버지이다" 라는 술어를 명시하여라.

H(x) : x는 사람이다.

F(x, y) : x는 y의 아버지이다.

M(x, y) : x는 y의 어머니이다.

주어진 문제는 "z는 y의 어머니이다", "x는 z의 아버지이다"와 같이 고쳐 쓰고, z라는 tfka의 존재를 가정하면 위의 술어를 다음과 같이 기호화할 수 있다.

∃z(H(z) ∧ F(x, z) ∧ M(z, y))

여기에서 z는 속박변수이며, x, y는 자유변수이다.

예) "모든 꽃은 아름답다"라는 명제를 기호화하기로 하자.

F(x) : x는 꽃이다.

P(x) : x는 아름답다.

주어진 명제는 이들 기호로부터 다음과 같이 기호화된다.

∀x(F(x) → P(x))

그렇지만 x의 논의영역을 꽃으로 한정한다면 위의 명제는 다음과 같이 기호화된다.

∀xP(x)

만일 주어진 명제 P(x)가 대상영역 내에서 어떤 값의 x에 대하여도 참이 아니라고 한다면 "~(∃xP(x))" 로 표기하고, "P(x)가 참이 되게 하는 x는 하나도 존재하지 않는다" 라고 말할 수 있다. 이와 같이 부정기호(∼)와 한정기호 (∀와∃)를 이용하여 다음의 여덟 가지의 술어계산을 행할 수 있다.

∀xP(x), ∃P(x) , ~(∀xP(x)), ~(∃xP(x)), ∀x(~P(x)),

∃x(~P(x)), ~(∀x(~P(x)), ~(∃x(~P(x))

예를 들면,∀x(~P(x))는 "모든 x에 대하여 P(x)는 거짓이다"를 의미하고 ~(∀xP(x))는 "모든 x에 대하여 P(x)가 참이라는 것은 거짓이다"를 의미한다.

이들 예에서 ~∃x(P(x))와 ∀x(~P(x))를 비교해 보자. 전자는 '하나도 참이 아님'을 후자는 '모두 거짓임'을 의미하므로 논리적으로 동일하다고 생각할 수 있다.

즉, ~∃x(P(x)) ⇔ ∀x(~P(x))이다 (예 참조). 마찬가지로 표 1 에서 보이는 바와 같이 다른 여섯 가지의 경우에 있어서도 논리적인 동치관계를 갖는 쌍을 구할 수 있다. 이것을 술어계산에서의 드 모르간 법칙이라고 한다.

예) ~∃x(P(x)) ⇔ ∀x(~P(x)) 의 관계를 논리적으로 증명하여라.

유한의 논의영역 U = {a1, a2, .. , an }에 대하여

∀x(P(x)) ⇔ P(a1) ∧ P(a2) ∧... ∧ P(an)

∃x(P(x)) ⇔ P(a1) ∨ P(a2) ∨... ∨ P(an)

따라서, 드 모르간 법칙을 원용하면

~∃x(P(x)) ⇔ P(a1) ∨ P(a2) ∨... ∨ P(an)

⇔ ~P(a1) ∧ ~P(a2) ∧... ∧ ~P(an)

⇔ ∀x(~P(x))

예) 다음 명제를 부정하여라. "모든 비행기는 사람보다 빠르다."

이 명제의 무정은 "모든 비행기는 사람보다 빠르지 않다." , 즉, "사람보다 빠르지 않은 비행기가 적어도 하나 존재한다."라고 놓을 수 있다. 따라서 논의영역 A를 모든 비행기의 집합이라고 하고, F(x)를 x가 사람보다 빠르다는 것을 의미한다고 할 때, 원래의 명제는 ∀x(F(x))가 된다. 이것의 부정 ~∀x(F(x))는 드 모르간 법칙에 의해 ∃x(~F(x))와 동치이다.

표) 술어논리에서의 드 모르간 법칙

1. 하나도 참이 아님 ~∃x(F(x)) ⇔ ∀x(~P(x))

2. 모두는 참이 아님 ~∀x(F(x)) ⇔ ∃x(~P(x))

3. 적어도 하나는 참임 ∃x(P(x)) ⇔ ~(∀x(~P(x)))

4. 모두 참임 ∀xP(x) ⇔ ~(∃x(~P(x)))

이제 한정기호를 사용하는 명제함수를 증명하는데 유용한 두 가지 방법을 소개하기로 한다.

(1) 존재증명 : ∃xF(x)의 형태를 갖는 명제가 참임을 증명할 때 ,논의영역에서 어떤 값 c에 대하여 F(c)가 참임을 보인다. 이 때, c를 얻을 수 있는 알고리즘을 명시할 수도 있고 F(c)가 참인 c를 제시할 수도 있다. 이러한 존재 증명 방법을 구성적이라고 부른다.

예) F(x)가 "x는 정수이며, x² = 100이다"일 때 ,제곱근을 구하는 알고리즘을 사용하여 증명한다.

한편, 비구성적인 존재증명에서는, F(c) 가 참이 되는 c를 찾는 대신에 다른 방법을 이용하여 ∃xF(x)가 참임을 보인다. 이 때, 흔히 사용되는 방법은 모순에 의한 증명이다. 즉, ~(∃xF(x))가 모순임을 보이면 된다.

예) 논의영역이 정수의 집합이고 F(x)가 "x는 소수이고, x는 n보다 크다 (즉, n보다 큰 소수가 존재한다.)"일 때, 비구성적인 방법으로 증명해보자. n이 양의 정수라 하고 값이 n! + 1 인 정수를 생각하여 본다. 모든 정수는 소수 인수를 가지므로 n! + 1을 나눌 수 있는 소수가 적어도 하나 존재한다(이 때, 자체가 이미 소수일 수 있음), n! + 1을 정수 m( m ?? n )으로 나누면 나머지는 1 이어서 m은 n! + 1 의 인수가 아니다. 따라서 n! + 1의 소수 인수는 n보다 크다. 여기서는 n보다 큰 소수를 제시하지 않았으므로 구성적인 증명이 아니다. 다만 그러한 수가 존재하여야만 한다는 것을 보였을 뿐이다.

(2) 반례(反例)에 의한 증명 : ∀xF(x)의 형태를 갖는 명제가 거짓임을 증명할 때, 논의영역에의 어떤 특정한 예 c에 대하여 F(c)가 거짓임을 보인다. 이 값 c를 명제함수 ∀xF(x)에 대한 반례라 한다.

예) "모든 양수 n에 대하여, n은 소수이다"라는 것은, 예를 들면 4가 2에 의해 나누어지므로 반례가 성립되어 주어진 명제함수는 거짓이 된다.

일반적으로 P(x, y)가 두 개의 변수 x, y를 갖는 술어라고 하면 전칭기호화 한정기호 두 가지를 이용하여 각 변수를 한정할 수 있다. 이 때, 두 기호의 순서를 고려하면 ∀x, ∀y , ∃x, ∃y에 대하여 모두 여덟 가지의 나열방법을 얻는다. 이들의 관계는 표 2 와 같다. 이 표에서 "⇔"는 논리적 동치를 "⇒"는 논리적 함의를 나타낸다.

표 2 술어계산에서의 논리적 관계

1.∀x∀y P(x, y) ⇔ ∀y∀x P(x, y)     5. ∃x∀y P(x, y) ⇔ ∀y∃x P(x, y)

2.∀x∀y P(x, y) ⇔ ∃y∀x P(x, y)     6. ∀x∃y P(x, y) ⇔ ∃y∃x P(x, y)

3.∀y∀x P(x, y) ⇔ ∃x∀y P(x, y)     7. ∀y∃x P(x, y) ⇔ ∃x∃y P(x, y)

4.∃y∀x P(x, y) ⇔ ∀x∃y P(x, y)     8. ∃y∃x P(x, y) ⇔ ∃x∃y P(x, y)

예) 논의영역이 실수인 다음의 두 명제를 비교분석해 보자.

(1) ∀x∃y[x + y = 10]

(2) ∃y∀x[x + y = 10]

(1)에서 임의의 x에 대하여 y = 10 -x를 선택하면 "x + y = 10"이 참이 되므로 ,∃y∀x[x + y = 10]는 참이다. 즉, ∃y∀x[x + y = 10]는 모든 x에 대하여 참이 되어 (1)은 참이다. (2)에서 y를 고정시키고 x = 5 - y를 선택하면 "x + y = 10"이 거짓이 되어 ∀x∃y[x + y = 10]는 참이 아니다. 즉, ∀x∃y[x + y = 10]는 어딴 y에 대하여 거짓이 되어 (2)는 거짓이다.

다음 예에서 (2)가 (1)을 논리적으로 함의함을 보기로 한다.

예) 1.30 ∃x∀y P(x, y) ⇒ ∀y∃xP(x, y)임을 보여라.

좌변의 진리값이 참이면 논의영역 안에 ∀yP(x0, y)가 참이 되도록 하는 하는 x0가 존재하여, P(x0, y)는 모든 y에 대하여 참이다. 이와같이 각 y에 대하여 동일 x0(단 하나의 값)으로 ∀yP(x, y)는 참이 된다.

한편, ∀yP(x0, y)모든 y에 대하여 참이므로 우변의 진리값도 참이 된다. 따라서 이 명제는 항진이다.

3. 술어논리의 추론 규칙

명제함수와 한정기호를 사용하는 술어논리에서는 명제논리와 다른 추론규칙을 추가로 정할 필요가 있다. 다음에서는 전칭기호와 존재기호를 첨삭하여 추론을 유도 할 수 있게 하는 네 가지의 규칙을 살펴보기로 한다.

(1) 전칭의 특정화(US) : 만일, ∀xP(x)형태의 명제가 참이라 하면, 전칭기호는 생략되어 논의영역 내의 임의의 대상 C에 대해 참임 P(c)를 얻을 수 있다.

∀xP(x)

∴ P(c)

예) 논의영역이 행성이고, P(x)는 '행성은 움직이고 있다'를 뜻할 때,

∀xP(x) (모든 행성은 움직이고 있다.)

∴ P(c)

(2) 전칭의 일반화(UG) : 명제 P(c)에 대하여 참이라면 전칭기호를 붙여를 얻는다.

P(c)

∴∀xP(x)

예) 논의영역이 신입생이고, P(x)는 'x는 교양과목을 수강한다'를 뜻할 때,

P(아무개)

∴∀xP(x)

(3) 존재의 특정화(ES) : ∃xP(x)형태의 명제가 참이라 하면, P(c) 가 참이되게 하는 논의영역 내의 한 요소 c가 존재한다.

∃xP(x)

∴ P(c)

여기서 유의하여야 할 점은 c는 전칭의 특정화에서와 같이 임의의 값이 아니라, 반드시 ∃xP(x)를 만족하는 요소이다. 예를 들면, 논의영역을 사람이라고 하고, F(x)를 'x는 여자이다', M(x)를 'x는 남자이다'라고 할 때, ∃xF(x)와 ∃xM(x)는 모두 참이다. 그러나 F(c) ∧ M(c) 는 논의영역 내의 c에 대하여 거짓이다 참이 되려면 논의영역 내의 요소 c와 d에 대해 F(c) ∧ M(d) 이어야 한다.

(4) 존재의 일반화(EG) : 만일 P(c)가 논의영역 내의 한 요소 c에 대하여 참이라 하면, 또한 참이다. 즉,

P(c)

∴∃xP(x)

예) 다음 추론을 증명하여 보아라.

∃xG(x) ∧ H(x)) → ∃G(x) ∧ ExH(x)

(1) ∃xG(x) ∧ H(x)) : 전체

(2) G(c) ∧ H(c) : ES

(3) G(c) : (2) 항의 단순화 (표 1.4 참조)

(4) H(c) : (2) 항의 단순화

(5) ∃xG(x) : (3) 항과 EC

(6) ∃xH(x) : (4) 항과 EC

(7) ∃G(x) ∧ ExH(x) : (5), (6) 항의 결합 (표 2 참조)

예) 1.34 다음의 추론을 기호화한 후 정확성 여부를 판정하여라.

사탕은 몸에 해롭다. │S(x) : x는 사람이다.

사탕이 있다. │H(x) : x는 몸에 해롭다.

그러므로 몸에 해로운 것이 있다. │

위의 추론을 기호화하면

∀xS(x) → H(x))

∃xS(x)

∴ ∃xH(x)

이 추론의 증명은 다음과 같다.

(1) ∃xS(x) : 전제

(2) S(a) : (1)항과 ES

(3) ∀xS(x) → H(x)) ; 전제

(4) S(a) → H(a) : (3)항과 US

(5) H(a) : (2), (4)항과 긍정식(표 1.4 참조)

(6) ∃H(x) : (5)항과 EG