0. 들어가기 전에
명제에 대한 연산자는 다음과 같이 쓴다
not p : !p
p and q : p&q
p or q : p|q
if p then q : p->q (!p|q와 동일)
p iff q : p<->q (p->q&q->p와 동일)
+ 밑에 나오는 용어들은 번역명을 모르거나, 개인 연구에 사용했거나, 잘못된 번역명을 사용하고 있을 수 있음.
+ 개인 연구에 사용하던 개념들이 종종 섞여있으니 몇몇 오류가 포함될 수 있음.
1. 논리적 귀결과 추론가능성
명제집합 A의 모든 원소가 참인 진리값을 가질 때 B또한 참이라면 B는 A의 논리적 귀결이라고 한다.
AㅑB 또는 (A의 모든 원소의 나열)ㅑB라고 쓴다. 이때 A를 전제, B를 결론이라 한다.
한편 추론가능성은 명제집합 A = {a1, a2, a3, ... , an}, 명제 B에 대해 다음 조건을 만족하는 명제의 나열 Q가 존재할 때 B는 A로부터 추론가능하다고 한다. AㅏB 또는 (A의 모든 원소의 나열)ㅏB라고 쓴다.
"모든 Q의 k번째 원소 qk는 적당한 규칙 X를 적용해 얻을 수 있다. 이 나열의 마지막 원소로 B가 존재한다."
이때 A를 조건, B를 정리라고 한다.
2. 추론규칙
ㄱ. P규칙
P규칙은 원 명제집합 A의 원소를 Q의 나열의 원소로 사용함을 의미한다.
ㄴ. T규칙
T규칙은 Q에서 몇 개를 취한 명제들의 논리적 귀결이 Z일때 Z를 Q의 나열의 원소로 사용함을 의미한다.
또는 T규칙으로 정의를 사용할 수 있다.
3. 논리적 귀결의 타당성 입증과 증명
논리적 귀결은 정의에서 조건이 모두 참임을 가지게 하기 위해 모든 경우의 수를 찾아야 한다.
예를 들어 {1,2,3} 위에서 명제 Px = "x는 자연수"임을 보이려면 모든 집합의 원소 1,2,3에 대해 "1는 자연수","2는 자연수", "3는 자연수"가 참인지 확인해야 한다. 즉, 전제가 모두 참인 모든 경우의 수에 대해서 참임을 보여야 한다.
하지만 추론가능성과 논리적 귀결이 동치임은 어떤 수학자가 증명해 뒀으니 그냥 사용하면 된다.
즉, 모든 조건이 참일 때 정리가 참임을 보인다면, 모든 전제를 만족했을 때 결론이 타당함은 당연하다는 것이다.
다른 말로 표현하자면 전제가 참일때 결론이 타당함을 보이기 위해 우리는 모든 경우에 대해 참임을 보이는 대신 추론가능성을 보이는 것으로 충분하다는 것이다.
이때 우리는 추론규칙에 따라 얻은 명제의 나열 Q로부터 정리 B를 얻었다면, Q를 정리 B에 대한 증명이라고 부른다.
4. 추가 추론 규칙
ㄱ. 가정법
Aㅏ(B->C)와 A,BㅏC는 동치이다.
Proof. B가 참이면, B->C는 C와 같다. 정의에 의해 A,BㅏC 또한 AㅏC와 같다. 따라서 동치이다.
B가 거짓이면, B->C는 A와 관계없이 참이고, A,BㅏC는 A,C와 관계없이 공허 참이다. 따라서 동치이다.
즉, 가정법은 Aㅏ(B->C)를 보이는 대신 A,BㅏC를 보이고, Aㅏ(B->C)는 참임을 이끌어 내는 추론 규칙이다.
ㄴ. 간접법
AㅏB가 참임은 A,!BㅏC&!C인 C가 존재함과 동치이다.
Proof. AㅏB가 참임은 A와 B가 모두 참이거나, A의 어떤 원소가 참이 아님을 의미한다.
C&!C는 거짓이므로 A의 모든 원소와 !B가 모두 참이라면 A,!BㅏC&!C는 거짓이다.
A,!BㅏC&!C가 참이 되려면 A의 어떤 원소 또는 !B가 거짓이어야 한다.
A의 어떤 원소가 거짓이라면 AㅏB는 공허참이다.
A의 모든 원소가 참이라면 !B가 거짓이고, B는 참에서 AㅏB는 참이다.
즉, 간접법은 AㅏB 대신 A,!B를 가정으로 항상 거짓인 명제 (어떤 명제와 그 부정이 동시에 참이 됨)을 유도해 A,!B가 동시에 참일 수 없다는 것을 이끌어내는 추론 규칙이다.
5. 추론 규칙의 실제
추론가능임을 보이기 위해 적당한 명제의 나열을 제시하는 것으로 충분하다.
P규칙과 T규칙은 명제의 나열로 작성할 수 있으나, 가정법과 간접법을 자연어를 배제한 명제의 나열로 나타내는 것은 다음과 같이 할 수 있다.
ㄱ. A규칙
간접법과 가정법은 모두 조건에 새로운 명제를 제시하여 주어진 문제의 추론가능성을 보이는 것과 같은 다른 명제를 추론하는 것으로 이루어 진다.
즉, 이때 새롭게 추가되는 명제를 A규칙을 이용해서 명제의 나열의 원소로 사용할 수 있고, 가정법이나 간접법 등으로 해소된다면 타당한 증명이 될 수 있다.
ㄴ. C규칙
C규칙은 가정법에 의해 참임을 보이는 규칙이다.
A규칙을 통해 문장에 나열된 명제와 T규칙 등(T규칙, 다른 C규칙, I규칙)을 이용해 추론된 명제를 조건문으로 결합한 명제를 명제의 나열의 원소로 사용하는 것을 의미한다.
ㄷ. I규칙
I규칙은 간접법에 의해 참임을 보이는 규칙이다.
A규칙을 통해 문장에 나열된 명제와 항상 거짓인 명제(명제와 부정인 명제가 동시에 참인 경우)를 근거로 A규칙을 통해 문장에 나열된 명제의 부정이 P규칙을 통해 나열된 명제들을 조건으로 하는 정리임을 의미한다.
실제로 어떤 정리1을 증명하자.
정리1. (A,BㅏC)->(A&BㅏC)
1. A,BㅏC (P규칙)
2. Aㅏ(B->C) (T규칙,1)
3. ㅏ(A->(B->C)) (T규칙,2)
4. ㅏ(A&B->C) (T규칙,3)
5. A&BㅏC (T규칙,4)
이 정리는 모든 추론의 전제는 유한집합이라면 명제집합 대신 명제집합의 모든 원소의 &연산을 한 단일명제로 대체할 수 있음을 의미한다.
혼동을 위해 얘기하자면 가정법이 C규칙이 아니고 T규칙인건 ㅏ를 포함한 명제에서 T규칙을 적용한다는 뜻임. "가정법"이라는 이름의 T규칙임.
실제로 C규칙을 이용한 증명은 다음 예시에서 볼 수 있다.
문제 : Proof that A->B, C->D, B|D->!EㅑE->(!A&!C)
1. A->B (P규칙)
2. C->D (P규칙)
3. B|D->!E (P규칙)
4. E (A규칙)
5. !!E (T규칙,4)
6. !(B|D) (T규칙,3,5)
7. !B&!D (T규칙,6)
8. !B (T규칙,7)
9. !D (T규칙,7)
10. !A (T규칙,1,8)
11. !C (T규칙,2,9)
12. !A&!C (T규칙,10,11)
13. E->(!A&!C) (C규칙,4,12)
