술어논리(8) ㅡ 만족가능성과 논리적 함축의 관계

$\Gamma$는 문장들의 집합, $\alpha$는 문장일 때

1.$\Gamma\models\alpha\Longleftrightarrow\Gamma\cup\{\neg\alpha\}\text{는 만족불가능}$

2.$\Gamma\not\models\alpha\Longleftrightarrow\Gamma\cup\{\neg\alpha\}\text{는 만족가능}$

3.$\Gamma\models\neg\alpha\Longleftrightarrow\Gamma\cup\{\alpha\}\text{는 만족불가능}$

4.$\Gamma\not\models\neg\alpha\Longleftrightarrow\Gamma\cup\{\alpha\}\text{는 만족가능}$

 즉, 만족가능성이 있으면 논리적 함축을 정의할 수 있고, 논리적 함축이 있으면 만족가능성을 정의할 수 있습니다. 서로 상호교환가능한 개념으로, 어느 하나가 특정한 상황에서 쓰기 어려우면 다른 한쪽으로 변환해서 사용하는 게 좋다는 의미입니다. 1과 2는 같은 말이고 3,4는 1에 부정기호만 추가하면 되기 때문에 1만 증명하면 됩니다.

 $\Gamma\models\alpha$를 가정합시다. 만족불가능성은 해석이 존재하지 않는다는 것과 동일하기 때문에 해석이 존재한다고 가정해서 모순을 이끌어내면 됩니다. 즉, 어떤 해석 $\mathcal{I}$가 있어서 $\mathcal{I}\models\Gamma\cup\{\neg\alpha\}$라고 합시다. 즉, $\mathcal{I}$는 $\Gamma\cup\{\neg\alpha\}$에 있는 모든 문장을 참으로 만듭니다. 따라서, $\Gamma$와 $\neg\alpha$를 참으로 만듭니다. 그런데 해석 $\mathcal{I}$가 $\Gamma$를 참으로 만들기 때문에 전제에 의해서 $\alpha$도 참으로 만들어야 합니다. 이미 $\mathcal{I}$에서 $\neg\alpha$가 참이기 때문에 둘은 동시에 성립할 수 없습니다. 따라서 모순이 발생하므로 귀류법에 의해 $\Gamma\cup\{\neg\alpha\}$를 참으로 만드는 해석은 존재하지 않습니다.

 이제 반대를 가정합시다. $\Gamma\cup\{\neg\alpha\}$가 만족불가능하다고 합시다. 우리는 $\Gamma\models\alpha$를 증명해야 합니다. 이는 $\Gamma$를 참으로 만드는 해석은 반드시 $\alpha$도 참으로 만들어야 한다는 것입니다. $\mathcal{I}\models\Gamma$인 임의의 $\mathcal{I}$를 택합시다. 그러면, $\alpha$는 이 해석 하에서 참이거나 거짓일 겁니다. 거짓이라고 합시다. 그러면 $\Gamma$와 $\neg\alpha$가 $\mathcal{I}$에서 모두 참인데, 전제는 두 집합의 합집합이 만족불가능, 즉 둘을 동시에 참으로 만드는 해석은 없다고 하였으므로 이 경우는 불가능합니다. 따라서 $\alpha$는 이 해석 하에서 반드시 참입니다. 우리는 $\Gamma$를 참으로 만드는 임의의 해석 $\mathcal{I}$에 대하여 $\alpha$가 참임을 보였기 때문에 원하는 것이 증명되었습니다.

 1번이 있으면 서로 환원시킬 수 있습니다. $\Gamma$가 만족가능하다는 개념을 논리적 함축으로 정의해봅시다.

a. $\Gamma$가 공집합인 경우 : 공집합은 언제나 만족가능합니다. 저번 시간에 했던 공집합에 관한 논리들을 사용하면, 공집합이 만족불가능하려면 '임의의 해석에 대해서 공집합에 속하는 모든 문장들은 주어진 해석 하에서 참이다'가 거짓이어야 하는데, 이는 '어떤 해석이 있어서 공집합에 속한 어떤 문장이 그 해석 하에서 거짓이다'라는 말이고 이 말은 '공집합에 어떤 원소(문장)가 있다'는 말이 되고, 공집합엔 원소가 없으므로 이는 거짓이 됩니다. 따라서 공집합은 언제나 만족가능합니다. 따라서 $\Gamma$가 공집합인 경우 $\Gamma$가 만족가능하다는 말은 논리적 참인 아무 문장을 잡아서 가령 $\models A\vee \neg A$로 정의하면 됩니다.

b. $\Gamma$가 공집합이 아닌 경우 : 4번 식을 사용하면 됩니다. $\Gamma$가 공집합이 아니므로 어떤 $\alpha$가 원소로 있을 것이고, 4번 식과 일치하게 만들어서 $(\Gamma - \{\alpha\})\cup\{\alpha\}$에 대해 4번식을 사용한 형태로 정의하면 됩니다. 우리는 문장들의 집합이 공집합인 경우도 허용하기 때문에 $\Gamma - \{\alpha\}$가 공집합인 경우에도 문제가 생기지 않습니다.

 반대로 만족가능하다는 개념으로부터 논리적 함축을 정의할 수 있습니다. 이는 1의 형태 그대로 정의하면 됩니다.