명제논리를 논할 때는 두 가지 관점에서 접근할 수 있다. 하나는 구문론적 관점이며 다른 하나는 의미론적 관점이다. 구문론적 관점에서는 문자열의 의미를 고려하지 않고 오직 기호 사이의 형식적 관계에만 관심을 가진다. 반면 의미론적 관점에서는 논리변수의 진릿값 배정에 따른 논리식의 진릿값과 논리식 사이의 논리적 귀결에 관심을 가진다.
이 두 관점은 상당히 다른 것처럼 보이지만, 실제로는 밀접하게 연관되어 있다. 주어진 가정 하에서 구문론적 관점에서 형식적으로 증명 가능한 논리식은 가정의 논리적 귀결이 되며, 그 역도 성립한다. 이러한 두 관점의 연결은 명제논리의 건전성과 완전성 정리를 통해 확립된다.
1. 건전성과 완전성의 의미
건전성(soundness)은 형식계에서의 정리가 논리적 귀결이 되는 성질이다. 즉, 형식적 추론을 통해 얻어진 결론은 의미론적으로도 타당하다는 것을 의미한다. 반면, 완전성(completeness)은 논리적 귀결이 되는 논리식은 형식적으로도 추론 가능하다는 성질이다.
명제논리는 건전성과 완전성을 모두 갖추고 있다. 즉, \(\varSigma\)가 논리식의 집합이고 \(\sigma\)가 논리식일 때 다음이 성립한다. \[\varSigma \models \sigma \quad \Longleftrightarrow \quad \varSigma \vdash \sigma \] 여기서 \(\varSigma \models \sigma\)는 "\(\sigma\)는 \(\varSigma\)의 논리적 귀결이다"라는 의미론적 주장이고, \(\varSigma \vdash \sigma\)는 "\(\sigma\)는 \(\varSigma\)로부터 형식적으로 추론될 수 있다"라는 구문론적 주장이다. 이 동치관계에서 순방향(\(\Rightarrow\))이 완전성이며, 역방향(\(\Leftarrow\))이 건전성이다.
2. 건전성 정리와 완전성 정리
건전성과 완전성을 증명하기 위해 먼저 몇 가지 용어를 정의하자. \(\varSigma\)가 논리식의 집합일 때, 만약 논리식 \(\psi\)가 존재하여 \(\psi\)와 \((\neg\psi)\)가 모두 \(\varSigma\)로부터 추론 가능하면 \(\varSigma\)는 결함이 있다(inconsistent)라고 한다. 그렇지 않은 경우 \(\varSigma\)는 무모순이다(consistent) 또는 무결하다라고 한다.
다음은 명제논리의 건전성과 완전성 정리이다.
정리 13.1. (명제논리의 건전성과 완전성)
임의의 논리식 집합 \(\varSigma\)에 대하여, \(\varSigma\)가 무모순일 필요충분조건은 값매김 \(v\)가 존재하여 임의의 \(\sigma \in \varSigma\)에 대하여 \(v(\sigma) = \mathrm{T}\)를 만족시키는 것이다.
이 정리로부터 다음과 같은 중요한 결과를 얻을 수 있다.
- 논리식이 항진일 필요충분조건은 정리인 것이다.
- \(\varSigma\)가 논리식의 집합이고 \(\sigma\)가 논리식일 때, \(\sigma\)가 \(\varSigma\)의 논리적 귀결일 필요충분조건은 \(\sigma\)가 \(\varSigma\)로부터 추론 가능한 것이다.
건전성 정리의 증명 개요
건전성 정리의 증명은 다음 두 가지 사실을 바탕으로 한다.
- 모든 공리는 항진이다.
- 추론규칙 MP는 진릿값을 보존한다. 즉, \(v(\phi) = \mathrm{T}\)이고 \(v((\phi \to \psi)) = \mathrm{T}\)이면 \(v(\psi) = \mathrm{T}\)이다.
이 두 가지 사실을 바탕으로, 증명 길이에 대한 수학적 귀납법을 적용하여 모든 정리가 항진임을 증명할 수 있다. 이로써 형식적으로 추론 가능한 모든 명제는 의미론적으로도 타당하다는 건전성이 증명된다.
완전성 정리의 증명 개요
완전성 정리의 증명은 다음과 같은 단계로 진행된다.
- 먼저 \(\varSigma\)가 무모순일 때, 임의의 논리식 \(\phi\)에 대하여 \(\varSigma \cup \{\phi\}\)와 \(\varSigma \cup \{(\neg \phi)\}\) 중 하나는 무모순임을 보인다.
- 이 사실을 활용하여 \(\varSigma\)를 무모순인 극대 집합 \(\varSigma^+\)로 확장한다. 이 과정에서 모든 논리식 \(\phi\)에 대해 \(\phi\)와 \((\neg \phi)\) 중 정확히 하나만 \(\varSigma^+\)에 속하도록 한다.
- 값매김 함수 \(v\)를 다음과 같이 정의한다. \[v(p_i) := \begin{cases} \mathrm{T} & (p_i \in \varSigma^+\text{일 때}) \\ \mathrm{F} & (p_i \notin \varSigma^+\text{일 때}) \end{cases}\]
- 수학적 귀납법을 사용하여 임의의 논리식 \(\phi\)에 대해 \(v(\phi) = \mathrm{T}\)일 필요충분조건이 \(\phi \in \varSigma^+\)임을 증명한다.
- 이로써 \(\varSigma\)에 속하는 모든 논리식이 참이 되도록 하는 값매김이 존재하고, 따라서 의미론적으로 타당한 모든 명제는 형식적으로도 추론 가능하다는 완전성이 증명된다.
문제 13.1. 형식계의 무모순성에 대해 다음을 답하시오.
- MU-계에서 부정 기호가 정의되지 않았는데, 이 형식계의 무모순성을 어떻게 정의할 수 있는가?
- 모든 문자열이 정리가 되는 형식계는 무모순인가?
- 공리가 없는 형식계는 항상 무모순인가?
3. 명제논리의 콤팩트성
명제논리의 건전성과 완전성으로부터 중요한 결과인 콤팩트성이 도출된다. 콤팩트성은 다음과 같이 정의된다.
정리 13.2. (명제논리의 콤팩트성)
\(\varSigma\)가 논리식의 집합일 때, 만약 \(\varSigma\)의 임의의 유한부분집합이 만족될 수 있다면(satisfiable) \(\varSigma\) 자체도 만족될 수 있다.
여기서 집합이 '만족될 수 있다'(satisfiable)는 것은 값매김 함수 \(v\)가 존재하여 해당 집합의 모든 논리식에 대해 \(v(\sigma) = \mathrm{T}\)를 만족시킨다는 의미이다.
콤팩트성 정리는 건전성과 완전성을 활용하여 증명할 수 있다. 그 핵심은 모순이 도출되려면 반드시 유한 개의 논리식만이 필요하다는 사실에 있다. 따라서 모든 유한부분집합이 만족될 수 있다면, 모순이 도출될 수 없고 전체 집합 역시 만족될 수 있다.
4. 콤팩트성의 응용: 평면지도의 사색 정리
명제논리의 콤팩트성은 수학의 여러 분야에 활용된다. 특히 주목할 만한 응용 중 하나는 유한평면지도의 사색 정리를 무한평면지도로 확장하는 것이다.
정리 13.3. (유한평면지도의 사색 정리)
임의의 유한평면지도를 채색하는 데에는 4가지 색이면 충분하다.
이 정리는 1976년 아펠(Kenneth Appel)과 하켄(Wolfgang Haken)이 컴퓨터의 도움을 받아 증명한 것으로 유명하다. 명제논리의 콤팩트성을 활용하면 이 정리를 무한평면지도로 확장할 수 있다.
정리 13.4. (평면지도의 사색 정리)
임의의 평면지도(유한 또는 무한)를 채색하는 데에는 4가지 색이면 충분하다.
이 확장의 핵심 아이디어는 다음과 같다.
- 무한평면지도의 각 국가에 대응하는 명제변수를 도입한다.
- 각 국가가 정확히 하나의 색을 가지도록 하는 논리식과, 인접한 국가가 서로 다른 색을 가지도록 하는 논리식을 정의한다.
- 이 논리식들의 집합의 임의의 유한부분집합은 유한평면지도에 대응되므로, 유한평면지도의 사색 정리에 의해 만족될 수 있다.
- 콤팩트성 정리에 의해 전체 논리식 집합도 만족될 수 있으므로, 무한평면지도 역시 4색으로 채색 가능하다.