기호논리학 10. 술어 논리의 자연 연역

 

보편 양화사 제거 (∀ 제거)

1. (∀x)A(x)

2. A(t)

여기서 'A(t)'는 'A(x)'에 나타나는 모든 자유변항 'x'를 이름 't'로 대체함으로써 얻어진 대체예이다.

 

보편 양화문장의 대체예를 형성할 때, 대체되는 변항은 모든 곳에서 같은 이름으로 대체되어야 한다.

ex) (∀x)Lxx에서 x를 a로 대체한다면 Lxa나 Lax 가 아닌 Laa가 되어야 한다.

 

변항을 이름으로 대체할때 양화사를 제거하고 자유 변항이 되는 것만 대체해 주어야 한다.

ex) '(∀x)Ax→(∀x)Bx' 에서 첫번째 양화사를 제거하고 x를 e로 대체하면'Ae→(∀x)Bx'

두번째 x가 자유변항이 되지 않는다는 것에 주의하라.

 

존재 양화사 도입(∃ 도입)

1. A(t)

2. (∃x)A(x)

제한사항: 'A(t)' 에서 't'가 'x'에 의해 대체되었을 때, 'x'는 'A(x)' 에서 구속되어서는 안된다.

즉 'A(x)' 에서 'x'가 자유 변항이여야 한다.

ex) (∀x)Lax 에서 (∃x)(∀x)Lxx를 도출해 낼 순 없다.

 

보편 양화사 도입(∀ 도입)

임의의 이름 'u' 에 대하여 우리가 'A(u)' 를 증명한다면 'A(x)'의 모든 대체예가 성립하는 것을 의미한다. 이 경우 우리는 (∀x)A(x)를 추론할 수 있다.

제한사항: 'A(u)' 에서 'u'를 'x'로 대체했을 대, 'x'는 'A(x)' 에서 구속되어서는 안된다.

 

존재 양화사 제거(∃ 제거)

1. (∃x)A(x)

2. (∀x)(A(x)→C)

3. C

약식 존재 양화사 제거(∃ 제거)

1. (∃x)A(x)

2. A(d)

제한 사항: 여기서 'd'는 새로운 이름이여야 한다. 또한 약식 제거 규칙을 이용해 궁극적으로 도출해 내는 결론에 'd' 가 포함되어 있으면 안된다.

 

양화사와 관련된 몇 가지 사실

(1) 보편 양화사는 연언에 대해 분배되고, 또한 결합된다. 즉 아래의 규칙이 성립한다.

(∀x)(Px&Qx) // (∀x)Px&(∀x)Qx

(∀x)Px&(∀x)Qx // (∀x)(Px&Qx)

 

(2) 보편 양화사는 선언에 대해 결합되지만, 분배되지는 않는다.

(∀x)Px∨(∀x)Qx // (∀x)(Px∨Qx)

 

(3) 보편 양화사는 조건 기호에 대해서 분배되지만, 결합되지는 않는다.

(∀x)(Px→Qx) // (∀x)Px → (∀x)Qx

 

(4) 존재 양화사는 연언에 대해 분배되지만, 결합되지는 않는다.

(∃x)(Px&Qx) // (∃x)Px&(∃x)Qx

 

(5) 존재 양화사는 선언에 대해 분배되고 또한 결합된다.

(∃x)(Px∨Qx) // (∃x)Px∨(∃x)Qx

(∃x)Px∨(∃x)Qx // (∃x)(Px∨Qx)

 

(6) 존재 양화사는 조건 기호에 대해 결합되지만, 분배되지는 않는다.

(∃x)Px→(∃x)Qx // (∃x)(Px→Qx)

 

양화사와 관련된 두가지 파생 규칙

(1) 존재 양화사의 부정 규칙 (~∃)

~(∃x)Fx // (∀x)~Fx

 

(2) 보편 양화사의 부정 규칙 (~∀)

~(∀x)Fx // (∃x)~Fx

 

 

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