형식논리

by I Seul Bee

1장에서는 명제와 논리 연산, 추론 규칙을 직관적인 수준에서 다루었다. 수학적 추론을 엄밀하게 분석하고 명료한 절차에 따라 검증하려면 이러한 논리를 형식적 기호 체계로 표현할 필요가 있다. 형식논리는 일상 언어의 모호함을 줄이고 명확한 구문 규칙과 추론 규칙에 따라 논리적 추론을 전개하게 해 주는 체계이다.

수학에서 주로 사용하는 형식논리는 크게 명제논리와 일계논리가 있다. 명제논리는 명제들 사이의 논리적 관계를 다루는 가장 기본적인 논리 체계이며, 일계논리는 여기에 한정기호와 관계, 함수 등을 추가하여 수학의 많은 내용을 표현할 수 있게 확장한 체계이다. 이들 논리 체계에서는 구문론적 관점(형식적 증명)과 의미론적 관점(진릿값과 모델) 사이의 관계가 핵심적인 주제가 된다.

이 부에서는 형식논리의 기본 개념부터 시작하여 명제논리와 일계논리의 구문론과 의미론을 살펴본다. 특히 건전성과 완전성 정리를 통해 형식적 증명과 의미론적 타당성의 관계를 확인하고, 이것이 수학의 기초에서 어떤 의미를 갖는지 살펴본다.

형식논리의 개념

형식논리는 수학적 추론에서 사용하는 기호와 식, 공리, 추론 규칙을 명시하여 증명을 유한한 기호 조작으로 다룰 수 있게 하는 체계이다. 이 절에서는 “형식적으로 검사할 수 있도록” 효과적으로 제시된 형식계를 생각한다.

정의 11.1. (형식계)

형식계(formal system)는 다음 자료로 이루어진 체계이다.

  • 알파벳(alphabet): 식을 만드는 데 사용하는 기호들의 집합이다.
  • 논리식(formula)의 집합: 알파벳의 기호로 이루어진 유한한 문자열 가운데 문법 규칙을 만족시키는 것들의 집합이다. 주어진 문자열이 논리식인지 형식적으로 판별할 수 있어야 한다.
  • 공리(axiom)의 집합: 증명 없이 출발점으로 허용하는 논리식들의 집합이다. 여기서는 주어진 논리식이 공리인지 형식적으로 판별할 수 있다고 가정한다.
  • 추론 규칙(rule of inference): 유한 개의 논리식을 전제로 하여 새로운 논리식을 결론으로 얻는 규칙이다. 주어진 한 단계가 추론 규칙의 올바른 적용인지 형식적으로 판별할 수 있어야 한다.

정의 11.2. (증명과 정리)

형식계에서 증명(proof)이란 논리식의 유한한 열 \[ \varphi_1,\,\varphi_2,\,\ldots,\,\varphi_n \] 으로서, 각 \(\varphi_i\)가 공리이거나 앞에 나타난 논리식들에 추론 규칙을 적용하여 얻어진 것을 말한다. 어떤 논리식이 어떤 증명의 마지막 논리식으로 나타나면 그 논리식을 그 형식계의 정리(theorem)라고 부른다.

문제 11.1. 논리식이 \(\varphi_n\;(n\in\mathbb N)\)이고, 유일한 공리가 \(\varphi_0\)이며, 유일한 추론 규칙이 \[ \frac{\varphi_n}{\varphi_{n+1}} \] 인 형식계 \(\mathcal F\)를 생각하자. 위와 같은 표기는 “\(\varphi_n\)으로부터 \(\varphi_{n+1}\)을 추론한다”라는 뜻이다. 다음 유한한 논리식의 열이 \(\mathcal F\)의 증명인지 판정하시오. 증명이라면 마지막 논리식이 어떤 정리인지도 쓰시오.

  1. \(\varphi_0\)
  2. \(\varphi_0,\varphi_1,\varphi_2,\varphi_3\)
  3. \(\varphi_0,\varphi_2\)
  4. \(\varphi_1,\varphi_2\)
  5. \(\varphi_0,\varphi_1,\varphi_1,\varphi_2\)

이처럼 효과적으로 주어진 형식계에서는 주어진 유한한 논리식의 열이 올바른 증명인지 검사할 수 있다. 따라서 가능한 유한한 문자열들을 차례로 조사함으로써 정리들을 체계적으로 열거할 수 있다. 그러나 주어진 논리식이 정리인지 아닌지를 항상 유한한 시간 안에 판별할 수 있는지는 별개의 문제이다. 이러한 판별 절차가 존재하는 성질을 “결정가능하다(decidable)”라고 표현한다. 정리 여부가 결정가능한 형식계도 있고 그렇지 않은 형식계도 있다.

문제 11.2. 효과적으로 주어진 형식계에 관한 다음 명제의 참과 거짓을 판정하고 이유를 설명하시오.

  1. 주어진 유한한 논리식의 열이 올바른 증명인지 여부는 유한한 절차로 검사할 수 있다.
  2. 형식계의 정리들을 하나씩 체계적으로 열거할 수 있다.
  3. 정리들을 열거할 수 있으면, 임의의 논리식이 정리인지 여부도 항상 유한한 시간 안에 판정할 수 있다.
  4. 어떤 논리식이 정리의 열거 과정에서 처음 \(N\)단계까지 나타나지 않았다면 그 논리식은 정리가 아니다.

정의 11.3. (메타정리)

형식계 자체를 수학적 대상으로 삼아 그 체계의 증명, 정리, 결정가능성 등의 성질에 관하여 얻는 정리를 메타정리(metatheorem)라고 한다. [초수학적 정리라고도 부른다.] 메타정리는 주어진 형식계 안에서 증명되는 정리와 구별되는, 그 형식계에 관한 수학적 진술이다.

형식계의 간단한 예로 호프스태터의 MU-계(MU-system)를 살펴보자.

MU-계의 알파벳은 \(\{\mathrm{M},\mathrm{I},\mathrm{U}\}\)이며, 이 세 기호로 이루어진 비어 있지 않은 모든 문자열을 논리식으로 삼는다. 공리는 하나뿐이다. \[ \mathrm{MI} \] 추론 규칙은 다음 네 가지이다.

  • 규칙 1. \(\mathrm{I}\)로 끝나는 문자열의 끝에 \(\mathrm{U}\)를 추가할 수 있다.
  • 규칙 2. \(\mathrm{M}x\) 꼴의 문자열에서 \(\mathrm{M}\) 뒤에 이어지는 문자열 \(x\)를 복제하여 \(\mathrm{M}xx\)를 얻을 수 있다.
  • 규칙 3. 문자열에 \(\mathrm{I}\) 세 개가 연달아 나타나면 그 세 문자를 \(\mathrm{U}\) 하나로 바꿀 수 있다.
  • 규칙 4. 문자열에 \(\mathrm{U}\) 두 개가 연달아 나타나면 그 두 문자를 없앨 수 있다.

문제 11.3. MU-계의 추론 규칙을 직접 적용하여 다음 물음에 답하시오.

  1. \(\mathrm{MI}\)에서 추론 규칙을 한 번 적용하여 얻을 수 있는 모든 문자열을 구하시오.
  2. \(\mathrm{MIII}\)에서 추론 규칙을 한 번 적용하여 얻을 수 있는 모든 문자열을 구하시오.
  3. 다음 각 변환이 추론 규칙을 한 번 적용하는 것인지 판정하고, 맞으면 사용한 규칙의 번호를 쓰시오. \[ \mathrm{MII}\to\mathrm{MIIU},\quad \mathrm{MII}\to\mathrm{MIIII},\quad \mathrm{MIIII}\to\mathrm{MUI},\quad \mathrm{MUU}\to\mathrm{M},\quad \mathrm{MUI}\to\mathrm{MUII}. \]

MU-계에서의 증명의 예는 다음과 같다. \[ \mathrm{MI} \longrightarrow \mathrm{MII} \longrightarrow \mathrm{MIIII} \longrightarrow \mathrm{MUI} \longrightarrow \mathrm{MUIU}. \] 차례로 규칙 2, 규칙 2, 규칙 3, 규칙 1을 적용한 것이다.

공리에는 \(\mathrm{M}\)이 맨 앞에 정확히 한 번 나타나고, 어느 추론 규칙도 새로운 \(\mathrm{M}\)을 만들거나 그 위치를 바꾸지 않는다. 따라서 MU-계의 모든 정리는 \(\mathrm{M}x\) 꼴이며, 여기서 \(x\)에는 \(\mathrm{I}\)와 \(\mathrm{U}\)만 나타난다.

문제 11.4. 다음 각각이 MU-계 내부의 논리식 자체인지, 아니면 MU-계에 관한 메타 수준의 진술인지 구별하시오. 논리식 자체인 경우에는 지금까지 제시된 증명이나 공리를 이용하여 정리인지도 판정하시오.

  1. \(\mathrm{MI}\)
  2. \(\mathrm{MUIU}\)
  3. “MU-계의 모든 정리는 \(\mathrm{M}\)으로 시작한다.”
  4. “\(\mathrm{MU}\)는 MU-계의 정리가 아니다.”

문제 11.5. MU-계에서 다음 문자열이 정리인지 확인하시오. 정리이면 증명을 제시하고, 정리가 아니라면 이유를 설명하시오.

  1. MIIII
  2. MUUII
  3. MUIIII
  4. MUIUIU
  5. MIII

이제 다음과 같은 질문을 생각해 보자.

“\(\mathrm{MU}\)는 정리인가?”

이 질문에 답하기 위해 MU-계에 관한 다음 메타정리를 증명하자.

문제 11.6. 문자열 \(w\)에 나타나는 \(\mathrm{I}\)의 개수를 \(N_{\mathrm I}(w)\)라고 하자. 한 추론 규칙을 적용하기 전의 문자열을 \(s\), 적용한 뒤의 문자열을 \(t\)라고 할 때 다음 물음에 답하시오.

  1. 네 추론 규칙 각각에 대하여 \(N_{\mathrm I}(t)\)를 \(N_{\mathrm I}(s)\)로 나타내시오.
  2. \(N_{\mathrm I}(s)\)를 \(3\)으로 나눈 나머지가 \(1\) 또는 \(2\)이면 \(N_{\mathrm I}(t)\)도 \(3\)의 배수가 될 수 없음을 확인하시오.
  3. 공리 \(\mathrm{MI}\)에서 시작하는 어떤 증명에서도 마지막 문자열의 \(\mathrm{I}\)의 개수가 \(3\)의 배수가 될 수 없을 것이라고 예상할 수 있는 이유를 설명하시오.

정리 11.4.

MU-계의 정리에서 \(\mathrm{I}\)가 나타나는 횟수는 \(3\)의 배수가 아니다.

증명 증명 길이에 대한 수학적 귀납법을 사용한다. 증명 길이가 \(1\)이면 마지막 논리식은 공리 \(\mathrm{MI}\)이고, \(\mathrm{I}\)의 개수는 \(1\)이므로 주장이 성립한다.

길이가 \(n\) 이하인 모든 증명의 마지막 논리식에서 주장이 성립한다고 가정하고, 길이가 \(n+1\)인 증명의 마지막 논리식을 \(t\)라고 하자. \(t\)가 공리가 아니면 MU-계의 각 추론 규칙은 전제를 하나만 가지므로, \(t\)는 길이가 \(n\) 이하인 증명을 갖는 어떤 정리 \(s\)에 한 추론 규칙을 적용하여 얻어진다. \(s\)에 나타나는 \(\mathrm{I}\)의 개수를 \(x\), \(t\)에 나타나는 \(\mathrm{I}\)의 개수를 \(y\)라고 하자. 귀납가정에 의해 \(3\nmid x\)이다.

규칙 1과 규칙 4에서는 \(y=x\)이다. 규칙 2에서는 \(y=2x\)이므로 \(3\nmid y\)이다. 규칙 3에서는 \(y=x-3\)이므로 \(y\equiv x\pmod 3\)이다. 따라서 어느 경우에도 \(3\nmid y\)이고, 수학적 귀납법에 의해 정리가 증명된다.

문자열 \(\mathrm{MU}\)에는 \(\mathrm{I}\)가 \(0\)개 나타나며 \(0\)은 \(3\)의 배수이다. 따라서 정리 11.4에 의해 \(\mathrm{MU}\)는 MU-계의 정리가 아니다.

문제 11.7. MU-계의 추론 규칙을 사용하여 다음 물음에 답하시오.

  1. \(\mathrm{MIII}\)로부터 \(\mathrm{MU}\)를 유도할 수 있는가?
  2. \(\mathrm{MIIIIII}\)로부터 \(\mathrm{MUI}\)를 유도할 수 있는가?
  3. \(\mathrm{MUUIII}\)로부터 \(\mathrm{MIII}\)를 유도할 수 있는가?

문제 11.8. MU-계에서 \(\mathrm{U}\)의 개수에 대한 다음 명제를 증명하거나 반례를 제시하시오.

  1. MU-계의 모든 정리는 \(\mathrm{U}\)를 짝수 개 포함한다.
  2. \(\mathrm{M}\)으로 시작하고 \(\mathrm{U}\)를 정확히 \(1\)개 포함하는 모든 문자열은 정리이다.
  3. MU-계의 정리에서 \(\mathrm{U}\)의 개수에는 최댓값이 존재한다.

문제 11.9. 정리 11.4의 부분적인 역을 증명하시오. 즉 \(x\)가 \(\mathrm{I}\)와 \(\mathrm{U}\)만으로 이루어진 문자열이고 \(x\)에 나타나는 \(\mathrm{I}\)의 개수가 \(3\)의 배수가 아니면 \(\mathrm{M}x\)는 MU-계의 정리임을 증명하시오. (\(x\)의 각 \(\mathrm{U}\)를 \(\mathrm{III}\)로 바꾸어 얻는 문자열을 생각한다. 또한 \(r\ge4\)일 때 규칙 1, 규칙 3, 규칙 4를 차례로 사용하면 \(\mathrm{MI}^r\)에서 \(\mathrm{MI}^{r-3}\)을 유도할 수 있다.)

정리 11.5. (MU-계 정리의 조건)

비어 있지 않은 문자열 \(w\)가 MU-계의 정리일 필요충분조건은 어떤 \(\mathrm{I}\)와 \(\mathrm{U}\)만으로 이루어진 문자열 \(x\)가 존재하여 \(w=\mathrm{M}x\)이고, \(x\)에 나타나는 \(\mathrm{I}\)의 개수가 \(3\)의 배수가 아닌 것이다.

정리 11.4와 문제 11.9를 합치면 정리 11.5를 얻는다. 따라서 MU-계에서는 주어진 문자열이 정리인지 여부를 실제로 결정할 수 있다. 이는 형식계에 따라 정리 여부의 결정가능성이 달라질 수 있다는 앞의 설명을 보여 주는 간단한 예이다.

문제 11.10. 정리 11.5를 사용하여 다음 문자열이 MU-계의 정리인지 판정하시오. 이 문제에서는 실제 증명을 구성하지 않아도 된다.

  1. \(\mathrm{MI}\)
  2. \(\mathrm{MU}\)
  3. \(\mathrm{MIIIU}\)
  4. \(\mathrm{MUUII}\)
  5. \(\mathrm{UMI}\)
  6. \(\mathrm{MMII}\)

집합과 수리논리 첫걸음 목차 보기

명제와 논리 집합의 개념 다양한 집합의 연산 관계와 함수 유한집합과 무한집합 자연수 집합의 기수 집합의 서수 집합론의 공리 선택 공리 형식논리 명제논리의 개념 명제논리의 건전성과 완전성 일계논리의 구문론 일계논리의 의미론 일계논리의 추론규칙 일계논리의 콤팩트성 페아노 산술 불완전성 정리