술어논리(7) ㅡ 만족가능성, 논리적 함축, 타당성

 술어논리의 해석의 개념와 관련하여 가장 중요한 개념 세 가지를 살펴봅시다. 이는 술어논리의 첫 시간에도 일부 잠깐 살펴본 것입니다.

$\Gamma$는 문장들의 집합, $\alpha$는 문장이라고 하자.

1. $\Gamma$가 만족가능하다는 말은 $\Gamma$ 안에 있는 모든 문장들을 참으로 만드는 해석이 존재한다는 것이다. 정의에 의해 $\Gamma$가 만족가능하지 않다는 말은 $\Gamma$의 문장들을 참으로 만드는 해석이 존재하지 않는다는 것이다.
2. $\Gamma\models\alpha$는 $\Gamma$의 모든 문장을 참으로 만드는 해석은 반드시 $\alpha$도 참으로 만든다는 것으로 정의되며, $\Gamma$를 전제(들의 집합), $\alpha$를 결론이라고 한다. 즉, $\Gamma$를 참으로 만드는 해석은 언제나 $\alpha$를 참으로 만든다는 것이다. 이를 $\Gamma$가 $\alpha$를 논리적으로 함축한다고 말합니다. 그렇지 않은 경우 $\Gamma\not\models\alpha$는 정의에 의해 $\Gamma$를 참으로 만들지만 $\alpha$를 거짓으로 만드는 해석이 존재한다는 말입니다.

3. $\alpha$가 논리적 참(logical truth)이라는 말은 $\alpha$가 모든 해석 하에서 참이라는 말이다. 즉, 임의의 $\mathcal{I}$에 대해 $\mathcal{I}\models\alpha$라는 말이다. 이와 동치인 개념으로 $\models\alpha$ 혹은 $\emptyset\models\alpha$가 있다. 논리적 참이 아닌 경우 $\not\models\alpha$로 표기한다. 이는 $\alpha$를 거짓으로 만드는 해석이 존재하는 말이다.

 논리적 참인 문장만 따로 볼 필요가 있습니다. $\emptyset$은 아무 원소도 지니지 않은 집합입니다. 원소가 없는 집합이란 개념이 생소하실 수 있겠지만 여러 가지 수학적 당위를 위해서 수학에서는 반드시 요구되는 개념입니다. 공집합은 자기자신과 같지 않은 원소들의 집합으로 정의됩니다. 즉, $\emptyset=\{x|x\neq x \}$입니다. 명제논리에서 실질조건문을 공부하셨으면 전건이 거짓이 되는 조건문은 언제나 참으로 정의한다는 걸 보셨을 겁니다. 술어논리에서도 조건문에 같은 방식으로 조건문을 정의했기 때문에 같은 방식이 통용됩니다.

 공집합에 이를 이용해봅시다. 가령 $A$가 집합이라고 하고 $x\in A$를 $x$가 $A$의 원소라고 하고, $\forall x (x\in A\rightarrow x\in B)$를 $A\subseteq B$의 정의로 합시다. 즉, A가 B의 부분집합이라는 말은 A에 속하는 원소들은 모두 B에 속해야 한다는 말입니다. 이를 이용하면 임의의 집합 $A$에 대해 $\emptyset\subseteq A$를 증명할 수 있습니다. 즉, $\forall x (x\in\emptyset \rightarrow A)$입니다. 집합론에 관한 아무 해석 $\mathcal{I}$을 가져옵시다. 임의의 $a\in\mathcal{I}$에 대해 $a'$는 $a$에 대한 개체상항이라고 할 때, $a'\in\emptyset$는 공집합의 정의상 $a\neq a$이고 수학적으로 이는 언제나 거짓입니다. 따라서 $a'\in\emptyset\rightarrow a'\in A$의 전건은 거짓으로 조건문은 참이 됩니다. 우리는 해석에 속하는 임의의 원소 $a$를 사용했으므로 결국 원래 문장이 증명됩니다.

 이것이 너무 번거롭다면 귀류법을 쓰면 됩니다. 공집합이 임의의 집합의 부분집합이라는 게 거짓이라고 합시다. 어떤 해석 $\mathcal{I}$와 집합 $A$가 있어서 $\mathcal{I}\not\models \forall x(x\in\emptyset\rightarrow x\in A)$가 된다는 말입니다. 실질조건문의 정의에 의해서 어떤 $a\in\mathcal{I}$가 있어서 괄호 안의 전건이 참이 되지만 후건이 거짓이 되는 경우가 있어야 합니다. 전건에 대해서만 보면 $a'\in\emptyset$가 되어야 합니다. 그런데 공집합에 원소가 존재한다는 건 자기자신과 같지 않은 대상이 존재한다는 것으로 이는 모순이기 때문에 불가능합니다. 모순은 우리가 가정한 것에서 나왔으므로 따라서 우리가 증명하고 싶은 것이 참이 됩니다.

 논리적 참이라는 개념은 논리적 함축의 개념으로 환원할 수 있습니다. 즉, $\alpha$가 논리적 참이라는 말은 공집합으로부터의 논리적 함축이라는 말과 동일합니다. 표기로는 $\emptyset\alpha$라고 씁니다만, 표기상의 이점으로 인해 공집합은 생략합니다. 이 동치개념은 공집합 때문에 발생합니다. 증명을 해봅시다. '$\alpha$가 논리적 참이면, $\emptyset\models\alpha$이다'와 그 역을 증명하면 됩니다.

 우선 $\alpha$가 논리적 참이라고 가정합시다. 우리는 $\emptyset$에 속하는 모든 문장(원소)을 참으로 만드는 해석은 $\alpha$도 참으로 만든다는 걸 증명하면 됩니다. 그런데 임의의 해석은 반드시 $\emptyset$에 속하는 문장을 참으로 만듭니다. 우선 아무 해석 $\mathcal{I}$를 택합시다. 이제 이를 집합론적 기호로 쓰면, $\forall \beta (\beta \in\emptyset\rightarrow \mathcal{I}\models\beta)$가 됩니다. 이때 $\beta$는 문장이라고 합시다. 물론 이 식은 논리학의 식은 아닙니다만 논리기호를 빌려서 우리가 증명하려는 문장의 형태를 보여줄 수 있습니다. 위에서 공집합이 모든 집합의 부분집합이라는 걸 증명할 때와 식이 거의 동일합니다. 이런 식으로 보면 공집합에 대해서 증명했던 방식과 동일하게 참임을 증명할 수 있습니다. 공집합은 원소가 없으므로 $\beta\in\emptyset$는 언제나 거짓이고 따라서 위의 문장은 실질조건문에 의해 언제나 참입니다.

 혹은, 귀류법을 사용할 수 있습니다. 증명하고자 하는 것의 모순을 가정합시다. 즉, $\emptyset\not\models\alpha$인데 이는 $\emptyset$에 속하는 모든 문장을 참으로 만들고 동시에 $\alpha$를 거짓으로 만드는 어떤 해석 $\mathcal{I}$가 존재한다는 말입니다. 그러나 전제에 의해서, 우리는 $\alpha$가 논리적 참이므로 $\mathcal{I}$는 $\alpha$를 참으로 만들어야 하므로 모순이 발생합니다. 따라서 처음에 가정한 것이 틀렸음을 알 수 있으므로 귀류법에 의해 증명하려던 것이 맞게 됩니다.

 역으로, $\emptyset\models\alpha$라고 합시다. 임의의 해석에 대해 $\alpha$가 참임을 증명하면 됩니다. 임의의 해석 $\mathcal{I}$를 가정합시다. 위와 같은 논리로 $\mathcal{I}\models\emptyset$이 됩니다. 이것이 거짓이라면 공집합에 속하는 어떤 원소(문장)에 대해서 해석이 그 문장을 참으로 만들어야 하는데 공집합에는 원소가 없기 때문에 모순입니다. 따라서 $\mathcal{I}$는 공집합을 참으로 만들기 때문에, 논리적 함축의 정의에 의해, 해당 해석은 $\alpha$를 참으로 만듭니다. $\mathcal{I}$는 임의의 해석이었기 때문에, 결국 임의의 해석이 $\alpha$를 참으로 만든다는 것을 증명했습니다.

 이렇게 되기 때문에 우리는 $\alpha$가 논리적 참이라는 말을 $\models\alpha$로 줄여쓸 것입니다.
*$\models$라는 말은 두 가지 의미로 사용되는 걸 잊지 마시길 바랍니다. $\mathcal{I}\models\alpha$는 해석 $\mathcal{I}$에서 $\alpha$가 참이라는 말이고, $\Gamma\models\alpha$는 $\Gamma$(문장들의 집합)을 참으로 만드는 모든 해석은 $\alpha$도 참으로 만든다는 말입니다. '해석 하에서 참인 문장'과 '어떤 전제들(문장들의 집합) 하에서 참인 문장'이 구분되서 사용됩니다.

*$\mathcal{I}\models\Gamma$를 자주 쓰기도 합니다. 이는 해당 해석이 문장들의 집합에 있는 문장들을 모두 참으로 만든다는 말의 줄임말입니다. $\mathcal{I}$가 $\Gamma$를 참으로 만든다고 말할 때가 많습니다.

1. $\{A\rightarrow B, \neg A \rightarrow C, B\rightarrow\neg A, C\rightarrow A\}$는 만족가능한가?
($A,B,C,D$는 문장들이라고 가정)

2. $\exists x \forall y Pxy \models \forall y \exists x Pxy$는 참인가?
3. $\forall y\exists x Pxy \models \exists x\forall y Pxy$는 참인가?
4. $\models \forall x Px \rightarrow\exists x Px$는 참인가?

 따로 증명해드리지는 않겠습니다. 직접 풀어보시고 모르시겠으면 댓글을 남겨주시길 바랍니다.

 답은 만족불가능, 참, 거짓, 참입니다. 

***

 수학교재와 철학교재들이 서로 용어사용이 다른 부분이 있습니다. 술어논리 첫 시간에 보았듯이 보통 '타당성'이란 개념은 논증에 사용됩니다. 즉, 어떤 술어논리의 문장들의 나열이 있을 때 마지막 문장을 제외한 문장들이 참인 모든 경우에 마지막 문장도 참인 경우에 논증이 타당하다고 말합니다. 이렇게 보면 논리적 타당성은 논리적 함축과 동일한 개념이라는 걸 알 수 있습니다. 이게 철학책의 관점입니다.

 수학에서 다루는 논리학에서는 논리적 함축과 타당성을 다르게 사용합니다. 여기서 정확히 설명하기는 어렵지만, 문장의 경우 논리적 참인 문장 = 타당한 문장으로 봅니다. 즉, sentence A is logical truth = A is (logically) valid로 봅니다. 일반적으로 타당성이란 개념은 논증에 사용하기 때문에 이 경우는 전제들의 집합이 공집합인 경우에만 한정하여 논증의 타당성 개념을 사용하고 있습니다. $\emptyset\models\alpha$인 경우에만 한정하여 사용합니다. 아마도 전제들이 참일 때 결론도 반드시 참이라는 개념을 '논리적 함축'이라는 이름으로 사용하기 때문에, 굳이 '타당성'이라는 이름을 다시 붙일 필요가 없어서 갈곳 잃은 타당성이란 이름을 전제들이 공집합인 특수한 논증으로 보낸 게 아닌가 싶습니다. 그러나, 수학적인 맥락이 아니라면 타당성은 전제가 공집합인 특수한 경우가 아니라 일반적인 전제들에 대해서도 사용한다는 점을 항상 염두에 두시길 바랍니다.