명제논리에는 서로 다른 두 관점이 있다. 구문론적 관점에서는 공리와 추론규칙을 사용하여 무엇을 증명할 수 있는지를 묻고, 의미론적 관점에서는 값매김에 의하여 어떤 논리식이 참이 되는지를 묻는다. 건전성과 완전성은 이 두 관점이 정확히 일치한다는 사실을 나타낸다.
1. 건전성 정리와 완전성 정리
건전성(soundness)은 \[ \varSigma\vdash\phi\quad\Longrightarrow\quad\varSigma\models\phi \] 가 성립하는 성질을 말한다. 즉, 형식적으로 증명 가능한 결론은 의미론적으로도 가정의 논리적 귀결이다.
완전성(completeness)은 그 역인 \[ \varSigma\models\phi\quad\Longrightarrow\quad\varSigma\vdash\phi \] 가 성립하는 성질을 말한다.
정의 13.1. (무모순성)
논리식의 집합 \(\varSigma\)에 대하여 어떤 논리식 \(\psi\)도 \[ \varSigma\vdash\psi, \quad \varSigma\vdash\neg\psi \] 를 동시에 만족시키지 않으면 \(\varSigma\)가 무모순(consistent)이라고 한다. 그렇지 않으면 모순적(inconsistent)이라고 한다.
정리 13.2. (건전성 정리)
임의의 논리식 집합 \(\varSigma\)와 논리식 \(\phi\)에 대하여 \[ \varSigma\vdash\phi \quad\Longrightarrow\quad \varSigma\models\phi \] 이다.
증명 \(\varSigma\)의 모든 논리식을 참으로 만드는 값매김 \(v\)를 하나 고정시키고, \(\varSigma\)로부터의 증명 길이에 대하여 수학적 귀납법을 사용한다. 공리 (A1)–(A3)은 진리표로 직접 확인하면 모두 항진이다. 가정은 \(v\)의 선택에 의하여 참이다. 또한 MP는 진릿값을 보존한다. 실제로 \(v(\chi)=\mathrm T\)이고 \(v(\chi\to\eta)=\mathrm T\)이면 함의의 진리표에 의하여 \(v(\eta)=\mathrm T\)이다. 따라서 증명의 모든 논리식이 \(v\)에서 참이고, 특히 마지막 논리식 \(\phi\)도 참이다.
따라서 만족 가능한 논리식 집합은 무모순이다. 실제로 \(\varSigma\)의 모형이 있는데 \(\varSigma\vdash\psi\)와 \(\varSigma\vdash\neg\psi\)가 동시에 성립하면 건전성 정리에 의하여 같은 값매김에서 \(\psi\)와 \(\neg\psi\)가 모두 참이어야 하므로 모순이다.
완전성을 증명하려면 무모순 집합으로부터 모형을 만들어야 한다. 다음 보조정리가 그 핵심이다.
보조정리 13.3. (극대 무모순 확장)
모든 무모순 논리식 집합 \(\varSigma\)는 자신을 포함하는 극대 무모순 집합 \(\Gamma\)를 가진다.
증명 개요 이 장의 명제변수는 가산 개이므로 모든 논리식도 가산 개이다. 이를 \[ \phi_0,\phi_1,\phi_2,\ldots \] 와 같이 나열한다.
정리 12.2의 추론 정리와 (A1)–(A3)으로부터 다음 사실을 얻을 수 있다. \[ \Delta\cup\{\chi\}\text{가 모순적} \quad\Longleftrightarrow\quad \Delta\vdash\neg\chi. \] 왼쪽에서 오른쪽 방향은 추론 정리와 공리계에서 유도되는 귀류법 \[ (\chi\to\theta)\to((\chi\to\neg\theta)\to\neg\chi) \] 을 사용한다. 오른쪽에서 왼쪽 방향은 \(\chi\)와 \(\neg\chi\)를 동시에 얻을 수 있으므로 즉시 따른다. 또한 이 공리계에서는 이중부정 제거 \[ \vdash\neg\neg\chi\to\chi \] 도 유도된다.
\(\Gamma_0=\varSigma\)로 두고, \(\Gamma_n\)이 정해졌을 때 \[ \Gamma_{n+1}= \begin{cases} \Gamma_n\cup\{\phi_n\} & (\Gamma_n\cup\{\phi_n\}\text{이 무모순일 때}),\\[5pt] \Gamma_n\cup\{\neg\phi_n\} & (\text{그렇지 않을 때}) \end{cases} \] 로 정의한다. 두 번째 경우에도 무모순성이 유지된다. 만약 \(\phi_n\)과 \(\neg\phi_n\)을 각각 더한 두 집합이 모두 모순적이면 위의 동치에 의하여 \(\Gamma_n\vdash\neg\phi_n\)와 \(\Gamma_n\vdash\neg\neg\phi_n\)을 동시에 얻고, 이중부정 제거에 의하여 \(\Gamma_n\) 자체가 모순적이 되기 때문이다.
이제 \[ \Gamma=\bigcup_{n\in\mathbb N}\Gamma_n \] 로 둔다. \(\Gamma\)에서 모순이 증명된다면 그 두 유한한 증명에 사용된 가정들은 어떤 하나의 \(\Gamma_N\)에 모두 들어가므로 \(\Gamma_N\)이 모순적이 되어 모순이다. 따라서 \(\Gamma\)는 무모순이다. 구성상 모든 논리식 \(\phi\)에 대하여 \(\phi\)와 \(\neg\phi\) 중 정확히 하나가 \(\Gamma\)에 속하므로 \(\Gamma\)는 극대 무모순이다.
보조정리 13.4. (진리 보조정리)
\(\Gamma\)가 극대 무모순 집합이면 \(\Gamma\)의 모든 논리식을 참으로 만드는 값매김이 존재한다.
증명 명제변수에 대하여 \[ v(p_i)=\mathrm T \quad\Longleftrightarrow\quad p_i\in\Gamma \] 라고 정의하고, 이를 모든 논리식으로 재귀적으로 확장한다.
극대 무모순성으로부터 임의의 \(\chi\)에 대하여 \(\chi\)와 \(\neg\chi\) 중 정확히 하나가 \(\Gamma\)에 속한다. 또한 \(\Gamma\vdash\chi\)이면 \(\chi\in\Gamma\)이다. 실제로 \(\chi\notin\Gamma\)이면 \(\neg\chi\in\Gamma\)이므로 \(\Gamma\)가 모순적이 된다.
따라서 MP에 대한 닫힘과 앞에서 증명한 \[ \vdash\neg\phi\to(\phi\to\psi) \] 및 (A1)을 이용하면 \[ (\phi\to\psi)\in\Gamma \quad\Longleftrightarrow\quad \phi\notin\Gamma\text{ 또는 }\psi\in\Gamma \] 를 얻는다. 이제 논리식의 구성에 대한 귀납법을 사용하여 \[ v(\chi)=\mathrm T \quad\Longleftrightarrow\quad \chi\in\Gamma \] 를 증명할 수 있다. 특히 \(\varSigma\subseteq\Gamma\)이면 \(v\)는 \(\varSigma\)의 모형이다.
정리 13.5. (무모순성과 만족 가능성)
논리식 집합 \(\varSigma\)가 무모순일 필요충분조건은 \(\varSigma\)가 만족 가능한 것이다.
증명 만족 가능하면 건전성 정리에 의하여 무모순이다. 반대로 무모순이면 보조정리 13.3에 의하여 극대 무모순 확장 \(\Gamma\)를 얻고, 보조정리 13.4에 의하여 \(\Gamma\), 따라서 \(\varSigma\)의 모형을 얻는다.
문제 13.1. 다음 논리식 집합이 만족 가능한지 판정하시오. 만족 가능하면 모형을 하나 제시하고, 만족 가능하지 않으면 그 이유를 설명하시오. 정리 13.5에 의하여 각 집합이 무모순인지도 함께 판정하시오.
- \(\Gamma_1=\{p,p\to q,\neg q\}\).
- \(\Gamma_2=\{p\to q,\neg p\}\).
- \(\Gamma_3=\{p\vee q,\neg p,\neg q\}\).
정리 13.6. (완전성 정리)
임의의 논리식 집합 \(\varSigma\)와 논리식 \(\phi\)에 대하여 \[ \varSigma\models\phi \quad\Longrightarrow\quad \varSigma\vdash\phi \] 이다.
증명 대우를 보인다. \(\varSigma\nvdash\phi\)라고 하자. 만약 \(\varSigma\cup\{\neg\phi\}\)가 모순적이면 보조정리 13.3의 증명에서 사용한 동치에 의하여 \(\varSigma\vdash\neg\neg\phi\)이고, 이중부정 제거에 의하여 \(\varSigma\vdash\phi\)가 되어 모순이다. 따라서 \(\varSigma\cup\{\neg\phi\}\)는 무모순이고, 정리 13.5에 의하여 이 집합의 모형 \(v\)가 존재한다. 그러면 \(v\)는 \(\varSigma\)의 모든 논리식을 참으로 만들지만 \(v(\phi)=\mathrm F\)이므로 \(\varSigma\not\models\phi\)이다.
명제논리의 건전성과 완전성을 결합하면 다음을 얻는다. \[ \varSigma\models\phi \quad\Longleftrightarrow\quad \varSigma\vdash\phi \] 특히 논리식 \(\phi\)가 항진일 필요충분조건은 \(\vdash\phi\)인 것이다.
문제 13.2. 건전성과 완전성을 이용하여 다음을 보이시오.
- \(\vdash p\to p\)라는 사실만으로 \(p\to p\)가 항진임을 결론낼 수 있는 이유를 설명하시오.
- 진리표로 \((p\wedge q)\to p\)가 항진임을 확인하고, 완전성 정리를 사용하여 \[ \vdash (p\wedge q)\to p \] 임을 결론내리시오.
- \(\varSigma\nvdash\phi\)이면 \(\varSigma\)의 모든 논리식을 참으로 만들면서 \(\phi\)를 거짓으로 만드는 값매김이 존재함을 설명하시오.
문제 13.3. 형식계의 무모순성에 대하여 다음을 답하시오.
- MU-계에는 부정기호가 없다. 따라서 정의 13.1을 그대로 적용할 수 없다. 이 경우 형식계가 비자명하다는 조건을 어떻게 정의할 수 있는지 설명하시오.
- 모든 논리식이 정리가 되는 형식계는 부정기호가 있는 경우 무모순일 수 있는가?
- 공리가 없는 형식계가 반드시 무모순인지 논하시오. 여기서는 전제가 0개인 추론규칙도 허용한다고 하자.
2. 명제논리의 콤팩트성
정리 13.7. (명제논리의 콤팩트성)
논리식의 집합 \(\varSigma\)에 대하여 다음 두 조건은 동치이다.
- \(\varSigma\)는 만족 가능하다.
- \(\varSigma\)의 모든 유한부분집합은 만족 가능하다.
증명 (1)에서 (2)는 자명하다. 반대로 \(\varSigma\)의 모든 유한부분집합이 만족 가능하다고 하자. 만약 \(\varSigma\)가 만족 가능하지 않으면 정리 13.5에 의하여 \(\varSigma\)는 모순적이다. 따라서 어떤 \(\psi\)에 대하여 \(\varSigma\vdash\psi\)와 \(\varSigma\vdash\neg\psi\)인 두 유한한 증명이 존재한다. 이 두 증명에서 실제로 사용된 가정은 유한 개뿐이므로, 그 가정들을 모두 포함하는 유한부분집합 \(\varSigma_0\subseteq\varSigma\)가 존재하여 \(\varSigma_0\)도 모순적이다. 건전성 정리에 의하여 \(\varSigma_0\)는 만족 가능하지 않다. 이는 가정에 모순이다.
따라서 의미론적 귀결도 유한한 부분에 의하여 결정된다. 즉, \[ \varSigma\models\phi \] 이면 어떤 유한부분집합 \(\varSigma_0\subseteq\varSigma\)가 존재하여 \(\varSigma_0\models\phi\)이다.
문제 13.4. \[ \varSigma=\left\{p_0\right\}\cup\{p_n\to p_{n+1}\mid n\in\mathbb N\} \] 이라고 하자.
- 임의의 \(k\in\mathbb N\)에 대하여 \(\varSigma\models p_k\)임을 보이시오.
- 주어진 \(k\)에 대하여 \(p_k\)를 논리적 귀결로 가지는 유한부분집합 \(\varSigma_k\subseteq\varSigma\)를 하나 구체적으로 제시하시오.
- 특히 \(p_5\)에 대하여 필요한 가정만을 모두 쓰시오. 이 예가 위의 유한성 결론과 어떻게 연결되는지 설명하시오.
3. 콤팩트성의 응용: 사색 정리의 가산 무한 확장
다음은 유한 평면그래프에 대한 사색 정리이다.
정리 13.8. (유한 평면그래프의 사색 정리)
모든 유한 평면그래프의 꼭짓점은 인접한 두 꼭짓점이 서로 다른 색을 갖도록 네 가지 색으로 칠할 수 있다.
이 정리는 1976년에 아펠과 하켄이 컴퓨터의 도움을 받아 처음 증명하였다. 여기서는 이 결과 자체는 증명 없이 사용하고, 명제논리의 콤팩트성을 사용하여 다음과 같이 확장된 정리를 얻는다.
정리 13.9. (가산 평면그래프의 사색 정리)
꼭짓점 집합이 가산인 모든 평면그래프는 네 가지 색으로 올바르게 꼭짓점 채색할 수 있다.
증명 평면그래프를 \(G=(V,E)\)라 하자. \(V\)가 가산이므로 각 \(a\in V\)와 색 \(c\in\{1,2,3,4\}\)에 명제변수 \(p_{a,c}\)를 대응시킬 수 있다. \(p_{a,c}\)는 “꼭짓점 \(a\)의 색이 \(c\)이다”라는 뜻으로 생각한다.
다음 논리식들을 모아 집합 \(\varSigma\)를 만든다.
- 각 \(a\in V\)에 대하여 \[ p_{a,1}\vee p_{a,2}\vee p_{a,3}\vee p_{a,4}; \]
- 각 \(a\in V\)와 \(1\le c<d\le4\)에 대하여 \[ \neg(p_{a,c}\wedge p_{a,d}); \]
- 각 변 \(\{a,b\}\in E\)와 \(c\in\{1,2,3,4\}\)에 대하여 \[ \neg(p_{a,c}\wedge p_{b,c}). \]
첫 번째와 두 번째 종류의 논리식은 각 꼭짓점이 정확히 하나의 색을 갖도록 하고, 세 번째 종류는 인접한 두 꼭짓점의 색이 다르도록 한다.
\(\varSigma\)의 유한부분집합 \(\Delta\)를 하나 잡자. \(\Delta\)에는 유한 개의 꼭짓점만 등장한다. 이 꼭짓점들이 만드는 유한 부분그래프는 평면그래프이므로 정리 13.8에 의하여 4색 채색이 가능하다. 그 채색에 맞추어 값매김을 정하면 \(\Delta\)의 모든 논리식이 참이 된다. 따라서 \(\varSigma\)의 모든 유한부분집합이 만족 가능하다.
콤팩트성 정리에 의하여 \(\varSigma\) 자체가 만족 가능하다. 그 모형에서 각 꼭짓점에 참인 유일한 \(p_{a,c}\)의 색 \(c\)를 부여하면 \(G\)의 4색 채색을 얻는다.
이 장에서는 명제변수를 가산 개만 사용했으므로 위 정리도 가산 평면그래프로 서술하였다. 임의의 크기의 명제변수 집합에 대해 콤팩트성 정리를 일반화하면 같은 논증을 사용하여 임의의 평면그래프에 대한 명제를 얻을 수 있다.
문제 13.5. 꼭짓점이 \(a,b,c\)이고 세 꼭짓점이 서로 모두 인접한 삼각형 그래프를 생각하자. 색은 \(1,2,3\) 세 가지를 사용하고, \(p_{x,i}\)는 “꼭짓점 \(x\)의 색이 \(i\)이다”라는 뜻으로 하자.
- 각 꼭짓점이 적어도 한 색을 갖는다는 조건을 세 논리식으로 쓰시오.
- 각 꼭짓점이 두 색을 동시에 갖지 않는다는 조건과 인접한 두 꼭짓점이 같은 색을 갖지 않는다는 조건을 논리식으로 나타내시오.
- \(a,b,c\)의 색을 각각 \(1,2,3\)으로 정한 채색에 대응하는 값매김을 제시하고, 위 조건을 모두 만족시킴을 확인하시오.
- 색을 \(1,2\) 두 가지만 허용하면 위와 같은 조건들의 집합이 만족 가능하지 않음을 설명하시오.