Propositional calculus ('모든'과 '어떤'의 개념을 사용하지 않는 0차 술어 논리 기준)으로,
수학에서 증명이란, 대충 말하면, 주어진 명제의 집합들로부터, 주어진 공리와 주어진 논리 법칙을 사용하여, 유한 번의 과정을 통해 어떤 명제를 이끌어내는 것을 말한다.
이러한 증명의 의미를 보다 명확히 하기 위해서는, 기본적으로
1. 명제가 무엇인지 그 범위를 정하고
2. 무엇을 공리로 할 것인지를 정하고
3. 무엇을 논리 법칙으로 할 것인지를 정해야 한다.
그리고 저 3가지를 어떻게 정하는지에 따라서 서로 다른 증명 체계를 만들 수 있다.
여기서 소개할 것은 '모든'과 '어떤'의 개념을 쓰지 않는 정말 간단한 0차 술어 논리 체계를 사용할 것이다. 그리고 0차 술어 논리 체계의 다양한 증명 체계 중 매우 간단하고 간결한 증명 체계인 힐베르트 시스템을 소개하고자 한다. (미리 말하지만, 간단한 것과 쉬운 것은 다른 것이다. 간결함을 포기하면 natural deduction system같은 더 직관적인 증명 체계도 있다.)
1. 0차 술어 논리체계에서의 명제
우선 명제를 구성하는 요소 중 어떠한 문자를 쓸 것인지를 정해야 한다. 즉, 논리의 언어로 쓸 문자를 정하는 것이다.
이 중에 기본 요소를 모아 놓은 것을 A={a1, a2, a3, ...} 라고 하자. (유한 집합이어도 되고, 무한 집합이어도 된다. 보통은 무한집합이다.)
그 다음에는 이 문자들을 연결해서 새로운 문장을 만들어 낼 수 있도록 접속사(connectives)를 모아 놓은 것을 C={->, ~} 라고 하자.
(사실, C는 유한집합이어도 되고, 무한집합이어도 된다. 보통은 공집합이 아닌 유한집합이다. 관습적으로 ~은 'OO이 아니다' 라는 의미로, ->는 'OO이면, OO이다'는 뜻으로 많이 쓴다.)
그리고 여기에 소괄호 ')' 와 '(' 도 각각 사용할 문자로 보겠다.
이러면, 수학에서 쓸 문자들의 집합은 AUCU{ (, ) } 가 된다. 그리고 이러한 문자들의 집합의 원소들을 유한 번 사용하여 나열한 집합을 S라고 하자. 대충 영어와 같이 알파벳이 있고, 그 알파벳을 유한한 개수를 써서 일렬로 나열한 것을 모아 놓았다고 생각하면 된다.
컴퓨터 공학 느낌으로 말하면, 문자는 character이고, S는 string의 집합이다.
그러면, S의 원소 중에서
명제의 정의는 다음과 같다.
1) A의 원소들은 모두 명제이다.
2) a와 b가 명제이면, (a->b), ~a도 명제이다.
3) 규칙 1과 규칙 2를 유한 번 적용하여 만들 수 없는 S의 원소는 명제가 아니다.
예를 들어, (a1->a2), ~a1, ~~a1, ~(~a1->~(a1->~~a5)) 같은 게 명제이다. 참고로, 양끝에 ( ) 가 있으면, 이 괄호는 생략하기도 한다.
2. 힐베르트의 증명 시스템.
힐베르트의 증명 시스템에서,
기본 요소들의 집합 A={a1, a2, ... an, ..} 이다. (그냥 countable인 집합을 아무거나 설정해주면 된다.)
접속사들의 집합 C={~, ->} 이다.
집합 P로부터의 명제 bn에 대한 증명이란, 특정 조건을 만족하는 명제들의 나열로서,
(b1, b2, b3, b4, ....., bn) 이 있고, 각각의 명제들이 다음의 조건 중 하나를 만족하면 (b1, b2, b3, b4, ....., bn)을 P로부터의 bn에 대한 증명이라고 한다.
a) bi는 P의 원소이다.
b) bi는 공리이다.
c) bi는 논리 법칙에 의해 유도되었다.
그리고 힐베르트 시스템에서,
공리들의 집합={a->(b->a) | a와 b는 명제}U{ (a->(b->c))->((a->b)->(a->c)) | a, b, c는 명제}U{(~a->~b)->(b->a) | a, b는 명제} 이다.
좀 더 보기 쉽게 쓰면, 다음의 형태를 띄고 있으면 공리이다.
공리 1 : a->(b->a)
공리 2 : (a->(b->c))->((a->c)->(a->c)) (대충 설명하면, -> 의 분배 법칙이다.)
공리 3 : (~a->~b)->(b->a) (대충 설명하면, 대우인데, 주의할 점은 ~을 없애는 방향만을 공리로 삼고 있지, ~을 첨가하는 방향을 공리로 삼고 있지 않다는 것이다.)
논리 법칙은 주어진 명제의 나열 (b1, b2, b3, b4, ....., bn)가 있을 때,
어떤 n이하의 양의 정수 i, j에 대해, bi가 (a->b)이고, bj가 a이면, b를 n+1 번째 명제로 놓을 수 있다는 것이다.
참고로, 이러한 형태의 논리 법칙을 논리학에서는 전건 긍정 혹은 modus ponens 라고 부른다.
즉, 힐베르트 시스템은 3가지 형태의 공리들(공리 자체는 무한 개)과 1개의 논리 법칙만을 사용한 증명 체계이다.
예를 들어 보자.
힐베르트 시스템에서, 다음을 증명해 보자. (여기서는 대충 A, B, C를 명제라고 보겠다. 원래 위에서 정한 대로면 a1, a2, a3라고 써야 하지만 말이다.)
ㄱ. {a1, a2, (a3->a2)} 로부터 (a3->a1)을 증명해라.
ㄴ. 공집합으로부터 (B->B)를 증명해라.
ㄷ. {(A->B), (B->C)} 로부터 (A->C)를 증명해라.
증명 : 가독성을 위해, 명제를 세로로 나열하고, 양끝에 있는 괄호는 생략하겠다. 그리고 각 줄의 오른쪽에는 어떤 조건을 만족해서 그 명제를 나열할 수 있는지를 쓰고, 각 줄의 왼쪽에는 몇 번째 명제인지를 적겠다. 참고로, 풀이 과정을 눈으로만 따라가려고 하면 힐베르트 시스템을 어떻게 사용한 것인지 헷갈릴 가능성이 있다.
ㄱ. P={a1, a2, (a3->a2)} 로부터 a3->a1 증명하기.
1. a1 P의 원소
2. a1->(a3->a1) 공리 1
3. a3->a1 1과 2에 대한 전건긍정
ㄴ. P=공집합 으로부터 B -> B 증명하기
1 B->(B->B) 공리1
2. (B->((B->B)->B)) -> ((B->(B->B)) -> (B->B)) 공리2
3. B->((B->B)->B) 공리 1 (참고로, 위의 공리 1에서 a를 B로, b를 (B->B)로 두면 된다.)
4. (B->(B->B)) -> (B->B) 2와 3의 전건 긍정
5. B -> B 1과 4의 전건 긍정
ㄷ. P={(A->B), (B->C)} 로부터 A->C 증명하기.
1. A->B P의 원소
2. B->C P의 원소
3. (A->(B->C)) -> ((A->B) -> (A->C)) 공리 2
4. (B->C)->(A->(B->C)) 공리 1
5. A->(B->C) 2와 4에 대한 전건긍정
6. (A->B) -> (A->C) 3과 5에 대한 전건긍정
7. A->C 1과 6에 대한 전건긍정
근데, 아직 공리3을 쓰지 않았다. 이를 활용해야 하는 증명 방법은 연습문제로 남겨두겠다.
연습 문제)
1. 공집합으로부터 (A->~~A)를 증명해라.
2. 공집합으로부터 (A->B) -> (~B->~A) 를 증명해라.
한 번 위 두 연습문제의 답을 댓글로 써서 풀이를 공유해 보자. 피드백도 해줄 수 있다.
참고로, 이 연습 문제를 풀려면 당연히 공리3이 필요하다.
여담 : 사실 초심자에게는 Natural deduction system을 배우는 게 매우 직관적이고 받아들이기 쉽다. natural deduction system은 접속사로 {~, ->. &, v, <->}를 사용하며, 11개의 논리 법칙과 0개의 공리로 이루어진 증명 체계이다. 힐베르트 시스템보다 정의나 성질을 증명하는 것은 더럽지만 훨씬 직관적이다.
