기호논리학 8. 술어 논리

술어 논리의 뜻

ex) 이브는 아담을 사랑한다.

따라서 어떤 사람은 아담을 사랑한다.

 

위의 두 문장을 보면 타당하다는 것을 알 수 있습니다. 하지만 문장 논리를 이용해서는 증명할 수 없습니다. 그래서 나온 것이 술어 논리입니다.

간단히 말하면 문장 논리는 문장을 사용하여 타당성을 증명하였지만, 술어 논리에서는 문장안의 내용을 분리하여 표기합니다.

 

일항 술어 (one-place predicate)

ex) 플라톤은 철학자이다.

소크라테스는 철학자이다.

위의 예시에서 앞의 이름을 제거하면 "_____는 철학자이다" 를 얻을 수 있습니다. 이와 같이 일종의 문장 함수(sentential function)으로 간주하여, 공란을 문자로 대체합니다.

 

x는 철학자이다.

 

이 상태에서 술어를 알파벳 대문자로 기호화 하고, 공란, 즉 이름을 소문자로 표기합니다.

 

s: 소크라테스

Px: x는 철학자이다.

Ps: 소크라테스는 철학자이다.

 

이항 술어

ex) 아담은 이브를 사랑한다.

이 문장에서 이름을 제거하면 "____는____를 사랑한다" 를 얻을 수 있습니다. 공란을 문자로 대체하면 "x는 y를 사랑한다" 로 나타낼 수 있고, 일항 술어때와 같이 술어는 대문자로, 공란을 소문자로 나타내면

 

a: 아담

b: 이브

Lxy: x는 y를 사랑한다.

Lab:아담은 이브를 사랑한다.

 

이와 같이 나타낼 수 있습니다.

삼항 술어

ex) 길수는 미애와 동현이 사이에 있다.

위에 했던 방식과 같이 :x는 y와 z사이에 있다. 로 대체한 후에 문자로 표기합니다.

 

Lxyz: x는 y와 z 사이에 있다.

 

양화사(Quantifier)와 변항(Variables)

1) 논의 영역(the universe of discourse)

논의 영역이란 변항 x가 취할 수 있는 모든 가능한 대상들의 집합.

 

2) 양화사(Quantifier)

양화사는 논의 영역 내에서 정의되어 진다.

모든 x에 대하여(For all x)=∀x

어떤 x에 대하여(For some x)=∃x

 

3) 양화사의 적용

Px가 모든 대상들에 대하여 참이다=(∀x)Px

Px가 만족하는 적어도 하나의 대상이 존재한다=(∃x)Px

(∀x)(Bx&Kx)=모든 x가 Bx와 Kx를 동시에 만족한다.

(∃x)(Bx→Kx)=어떤 x에 대하여 Bx이면 Kx이다. (Bx이면 Kx인 x가 적어도 하나 존재한다.)

 

술어 논리의 구문론(Syntax of Predicate Logic)

1) 기본 기호

이름: a,b,c,....

변항: x,y,z,...

술어: 1항 술어: Bx, Tx...

2항 술어: Lxy,....

3항 술어:Gxyz,...

논리적 연결사:∨, ↔, ←, →, &, ~

양화사:∃, ∀

괄호: ), (

 

2) 항

모든 이름들과 변항들은 항이다.

 

3) 단순 적형식(atomic well-formed formulas)

'F'가 n항 술어이고, 't1', 't2', 't3',...,'tn' 이 항들이라면, 'Ft1, t2,...,tn'은 단순 적형식이다.

ex) Ba, Lae, Tabc...

 

4) 적형식(well-formed formulas)

(1) 모든 단순 적형식들은 적형식이다.

(2) 'A'가 적형식이면 '(~A)'도 적형식이다.

(3) 'A'와 'B'가 적형식이면, '(A&B)'도 적형식이다.

(4) 'A'와 'B'가 적형식이면, '(A∨B)'도 적형식이다.

(5) 'A'와 'B'가 적형식이면, '(A→B)'도 적형식이다.

(6) 'A'와 'B'가 적형식이면, '(A↔B)'도 적형식이다.

(7) 'A'가 적형식이고 'x'가 변항이면, '(∀x)A' 도 적형식이다.

(8) 'A'가 적형식이고 'x'가 변항이면, '(∃x)A' 도 적형식이다.

 

5) 자유 변항(free variable)과 구속 변항(bound variable)

변항 'x'의 한 사례가 양화사의 적용 범위 내에서 발생하면, 그 'x'의 사례는 구속되어 있다고 말한다. 'x'의 한 사례가 구속되어 있지 않으면, 그 'x'의 사례는 자유롭다고 말한다.

간단히 말해서, 양화사가 붙은 문장일 때, 양화사 뒤에 붙은 변항이 구속 변항이고, 아니면 자유 변항이다.

 

ex) (∃x)Lxy

x 가 구속 변항이고 y가 자유 변항이다.

 

6) 문장

적형식 중에 자유 변항을 포함하지 않는 것들을 문장이라 한다.

따라서, 아예 양화사가 없거나, 양화사가 있으면 모든 변항에 대해 양화사가 붙어 있어야 한다.

ex) Bx =문장

(∀x)Lxy = 문장 아님(자유 변항 존재)

(∃x)Tx =문장

 

집합

간단히 말하면, 집합(set)은 대상들을 모아놓은 것이다.

집합에 대한 내용은 수학에서 배운 집합과 똑같으니 넘어가도록 하겠다.

 

순서쌍

'x는 y의 동생이다' 라는 관계를 생각해보자. 우리는 이 관계를 단순한 집합으로는 표현할 수 없다.

예를 들어 태종은 정종의 동생이지만, 정종은 태종의 동생이 아니다. 그런데 다음 두 집합은 동일한 집합이다.

 

{태종, 정종}={정종, 태종}

 

우리는 이를 해결하기 위해 순서쌍(ordered pair)를 도입할 것이다. 그리고 이것을 표현하기 위해 '< >' 기호를 도입할 것이다. <태종, 정종> 은 태종과 정종으로 이루어진 순서쌍인데, 순서쌍에서는 순서가 중요하다.

 

<태종, 정종>≠<정종, 태종>

 

따라서 우리는 순서쌍의 원리를 다음과 같이 표현할 수 있다.

 

(<x1, x2,......,xn>=<y1,y2,......,yn>)↔(x1=y1&x2=y2&......&xn=yn)

 

해석(Interpretation)

1) 해석함수 I

해석함수 I(x) 말 그대로 x를 해석한 것이다. 변항일땐 문자가 지칭하는 대상, 술어일 땐 술어를 참으로 만드는 집합을 표현한다.

ex) a: 이브

b: 아담

Lx: x는 금발이다.

Axy: x는 y의 아내이다.

La는 참이지만 Lb는 참이 아니다. Aab는 참이지만 Aba는 참이 아니다.

l(a)=이브, I(b)= 아담

I(L)={a}, I(A)={<a,b>}

 

2) 대체예(substitution instance)

양화사가 들어간 문장에서 양화사를 제거한 후에 자유 변항 'x'를 이름 's' 로 대체한 것.

ex) 논의 영역= {a, b, c, d, e}

(∀x)Px 혹은 (∃x)Px 에서 대체예를 구하면

Pa, Pb, Pc, Pd, Pe

 

따라서 다음과 같은 양화사를 포함한 조건들의 진리 조건을 정의할 수 있다.

'(∀x)Px' 는 M에서 참이다= df 'Px'의 모든 대체예들이 M에서 참이다.

'(∃x)Px' 는 M에서 참이다= df 'Px'의 대체예들 중에 적어도 하나는 M에서 참이다.

 

만약 M1={ a, e } 라 하면, M1에서의 보편 양화 문장들의 진리조건은 다음과 같이 표현될 수 있다.

(∀x)Px ↔ (Pa&Pe)

(∀x)Lxe↔(Lee&Lae)

(∃x)Px↔(Pa∨Pb)

(∃x)Lxe↔(Lae∨Lee)

 

만약 논의 영역이 유한할 경우, 보편 양화 문장은 유한한 연언 혹은 선언으로 표현 가능하다. 또한, 논의 영역이 무한할 경우에는 무한히 긴 연언 혹은 선언으로 표현될 수 있다.

 

술어 논리의 의미론과 타당성(Semantics and Validity in Predicate Logic)

모형세계 M에 상대적인 문장의 진리값은 다음과 같이 회귀적으로 정의된다.

(1) 단순 문장 'Ft1,...,tn'은 M에서 참이다.= df <I(t1),...,I(tn)>∈I(F)

(2) '~A'는 M에서 참이다= df 'A'는 M에서 참이 아니다.

(3) 'A&B'는 M에서 참이다.= df 'A'는 M에서 참이고 'B'도 M에서 참이다.

(4) 'A∨B'는 M에서 참이다.= df 'A'는 M에서 참이거나 'B'가 M에서 참이다.

(5) 'A→B'는 M에서 참이다.= df 'A'는 M에서 거짓이거나 또는 'B'가 M에서 참이다.

(6) 'A↔B'는 M에서 참이다.= df 'A'와 'B'는 M에서 동시에 참이거나 동시에 거짓이다.

(7) '(∀x)A(x)' 는 M에서 참이다.= df 'A(x)'의 모든 대체예들은 M에서 참이다.

(8) '(∃x)A(x)' 는 M에서 참이다.= df 'A(x)의 적어도 한 대체예가 M에서 참이다.

 

한 논증의 타당성을 증명하는 방법은 M을 임의의 모형세계라고 가정한 후에, 모든 전제들이 M에서 참이라고 가정하고, 결론 또한 M에서 참임을 보이는 것 이다. 만약 모든 전제들이 참이고 결론이 거짓인 모형세계 M이 있다면 그 논증은 부당하고 그러한 모형세계를 반례(counterexample)라고 한다.

 

[참고문헌] 논리적 추론과 증명(이병덕)