명제 논리 (3): 타당성, 건전성, 완전성

오늘의 논리학 시리즈는 현대 논리학에 대한 포괄적이고 기초적인 이해를 위한 자료들을 제공합니다.

1. 명제 논리 (1) | (2) | (3) | (4)
2. 1차 양화 논리 (1) | (2) | (3) | (4)
3. (추가 예정)

1.6. 타당성

논리학에서, 명제 집합 \(\Gamma\)의 원소들을 전제로 하여 명제 \(\phi\)를 결론으로 갖는 논증은, 다음과 같은 경우 타당하다고^valid 일컬어진다: \(\Gamma\)의 모든 원소들이 참인 모든 해석 하에서, \(\phi\)가 참. 이 경우를 우리는 다음과 같이 약호하며, 이에 대해 ‘타당하다’라고 말하는 대신 “\(\phi\)가 \(\Gamma\)의 의미론적 귀결^{semantic consequence}이다”, 또는 “\(\Gamma\)가 \(\phi\)를 함축한다^entails”라고 읽을 것이다: \(\Gamma\vDash\phi\). \(\Gamma=\emptyset\)일 때, 즉 \(\emptyset\vDash\phi\)일 때 우리는 이를 다음과 같이 약호하며, “\(\phi\)가 (이 체계에서) 타당하다”, 또는 “\(\phi\)가 동어반복^tautology이다”라고 읽는다: \(\vDash\phi\).

우리는 전제가 단 하나의 원소만을 갖는 의미론적 귀결의 경우를 이미 살펴보았다. (표 1.3)에서 발견한, \(\phi\)가 \(\phi\lor\psi\)를 함축한다는 사실이 바로 그것이다(아래의 (표 1.4)를 보라). 즉 여기에서의 “\(\phi\)가 \(\phi\lor\psi\)를 함축한다” 역시 다음을 의미하고 있었다는 것이다: \(\phi\vDash\phi\lor\psi\) (전제가 단집합^{singleton set}인 경우, 그리고 중의성이 없는 경우 중괄호({, })는 생략하기로 하자). 나아가, (표 1.4)는 전제가 둘 이상인 경우, 즉 전제 집합 \(\{\phi, \psi\}\)가 \(\phi\land\psi\)를 의미론적 귀결로 갖는다는 것을 보여주고 있다.

(표 1.3)과 (표 1.4)는 명제 논리에서 어떤 식의 타당성, 그리고 어떤 논증의 타당성(즉, 의미론적 귀결 여부)을 평가하기 위해 진리표를 사용할 수 있을 것임을 시사한다. 가령, (표 1.5)를 통해 우리는 \(\{p, q\} \vDash (p\lor q)\), \(p \vDash (p\lor q)\), \(q \vDash (p\lor q)\), \(\{p, q\} \vDash (p\lor\neg p)\), \(\vDash (p\lor\neg p)\), 등의 사실을 확인할 수 있다.

그러나 (표 1.5)를 통해 우리가 \(\{p, q\} \vDash r\) 따위를 주장할 수는 없음에 유의하라. 이 표에 한정할 때 \(r\)과 \(p\lor q\)는 항상 같은 값을 가지며, 이에 의해 일견 \(r\)과 \(p\lor q\)가 동치인 양 보이지만, 이 표는 \(r\)에 유관한 모든 해석을 다루고 있지는 않다. 이 표를 확장해 문장들에 대한 모든 해석을 기술할 경우 우리는 다음의 표를 얻는데 (기울여진 숫자는 추가된 부분),

이는 \(r\)과 \(p\lor q\)가 동치가 아니며, \(\{p, q\} \vDash r\) 또한 성립하지 않음을 (\(v(p)=1\), \(v(q)=1\), \(v(r)=0\)인 경우가 있으므로) 보여준다.

하지만 어떤 식들은 이렇게 진리표를 그리기에는 난해할 수 있다. 가령, \(\phi\supset(\neg\phi\supset(\psi\supset\chi))\)은 동어반복인가 아닌가? 애초에 \(\phi, \psi, \chi\)에 대한 모든 해석을 어떻게 표의 형태로 기술할 수 있을지부터가 난감하다. 이런 경우, 우리가 보다 쉽게 사용할 수 있는 방법은 (1.4)에서의 정의를 통해, 어떤 식이 거짓인 경우 모순이 발생한다는 메타 논리적^metalogical 증명을 취하는 것이다. 가령 우리는 다음과 같은 귀류법을 갖고 메타 논리적으로 증명할 수 있다:

1. \(v(\phi\supset(\neg\phi\supset(\psi\supset\chi)))=0\)이라고 하자.
2. \(\supset\)의 정의와 1의 가정에 따를 때, (1) \(v(\phi)=1\)이면서 (2) \(v(\neg\phi\supset(\psi\supset\chi))=0\)이다.
3. \(\supset\)의 정의와 2.(2)에 따를 때, (1) \(v(\neg\phi)=1\)이면서 (2) \(v(\psi\supset\chi)=0\)이다.
4. \(\neg\)의 정의와 3.(1)에 따를 때, \(v(\phi)=0\)이다.
5. 2.(1)과 4에 따르면, \(v(\phi)=1\)이면서 \(v(\phi)=0\)이다.
6. 5는 부조리하다. 따라서 1의 가정은 틀렸다.

1.7. \(Pr\)의 건전성

형식 체계 \(S\)의 건전성을 다음과 같이 정의하자:\[\eqalign{
\text{형식 체계 $S$가 건전하다}\iff S\text{의 모든 적형식 $\phi$에 대해, }\vdash\phi\Rightarrow\vDash\phi
}\tag{1.5}\]
체계의 건전성을 따져보는 것은 중요하다. 만약 어떤 체계가 건전하지 않다면, \(\vdash\phi\)이면서 \(\not\vDash\phi\)인 경우가, 즉 거짓인 명제를 증명 가능한 경우가 생길 것이기 때문이다. 이러한 경우가 허용되는 체계를 올바른 논리 체계로 사용하기는 어려울 것이며, 그렇기에 이 단락에서 우리는 \(Pr\)이 건전성을 갖는지 확인해 볼 것이다.

건전성을 증명하기 위해, 우리는 다음과 같은 증명 방법을 사용할 수 있다. 먼저, \(Pr\)에서 증명 가능한 기본적인 사례들, 즉 (AxPr\(_1\)), (AxPr\(_2\)), (AxPr\(_3\))에서 \(\alpha, \beta, \gamma\)가 어떠한 적형식으로 대치되든, 이로부터 얻은 문장이 동어반복임을 보인다. 그리고 \(Pr\)의 도출 규칙은 (MP) 뿐이었으므로, (MP)가 진리치를 보존한다는 점을 보인다. 다시 말해 모든 적형식 \(\phi, \psi\)에 대해, \(\phi, \phi\supset\psi\)가 모두 참이라면 \(\psi\)가 참임을 보인다.

이러한 증명 방법을 “수학적 귀납법”이라고 부른다. (우리가 학교에서 배운 그거 맞다.) 수학적 귀납법은 관계 \(R\)에 대해 닫혀 있는 어떤 집합 \(\Sigma\)의 모든 원소가 \(\bf\Phi\)라는 성질을 가짐을 보이기 위한 증명법으로, 다음의 두 단계로 이루어진다. 먼저 \(\Sigma\)의 원소들 중 기초 사례^{base case}가 될 수 있는 것들을 떼어 두고, 그것들이 \(\bf\Phi\)임을 보인다. 이어, \(\bf\Phi\)인 원소 \(\sigma\)에 대해 \(R\sigma\tau\)라면 \(\tau\) 또한 \(\bf\Phi\)임을 보인다(귀납 절차^{inductive step}).

다시 건전성의 이야기로 돌아오자. \(Pr\)의 건전성은 이하에 따라 수학적 귀납법으로 증명될 수 있다. \(Pr\)에서 증명 가능한 임의의 적형식 \(\phi, \psi, \chi\)에 대해 다음 각각을 보이자:\[\begin{align}
&\vDash\phi\supset(\psi\supset\phi));\\
&\vDash(\psi\supset(\phi\supset\chi))\supset((\phi\supset\psi)\supset(\phi\supset\chi)); \tag{기초 사례}\\
&\vDash(\neg\psi\supset\neg\phi)\supset((\neg\psi\supset\phi)\supset\psi).\\ \\
&\vDash\phi, \vDash\phi\supset\psi\Rightarrow\vDash\psi\tag{귀납 절차}
\end{align}\]

증명의 개요. 기초 사례들은 모두 \(v\)의 정의를 여러 번 적용하여 참임을 확인할 수 있다. 귀납 절차 또한 \(v\)의 정의를 사용하여 참임을 확인할 수 있다. 따라서, \(Pr\)에서 증명 가능한 식들의 집합 \(\Pi\)의 임의의 원소 \(\pi\)에 대해 \(\vDash\pi\)인 것이므로, \(Pr\)의 모든 적형식 \(\phi\)에 대해 \(\vdash\phi\Rightarrow\vDash\phi\)이다. \(\blacksquare\)

건전성이 증명되었음에 따라, 우리는 \(Pr\)에 대한 다음의 따름정리를 또한 얻는다:\[\eqalign{S\text{의 모든 적형식 $\phi$에 대해, }\not\vDash\phi\Rightarrow\not\vdash\phi}\tag{1.6}\] 즉, \(Pr\)에서 거짓인 문장은 \(Pr\)에서 증명 불가능하다.

1.8. \(Pr\)의 완전성

형식 체계 \(S\)의 완전성을 다음과 같이 정의하자:\[\eqalign{
\text{형식 체계 $S$가 완전하다}
\iff S\text{의 모든 적형식 $\phi$에 대해, }\vDash\phi\Rightarrow\vdash\phi
}\tag{1.7}\]
건전성과 달리 완전성은 형식 체계에게 치명적인 성질은 아니다. 그럼에도 완전성은 유용하고 흥미로운 성질이므로, 체계가 완전한지를 따져보는 것에는 큰 의의가 있다.

건전성과 달리 완전성은 보다 까다로운 증명이 요구된다. 일단은 귀류법적 증명을 취하는데, 귀류법에까지 나아가기 위한 보조적 증명들이 분량을 요한다. 따라서 요구되는 증명을 모두 상술하는 대신, 증명을 위한 대략의 아이디어를 약술하는 데에서 만족하기로 하자.^[1]

대략의 증명 절차는 다음과 같다:
먼저 \(Pr\)의 완전성을 부정하여, 어떤 문장 \(\phi\)에 대해 \(\vDash\phi\)이면서 \(\not\vdash\phi\)라고 가정하자. 한편, 어떤 최대 일관 집합, 즉, 어떠한 원소를 전제로 하더라도 모순이 귀결되지 않으며, 또 모든 적형식(\(\chi\))에 대해 그 적형식 또는 그 부정(\(\neg\chi\))을 원소로 갖는 그런 집합 중 \(\Gamma\)에 있어, 해석 \(\mathcal{I}^*\) 하에서 그 모든 원소가 참이라고 하자. 그런데 완전성을 부정한 처음의 가정에 따를 때, \(\Gamma\)는 \(\phi\) 및 \(\neg\phi\)의 포함에 관한 모순을 낳는다. 따라서 가정이 틀렸다. \(\blacksquare\)

이러한 절차를 통해 완전성이 증명된다면, 마찬가지로 우리는 \(Pr\)에 대한 다음의 따름정리를 얻을 것이다:\[\eqalign{S\text{의 모든 적형식 $\phi$에 대해, }\not\vdash\phi\Rightarrow\not\vDash\phi}\tag{1.8}\] 즉, \(Pr\)에서 증명 불가능한 문장은 \(Pr\)에서 거짓이다.

건전성과 완전성, 그리고 (1.6)과 (1.8)을 통해 우리는 \(Pr\)에서 증명 가능하다는 것과 \(Pr\)에서 참이라는 것이 동치임과, \(Pr\)에서 증명 불가능하다는 것과 \(Pr\)에서 거짓이라는 것이 동치임, 즉 각각에 해당하는 문장들의 집합이 동일함을 보장받는다.

이렇게 우리는 논리학에서의 타당성 개념 및 명제 논리에서 논증의 타당성을 확인하는 방법에 관해 논했고, 이어 \(Pr\)이 갖는 두 성질인 건전성과 완전성을 증명했다. 이제 명제 논리에 관한 형식적인 개설은 끝났다. 이어서는, 1차 양화 논리로 넘어가기 전, 자연어로 구성된 논증을 \(Pr\)의 논증으로 번역한 뒤 이를 평가하는 방법에 관해 이야기해 보자.

각주

1. 보다 상세한, 그럼에도 친절한 증명으로는 §2.9, Logic for Philosophy(Ted Sider 2010)를 참조.