수학적 추론을 엄밀하게 분석하고 기계적으로 검증하기 위해서는 논리를 형식적 기호 체계로 표현해야 한다. 형식논리는 일상 언어의 모호함을 배제하고 명확한 규칙에 따라 논리적 추론을 전개할 수 있게 해주는 강력한 도구이다.
수학에서 주로 사용하는 형식논리는 크게 명제논리와 일계논리로 나뉜다. 명제논리는 명제들 사이의 논리적 관계를 다루는 가장 기본적인 논리 체계이며, 일계논리는 여기에 한정사와 관계, 함수 등을 추가하여 수학의 대부분 내용을 표현할 수 있게 확장한 체계이다. 이들 논리 체계에서는 구문론적 관점(형식적 증명)과 의미론적 관점(진릿값과 모델) 사이의 관계가 핵심적 주제가 된다.
이 부에서는 형식논리의 기본 개념부터 시작하여 명제논리와 일계논리의 구문론과 의미론을 살펴본다. 특히 건전성과 완전성 정리를 통해 형식적 증명과 논리적 타당성이 정확히 일치함을 확인하고, 이것이 수학의 기초에 어떤 의미를 갖는지 살펴본다.
형식논리의 개념
형식논리는 수학적 추론을 엄밀하게 정의하고 기호를 통해 표현하는 체계이다. 일상 언어의 모호함을 배제하고 명확한 규칙에 따라 논리적 사고를 전개할 수 있도록 한다. 형식논리는 수학의 기초를 확립하는 데 중요한 역할을 한다.
형식계(formal system)는 다음 네 가지로 구성된 체계이다.
- 알파벳 \(A\): 기호의 집합이다.
- 논리식(formula)의 집합: 각 논리식은 \(A\)에 속한 기호로 이루어진 문자열이다. 주어진 문자열이 논리식인지 여부를 판별하는 형식적 절차[의미를 따지지 않고 규칙만을 유한 번 적용하는 절차]가 존재한다.
- 공리(axiom)의 집합: 각 공리는 논리식이다. 모든 논리식이 공리인 것은 아니며, 주어진 논리식이 공리인지 여부를 판별하는 형식적 절차가 존재한다.
- 추론규칙(rule of inference): 각 추론규칙은 유한 개의 논리식을 입력받아 하나의 논리식을 출력한다. 추론규칙을 적용하는 형식적인 절차가 존재한다.
형식계에서 증명(proof)이란 논리식의 열로, 각 논리식은 공리이거나 이전 항에 등장한 논리식에 추론규칙을 적용하여 얻어진 것이다. 증명의 마지막 항을 정리(theorem)라고 부른다.
하나의 형식계에서 모든 정리는 형식적인 절차에 의하여 얻어질 수 있다. 그러나 일반적으로 주어진 논리식이 정리인지 아닌지를 판별하는 절차는 존재하지 않는다. 형식계가 가진 특성에 따라 주어진 논리식이 정리인지를 밝혀내는 것이 가능할 수도 있고 그렇지 않을 수도 있다.
형식계 자체를 수학적 대상으로 다루면 상위수학정리(metatheorem)['초수학정리' 또는 '수학외적정리'라고도 부른다.]를 얻을 수 있다. 이것은 형식계 자체의 특성에 대한 정리로서, 형식계 내에서 얻어지는 정리와는 다른 개념이다.
형식계의 예: MU-계
형식계의 예로 호프스태터의 \(\mathrm{MU}\)-계(MU-system)를 살펴보자.
MU-계에서 알파벳은 집합 \(\left\{ \mathrm{M},\, \mathrm{I},\, \mathrm{U}\right\}\)이며 논리식은 비어있지 않은 문자열이다. 공리는 다음과 같이 단 하나 존재한다. \[\mathrm{M I}\] 추론규칙은 다음과 같이 네 개가 존재한다.
- 규칙 1. \(\mathrm{I}\)로 끝나는 문자열에는 끝에 \(\mathrm{U}\)를 추가할 수 있다.
- 규칙 2. \(\mathrm{M}\)으로 시작하는 문자열 \(\mathrm{Mx}\)에 대하여 \(\mathrm{M}\) 뒤에 이어지는 문자열을 복제하여 \(\mathrm{Mxx}\)를 얻을 수 있다.
- 규칙 3. 문자열에 \(\mathrm{I}\) 세 개가 연달아 나타나면 그 세 개의 문자를 \(\mathrm{U}\)로 바꿀 수 있다.
- 규칙 4. 문자열에 \(\mathrm{U}\) 두 개가 연달아 나타나면 그 두 개의 문자를 없앨 수 있다.
MU-계에서의 증명의 예로서 다음과 같은 것을 들 수 있다. \[\mathrm{MI,} \quad \mathrm{MII,} \quad \mathrm{MIIII,} \quad \mathrm{MUI,} \quad \mathrm{MUIU}.\] 이 증명은 공리 \(\mathrm{MI}\)로부터 시작하여 규칙 2를 두 번 적용하고 규칙 3과 규칙 1을 이어서 적용한 것이다.
문제 11.1. MU-계에서 다음 문자열이 정리인지 확인하시오. 정리이면 증명을 제시하고, 정리가 아니라면 이유를 설명하시오.
- MIIII
- MUUII
- MUIIII
- MUIUIU
- MIII
이제 다음과 같은 질문을 생각해 보자.
"\(\mathrm{MU}\)는 정리인가?"
이 질문에 답하기 위해 다음과 같은 상위수학정리를 도입하자.
정리 11.1.
MU-계의 정리에서 \(\mathrm{I}\)가 나타나는 횟수는 \(3\)의 배수가 아니다.
증명
증명 길이에 대한 수학적 귀납법을 사용한다.
기본 단계: 가장 짧은 증명은 공리 \(\mathrm{MI}\)로만 이루어져 있다. \(\mathrm{MI}\)에는 \(\mathrm{I}\)가 1개 포함되어 있고, 1은 3의 배수가 아니므로 주장이 성립한다.
귀납 단계: 증명 길이가 \(n\)인 정리 \(t\)에 대해, \(t\)는 증명 길이가 \(n-1\)인 정리 \(s\)에 추론 규칙을 적용하여 얻어진 것이다. \(s\)에 나타나는 \(\mathrm{I}\)의 개수를 \(x\)라고 하자. 귀납적 가정에 의하여 \(x\)는 \(3\)의 배수가 아니다. \(t\)에 나타나는 \(\mathrm{I}\)의 개수를 \(y\)라고 하자. 각 추론 규칙을 적용했을 때 \(x\)와 \(y\)의 관계를 등식으로 나타내면 다음과 같다.
- 규칙 1: \(y=x\)
- 규칙 2: \(y=2x\)
- 규칙 3: \(y=x-3\)
- 규칙 4: \(y=x\)
각 경우에 \(y\)는 \(3\)의 배수가 아니다. 따라서 수학적 귀납법에 의하여 정리가 증명되었다.
위 정리에 의하면, '\(\mathrm{MU}\)'에는 \(\mathrm{I}\)가 없으므로 \(\mathrm{MU}\)는 MU-계의 정리가 아니다.
문제 11.2. MU-계의 추론규칙을 사용하여 다음 물음에 답하시오.
- \(\mathrm{MIII}\)로부터 \(\mathrm{MU}\)를 유도할 수 있는가?
- \(\mathrm{MIIIIII}\)로부터 \(\mathrm{MUI}\)를 유도할 수 있는가?
- \(\mathrm{MUUIII}\)로부터 \(\mathrm{MIII}\)를 유도할 수 있는가?
문제 11.3. MU-계에서 \(\mathrm{U}\)의 개수에 대한 다음 명제를 증명 또는 반증하시오.
- MU-계의 모든 정리는 \(\mathrm{U}\)를 짝수 개 포함한다.
- \(\mathrm{M}\)으로 시작하고 \(\mathrm{U}\)를 정확히 1개 포함하는 모든 문자열은 정리이다.
- MU-계의 정리에서 \(\mathrm{U}\)의 최대 개수는 존재하는가?
문제 11.4. 정리 11.1의 (부분적인) 역이 성립함을 증명하시오. 즉 \(\mathrm{MU}\)-계에서 \(\mathrm{M}\)으로 시작하고 \(\mathrm{I}\)가 나타나는 횟수가 3의 배수가 아닌 논리식은 정리임을 증명하시오.