명제논리의 건전성, 완전성, 긴밀성

By | November 18, 2016

명제논리에 대하여 논할 때는 두 가지 관점에서 논하게 된다. 하나는 구문론적 관점이며 다른 하나는 의미론적 관점이다. 구문론에서는 문자열의 의미는 따지지 않고 오직 기호 사이의 형식적 관계에만 관심을 가진다. 반면 의미론에서는 논리변수의 진릿값 배정에 따른 논리식의 진릿값과 논리식 사이의 논리적 귀결에 대해 관심을 가진다.

이들 두 관점은 완전히 서로 다른 것처럼 보이지만, 사실은 밀접한 연관을 가지고 있다. 즉 가정이 주어졌을 때 구문론적 관점에서 형식적으로 증명 가능한 논리식은 가정의 논리적 귀결이 되며 그 역도 성립한다. 형식계에서의 정리가 논리적 귀결이 되는 성질을 건전성(soundness)이라고 부르며, 논리적 귀결이 되는 논리식은 형식적으로 추론 가능하다는 성질을 완전성(completeness)이라고 부른다.

명제논리의 건전성과 완전성

명제논리는 건전성과 완전성을 모두 가지고 있다. 즉 \(\Sigma\)가 논리식의 모임이고 \(\sigma\)가 논리식일 때 \[\Sigma \models \sigma \quad \Longleftrightarrow \quad \Sigma \vdash \sigma \] 이다. 여기서 순방향(\(\Rightarrow\))이 완전성이며, 역방향(\(\Leftarrow\))이 건전성이다.

명제논리의 건전성과 완전성을 증명하기 전에 몇 가지 용어를 정의하자. \(\Sigma\)가 논리식의 집합이라고 하자. 만약 논리식 \(\psi\)가 존재하여 \(\psi\)와 \( (\neg\psi )\)가 모두 \(\Sigma\)로부터 추론 가능하면 '\(\Sigma\)는 결함이 있다(inconsistent)'라고 말하며, 그렇지 않은 경우 '\(\Sigma\)는 무결하다(consistent)'라고 말한다.

아래 정리에서 명제변수의 개수는 유한 또는 가산인 것으로 가정한다.

정리 1.  명제논리의 건전성과 완전성.

임의로 주어진 논리식의 집합 \(\Sigma\)에 대하여, \(\Sigma\)가 무결할 필요충분조건은 값매김 \(v\)가 존재하여 임의의 \(\sigma \in \Sigma\)에 대하여 \(v(\sigma )= \mathrm{T}\)를 만족시키는 것이다.

정리 1에 의하여 다음을 얻는다.

따름정리 2. \(\Sigma\)가 논리식의 집합이고 \(\sigma\)가 논리식일 때, \(\sigma\)가 \(\Sigma\)의 논리적 귀결일 필요충분조건은 \(\sigma\)가 \(\Sigma\)로부터 추론 가능한 것이다.

따름정리 3. 논리식이 항진일 필요충분조건은 정리인 것이다.

이제 건전성 정리와 완전성 정리의 증명을 살펴보자.

건전성 정리의 증명. 공리는 모두 항진이며, 추론규칙 MP는 진릿값을 보존한다. [즉 \(v(\phi) = \mathrm{T}\)이고 \(v( (\phi \to \psi )) = \mathrm{T} \)이면 \(v(\psi ) = \mathrm{T}\)이다.] 이 사실은 진리표를 이용하면 쉽게 증명된다.

이제 증명 길이에 대한 수학적 귀납법을 이용하여 \(\phi\)가 정리이면 \(\phi\)가 항진임을 증명하자. 먼저 공리는 항진이므로 \(\phi\)가 한 줄 짜리 증명을 가질 때 \(\phi\)는 항진이다. 다음으로 MP가 진릿값을 보존하므로 \(2\) 이상인 자연수 \(n\)에 대하여 증명 길이가 \(n\) 미만인 임의의 정리가 항진이면 증명 길이가 \(n\)인 정리도 항진이다.

일반화하면, 만약 \(\phi\)가 \(\Sigma\)로부터 증명 가능하면 \(\Sigma\)에 속하는 모든 논리식에 \(\mathrm{T}\)의 값을 매기는 값매김은 \(\phi\)에도 \(\mathrm{T}\)의 값을 매긴다. 특히 \(\Sigma\)에 속하는 모든 논리식에 \(\mathrm{T}\)의 값을 매기는 값매김이 존재하면 \(\Sigma\)는 무결하다. 왜냐하면 \(\psi\)와 \( (\neg \psi )\) 모두에게 \(\mathrm{T}\)의 값을 매기는 값매김은 존재하지 않기 때문이다. 이로써 건전성 정리가 증명되었다.

완전성 정리의 증명. 먼저 \(\Sigma\)가 무결할 때 임의의 논리식 \(\phi\)에 대하여 \(\Sigma \cup \left\{\phi\right\}\)와 \(\Sigma \cup \left\{ (\neg \phi )\right\}\) 중 하나는 무결함을 보이자. 이것을 보이기 위하여 결론을 부정하자. 그러면 \(\Sigma \cup \left\{\phi\right\}\)와 \(\Sigma \cup \left\{ (\neg \phi )\right\}\)로부터 모순 \(\kappa\)가 추론되며 \( (\phi \to \kappa )\)와 \( (( \neg \phi ) \to \kappa )\)가 모두 \(\Sigma\)로부터 추론된다. 그런데 \[ (( \phi \to \kappa ) \to ((( \neg \phi ) \to \kappa ) \to \kappa ))\] 가 명제논리의 정리이므로 \(\kappa\)가 \(\Sigma\)로부터 추론된다. 이것은 모순이다.

모든 논리식들의 집합이 가산이므로 \(\Sigma\)는 다음과 같은 과정을 통해 무결한 극대 집합 \(\Sigma ^+ \)로 확장될 수 있다: 논리식들 \(\phi_0 ,\) \(\phi_1 ,\) \(\phi_2 ,\) \(\cdots\)을 나열한다. 그리고 처음에 \(\Sigma ^+\)를 공집합으로 시작하여, 각 \(n\)째 단계에서 \(\Sigma ^+ \cup \left\{\phi _n \right\}\)이 무결하면 \(\phi_n\)을 \(\Sigma ^+\)에 추가하고, 그렇지 않으면 \( (\neg \phi _n )\)을 \(\Sigma ^+\)에 추가한다. 그러면 각 \(n\)에 대하여 \(\phi_n \)과 \( (\neg \phi_n )\) 중 하나는 \(\Sigma ^+\)에 속하게 되며, 둘 중 하나만 속하게 된다.

이제 값매김 함수 \(v\)를 다음과 같이 정의한다. \[v( p _i ) := \begin{cases} \mathrm{T} \quad &\mbox{if} \,\, p _i \in \Sigma ^+ \\ \\ \mathrm{F} \quad &\mbox{if} \,\, p _i \notin \Sigma^+ \end{cases} \] \(\phi\)의 증명 길이에 대한 수학적 귀납법을 이용하여 \( v(\phi ) = \mathrm{T}\)일 필요충분조건이 \(\phi \in \Sigma ^+ \)임을 보이자. \(v\)의 정의에 의하여 각 논리식 \(p_i\)에 대해서는 자명하게 \( v(p_i ) = \mathrm{T}\)일 필요충분조건이 \( p_i \in \Sigma ^+ \)가 된다. 이제 \(\phi\)가 둘 이상의 기호를 포함하고 있다고 하자. 그러면 다음과 같이 두 가지 경우로 나누어 생각할 수 있다.

\(\phi\)가 \( (\neg \psi )\)인 경우 \[ v( \phi ) = \mathrm{T} \quad \Leftrightarrow \quad v(\psi ) = \mathrm{F} \quad \Leftrightarrow \quad \psi \notin \Sigma ^+ \quad \Leftrightarrow \quad \phi \in \Sigma ^+ \] 가 성립한다 여기서 두 번째 필요충분조건 관계는 귀납적 가정에 의하여 성립한다.

\(\phi\)가 \( (\psi \to \theta )\)인 경우 \[ \begin{eqnarray} v(\phi ) = \mathrm{T} \quad & \Leftrightarrow & \quad v(\psi ) = \mathrm{F} \,\, \mathrm{o r} \,\, v(\theta ) = \mathrm{T} \\[5pt] & \Leftrightarrow & \quad \psi \notin \Sigma ^+ \,\, \mathrm{o r} \,\, \theta \in \Sigma ^+ \\[5pt] & \Leftrightarrow & \quad ( \neg \psi ) \in \Sigma ^+ \,\, \mathrm{o r} \,\, \theta \in \Sigma ^+ \end{eqnarray} \] 이다. \(v(\phi ) = \mathrm{T} \)이고 \(\phi \notin \Sigma ^+\)라고 가정하자. 그러면 \( (\neg \phi ) \in \Sigma ^+ \)이다. 두 식 \[ (( \neg \psi ) \to ( \psi \to \theta )), \] \[ ( \theta \to ( \psi \to \theta )) \] 가 모두 명제논리의 정리이므로 \(\phi\)와 \( (\neg \phi )\)가 모두 \(\Sigma ^+\)로부터 추론될 수 있으며 \(\Sigma ^+\)는 결함이 있다. 즉 \(v(\phi ) = \mathrm{T} \)이고 \(\phi \notin \Sigma ^+\)인 경우는 존재하지 않는다. 한편 \(v(\phi ) = \mathrm{F}\)이고 \(\phi \in \Sigma ^+ \)라고 가정하자. 그러면 \(\psi \in \Sigma^+ , \) \( (\neg \theta ) \in \Sigma ^+ \)이다. 그런데 \[ ( \psi \to (( \neg \theta ) \to ( \neg ( \psi \to \theta )))) \] 가 명제논리의 정리이므로 \(\phi\)와 \( (\neg \phi )\)가 모두 \(\Sigma ^+\)로부터 추론될 수 있으며 \(\Sigma ^+\)는 결함이 있다. 즉 \(v(\phi ) = \mathrm{F}\)이고 \(\phi \in \Sigma ^+ \)인 경우는 존재하지 않는다. 그러므로 결국 \[ v(\phi ) = \mathrm{T} \quad \Leftrightarrow \quad ( \phi \in \Sigma ^+ ) \] 가 성립한다. 그러므로 증명 길이에 대한 수학적 귀납법에 의하여 \( v(\phi ) = \mathrm{T}\)일 필요충분조건이 \(\phi \in \Sigma ^+ \)임이 증명되었다.

\(\Sigma \subseteq \Sigma ^+\)이므로 \(\Sigma\)에 속하는 모든 논리식이 참이 되도록 하는 값매김 \(v\)를 구성하였다. 이로써 완전성 정리가 증명되었다.

따름정리의 증명. 건전성 정리의 경우 정리 1로부터 따름정리 2와 따름정리 3이 증명됨은 자명하다. 그러므로 완전성 정리에 대해서만 증명하면 된다.

\(\phi\)가 \(\Sigma\)의 논리적 귀결이라고 하자. 그러면 \(\Sigma \cup \left\{ (\neg \phi )\right\}\)에 속하는 모든 논리식이 참이 되도록 하는 값매김은 존재하지 않으므로, 이 집합으로부터 \(\psi\)와 \( ( \neg \psi )\) 모두를 증명하는 것이 가능하도록 하는 논리식 \(\psi\)는 존재하지 않는다. \(\kappa\)가 \(\psi\) 또는 \( (\neg \psi )\) 둘 중 하나일 때 추론 정리에 의하여 \(\Sigma\)로부터 \( (( \neg \phi ) \to \kappa ) \)를 증명하는 것이 가능하다. 이 사실과 명제논리의 정리 \[ ((( \neg \phi ) \to \psi ) \to ((( \neg \phi ) \to (\neg \psi )) \to \phi ))\] 를 이용하면 \(\Sigma\)로부터 \(\phi\)가 증명된다.

만약 논리식 \(\phi\)의 증명을 찾기 위하여 노력하였지만 실패하였다면 \(\phi\)는 명제논리의 정리가 아니라고 할 수 있을까? 그렇지 않다. 비록 증명을 찾지는 못하였지만 아직 알아내지 못한 증명이 존재할 수 있기 때문이다. 이러한 상황에서 건전성 정리와 완전성 정리는 주어진 논리식이 정리인지 아닌지를 판별하는 또다른 방법을 제공한다.

\(\phi\)가 유한 개의 명제변수를 이용하여 구성된 논리식이라고 하자. 명제변수에 진릿값을 배정할 수 있는 모든 경우를 고려하여 \(\phi\)의 진리표를 만들고 \(\phi\)의 진릿값을 살펴보았을 때 모든 경우에 \(\mathrm{T}\)가 나오면 \(\phi\)는 명제논리의 정리이며, \(\mathrm{F}\)인 경우가 하나라도 있다면 \(\phi\)는 명제논리의 정리가 아니다.

명제논리의 긴밀성

명제논리의 형식계(구문론적 관점)가 진리표(의미론적 관점)와 같은 정보를 제공하는 반면 다루기는 어렵기 때문에, 명제논리의 형식계는 불필요한 것으로 생각될 수도 있다. 그러나 다음에 살펴볼 명제논리의 긴밀성(compactness)을 증명할 때 명제논리의 건전성과 완전성은 대단히 중요한 역할을 한다.

\(\Sigma\)가 논리식의 집합이라고 하자. 만약 값매김 함수 \(v\)가 존재하여 임의의 \(\sigma \in \Sigma\)에 대하여 \( v( \sigma ) = \mathrm{T}\)를 만족시키면 '\(\Sigma\)는 만족될 수 있다(satisfiable)'라고 말한다. ['만족될 수 있다'를 '만족 가능하다'라고 표현하기도 한다.]

정리 4.  명제논리의 긴밀성.

\(\Sigma\)가 논리식의 집합이라고 하자. 만약 \(\Sigma\)의 임의의 유한부분집합이 만족될 수 있으면 \(\Sigma\)도 만족될 수 있다.

증명. 정리 1에 의하면 \(\Sigma\)가 만족될 수 있을 필요충분조건은 \(\Sigma\)로부터 모순이 추론되지 않는 것이다. 그런데 모순이 추론된다는 것은 논리식의 유한열로 이루어진 증명이 존재한다는 것을 뜻한다. 한편 논리식의 유한열은 \(\Sigma\)의 유한부분집합의 원소로 이루어지므로 모순의 증명은 존재하지 않는다. 그러므로 \(\Sigma\)는 만족될 수 있다.

명제논리의 긴밀성을 응용하여 문제를 해결하는 예를 살펴보자. 명제논리의 긴밀성을 이용하면 유한평면지도의 4색 정리로부터 무한평면지도의 4색 정리를 이끌어낼 수 있다.

평면지도(plane map)는 고정된 수의 국가(country)로 이루어져 있는데, 각 국가는 경계가 단순닫힌곡선인 단순연결영역이며, 임의의 서로 다른 두 국가는 겹치지 않거나 겹친다면 경계만 공유한다. 여기서 '고정된 수'는 집합의 기수(cardinal number)를 의미하며, 유한일 수도 있고 무한일 수도 있다. 국가의 수가 유한인 평면지도를 유한평면지도라고 부르고, 국가의 수가 무한인 평면지도를 무한평면지도라고 부른다. 평면지도에서 서로 다른 두 국가가 인접해있다는 것은 두 국가의 폐포의 경계가 겹치며, 겹치는 부분이 길이가 양수인 곡선을 포함하는 것이다. 지도의 채색(coloring)이란 국가의 집합으로부터 색의 집합(set of colors)으로의 대응인데, 인접해 있는 서로 다른 임의의 두 국가가 서로 다른 색으로 대응되는 것이다.

1976년 Kenneth Appel과 Wolfgang Haken은 고성능 컴퓨터의 도움을 받아 약 2,000 시간의 계산을 통해 모든 경우의 수를 검토함으로써 임의의 유한평면지도를 채색하는 데에 4가지 색이면 충분하다는 사실을 증명하였다. 이 정리를 '4색 정리(four-color theorem)'라고 부른다. 여기서는 증명은 소개하지 않고 정리의 내용만 소개한다.

정리 5.  유한평면지도의 4색 정리.

임의의 유한평면지도를 채색하는 데에는 4가지 색이면 충분하다.

명제논리의 긴밀성 정리를 이용하여, 이 정리가 무한평면지도에 대해서도 성립함을 보이자.

정리 6.  평면지도의 4색 정리.

임의의 평면지도를 채색하는 데에는 4가지 색이면 충분하다.

증명. 평면지도에서 유한 개의 지도를 포함하는 영역을 확장하는 방식으로 증명이 진행될 것이라고 생각할 수도 있지만, 그러한 방법으로는 증명이 되지 않는다. 증명은 한 점으로부터 시작한다. [이것이 바로 유한평면지도의 4색 정리를 증명하는 것이 어려운 이유이다.]

임의의 무한평면지도가 주어졌다고 하자. \(\mathbb{R} ^2\)는 가분공간(separable space)이므로 조밀한 가산부분집합 \(D\)가 존재하며, 임의의 국가는 내부에 \(D\)의 원소를 하나 이상 가지므로 모든 국가의 집합은 가산집합이다. 그러므로 모든 국가의 집합을 \(\mathcal{C} = \left\{ C_n \, | \, n \in \mathbb{N} \right\}\)으로 나타낼 수 있다.

가산 개의 명제변수의 집합 \(\left\{ p_{n,k} \, | \, n \in \mathbb{N} ,\, k = 0,\,1,\,2,\,3 \right\}\)을 생각하자. 이제 \(\Sigma\)가 다음과 같은 논리식들로 구성된 집합이라고 하자.

  • 각 \(n \in \mathbb{N}\)에 대하여 \[ (( p_{n,0} \vee p_{n,1} \vee p_{n,2} \vee p_{n,3} ) \wedge (( \neg ( p_{n,0} \wedge p_{n,1} )) \wedge \cdots \wedge (\neg (p_{n,2} \wedge p_{n,3} )))) . \tag{a} \] 이 논리식은 \(p_{n,0} ,\) \(p_{n,1} ,\) \(p_{n,2} ,\) \(p_{n,3}\) 중 딱 하나가 참일 때 참이다. [이 논리식에서는 편의를 위하여 괄호가 생략되었다. 명제곱의 결합법칙과 명제합의 결합법칙에 의하여 괄호를 생략하여도 의미가 변하지 않는다.]
  • 인접하고 서로 다른 두 국가로 이루어진 임의의 쌍 \(( C_n ,\, C_m )\)과 각 \(k \in \left\{ 0 ,\, 1 ,\, 2 ,\, 3 \right\}\)에 대하여 \[ ( \neg ( p_{n,k} \wedge p_{m,k} )) . \tag{b} \]

이제 \(\Sigma\)를 만족시키는 값매김 함수 \(v\)가 주어졌다고 하자. \(v ( p_{n,k} ) = \mathrm{T} \)일 때 \(C_n\)에 색 \(k\)를 대응시키면 이러한 대응은 \(\mathcal{C}\)의 채색이 된다. 왜냐하면 (a)에 의하여 \(C_n\)은 하나의 색에만 대응되며, (b)에 의하여 인접한 두 국가는 다른 색에 대응되기 때문이다.

다음으로 \(\Sigma\)의 임의의 유한부분집합 \(\Sigma_0\)이 만족될 수 있음을 보이자. \(\Sigma_0\)에 속하는 논리식에서 사용된 명제변수 \(p_{n,k}\)들에 대응되는 국가 \(C_n\)의 수가 유한이므로, 이들 국가들로 이루어진 평면지도는 유한평면지도이며, 유한평면지도의 4색 정리에 의하여 이 지도는 4가지 색으로 채색 가능하다. 그러므로 \(p_{n,k}\)에 진릿값을 대응시켜 \(\Sigma_0\)이 만족되도록 할 수 있다.

끝으로 명제논리의 긴밀성 정리에 의하여 \(\Sigma\)는 만족될 수 있다. 따라서 주어진 무한평면지도는 4가지 색으로 채색될 수 있다.

명제변수의 개수가 더 많은 경우

정리 1에서 살펴본 명제논리의 건전성과 완전성은 명제변수의 개수가 유한이거나 가산인 경우만 다루었다. 그러나 사실 명제변수의 개수가 더 많을 때에도 명제논리는 건전성과 완전성을 가진다.

정리 7. 명제논리의 변수의 집합이 정렬집합일 때 명제논리는 건전성과 완전성을 가진다.

증명. 논리식은 명제변수와 유한 개의 결합자와 괄호로 이루어진 알파벳으로부터 선택된 기호들로 이루어져 있으며 길이가 유한인 문자열이다. 명제변수들의 집합이 정렬집합이면 알파벳의 집합 전체도 정렬집합이므로 문자열들의 집합도 정렬집합이며 그 부분집합인 논리식들의 집합도 정렬집합이다.

이제 정리 1을 증명할 때와 같은 방법으로 증명을 이어간다. 단, 무결한 극대 집합 \(\Sigma ^+\)를 구성하는 과정이 다르다. 초한 귀납법(transfinite induction)을 이용하여 \(\Sigma ^+\)를 구성하자. 적당한 서수 \(\beta\)에 대하여 \( (\phi_{\alpha} \,|\, \alpha < \beta )\)로서 논리식들의 집합에 정렬을 부여한다. 이제 초한 귀납법을 다음과 같이 적용하여 \(\Sigma ^+\)를 구성한다.

  • 단계 1.  \(\Sigma_{\alpha} := \Sigma\)로 둔다.
  • 단계 2.  주어진 \(\Sigma_{\alpha}\)에 대하여, \(\Sigma_{\alpha} \cup \left\{\phi_{\alpha} \right\}\)와 \(\Sigma_{\alpha} \cup \left\{ ( \neg \phi_{\alpha} ) \right\}\) 중 무결한 것을 \(\Sigma_{s(\alpha )}\)로 둔다.
  • 단계 3.  \(\alpha\)가 극서수(limit ordinal)일 때 \[\Sigma_{\alpha} := \bigcup_{\gamma < \alpha} \Sigma_{\gamma}\] 로 둔다.

\(\Sigma ^+ := \Sigma_{s(\beta )}\)로 두면 \(\Sigma ^+\)는 우리가 원하는 성질을 갖는 집합이 된다.

완전성의 증명은 지금까지의 증명에서 초한 귀납법 적용 3단계를 제외한 부분이 같다. 대신, 3단계는 다음과 같다: 만약 적당한 극서수 \(\alpha\)가 존재하여 \(\Sigma_{\alpha}\)로부터 모순이 추론된다고 가정하면, 이 모순의 증명은 유한 개의 논리식들로 이루어진 열이므로 적당한 \(\gamma < \alpha\)가 존재하여 그러한 논리식들이 모두 \(\Sigma_{\gamma}\) 안에 놓이게 된다.

이어서 \(\Sigma ^+\)를 구성하고, 정리 1의 증명 방법을 그대로 사용하면 완전성이 증명된다.

정리 7의 결과에 정리 4의 증명 방법을 적용하면 다음을 얻는다.

정리 8. 명제논리의 변수의 집합이 정렬집합일 때 명제논리는 긴밀성을 가진다.

ZFC에서는 Zermelo의 정렬 정리에 의하여 임의의 집합이 정렬 가능하다. 따라서 다음을 얻는다.

정리 9. ZFC에서 임의 개수의 명제변수가 주어졌을 때 명제논리는 긴밀성을 가진다.

사실 ZF에서 임의 개수의 명제변수에 대한 명제논리의 긴밀성은 선택 공리의 결과이다. 그러나 명제논리의 긴밀성은 선택 공리보다 약하다는 사실이 알려져 있다. 즉 ZF에서 명제논리의 긴밀성을 가정하더라도 선택 공리는 증명되지 않는다.

Leave a Reply