1.2 Validity, Satisfiability, Contradiction
$\mathcal{S}=\{A_{1}, \cdots A_{n}\}$를 atomic formula들의 집합, $\mathcal{F(S})$를 $\mathcal{S}$의 atomic formula들로부터 만들어지는 모든 formula들의 집합이라고 하자.
Definition 1.2.1
$\mathcal{S}$의 assignment(할당)란 함수 $\mathcal{A}: \mathcal{S} \rightarrow \{0,1\}$이다.
즉 $\mathcal{S}$의 assignment는 $\mathcal{S}$의 각 atomic formula와 그 진릿값을 대응시킨다. 이를 자연스럽게 $\mathcal{F(S})$로 확장할 수 있다. 임의의 formula $F \in \mathcal{F(S})$가 주어지면 $\mathcal{S}$의 assignment $\mathcal{A}$가 $F$의 진리표에서 하나의 행에 대응하기 때문이다. 이 행에서 $F$의 진릿값을 $\mathcal{A}(F)$로 정의한다.
Remark 1.2.2
더 나아가 $\mathcal{S}$의 assignment $\mathcal{A}$는 $\mathcal{F(S})$에 속하지 않는 formula에 대해서까지 확장할 수 있다.
$F_{0} \notin \mathcal{F(S})$를 생각. $\mathcal{S}_{0}$를 $F_{0}$의 atomic subformula들의 집합이라고 하자. 만일 $\mathcal{A}$를 $\mathcal{S} \cup \mathcal{S}_{0}$까지 확장시킨 모든 extension들이 $F_{0}$에 같은 값을 할당해 준다면, 이 값으로 $\mathcal{A}(F_{0})$을 정의할 수 있을 것이다.
Example 1.2.3
$A$, $B$를 atomic formula, $\mathcal{A}$를 $\{A,B\}$의 assignment라고 하자. $\mathcal{A}(A)=1$, $\mathcal{A}(B)=0$이면,
\[\mathcal{A}(A \wedge B)=0\]
\[\mathcal{A}(A \vee B)=1\]
\[\mathcal{A}(A \wedge (C \vee \neg C))=1\]
\[\mathcal{A}(B \vee (C \wedge \neg C))=0\]
$\mathcal{A}(A)=1$이고, $C$에 어떤 값을 할당하든 $ (C \vee \neg C)$는 진릿값 1을 가지므로, $\mathcal{A}(A \wedge (C \vee \neg C))=1$이다.
마찬가지로 $\mathcal{A}(B)=0$이고, $C$에 어떤 값을 할당하든 $(C \wedge \neg C)$는 진릿값 0을 가지므로, $\mathcal{A}(B \vee (C \wedge \neg C))=0$.
Definition 1.2.4
$\mathcal{A}$를 $\mathcal{S}$의 assignment, $F$를 formula라고 하자.
$\mathcal{A}(F)=1$일 때, $F$가 assignment $\mathcal{A}$ 아래에서 hold(성립)한다고 말한다. 또는 $\mathcal{A}$가 $F$의 model(모형)이라고 한다. 이를 $\mathcal{A} \models F$라고 표현한다.
Definition 1.2.5
- Formula가 모든 assignment 아래에서 성립한다면 이를 valid(타당)하다고 한다. 이를 $\models F$로 쓴다. Valid formula를 tautology(항진 명제)라고 한다.
- Formula가 어떤 assignment 아래에서 성립한다면 이를 satisfiable(충족가능)하다고 한다.
- Formula가 어느 assignment 아래에서도 성립하지 않는다면 이를 unsatisfiable(충족불가능)하다고 한다. Unsatisfiable formula를 contradiction(모순 명제)라고 한다.
Example 1.2.6
Example 1.2.3의 $ (C \vee \neg C)$는 tautology, $(C \wedge \neg C)$는 contradiction.
주어진 formula가 valid인지 아닌지를 판단하고 싶다. 이는 decision problem(결정 문제)의 하나이다. Decision problem이란 특정한 input이 주어졌을 때, “Yes” 또는 “No”로 답이 나오는 문제를 말한다.
Input이 주어진 formula $F$라면, “Is $F$ valid?”라는 질문을 할 수 있다. 이러한 질문을 validity problem(타당성 문제)라고 한다. 비슷하게 “Is $F$ satisfiable?”이라는 질문은 satisfiable problem(충족가능성 문제)이다.
이러한 문제들에 대답해 줄 수 있는 도구가 바로 진리표. 만일 $F$의 모든 진릿값이 1이라면, $F$는 valid. 만약 어떤 진릿값이 1이라면, $F$는 satisfiable. 그리고 진릿값 1이 존재하지 않으면, $F$는 unsatisfiable이다.
Example 1.2.7
\[(A \wedge (A \rightarrow B)) \rightarrow B)\]
위 formula는 satisfiable일까? 진리표를 그려보자.
| \[A\] | \[B\] | \[A \rightarrow B\] | \[A \wedge (A \rightarrow B)\] | \[(A \wedge (A \rightarrow B)) \rightarrow B)\] |
|---|---|---|---|---|
| \[0\] | \[0\] | \[1\] | \[0\] | \[1\] |
| \[0\] | \[1\] | \[1\] | \[0\] | \[1\] |
| \[1\] | \[0\] | \[0\] | \[0\] | \[1\] |
| \[1\] | \[1\] | \[1\] | \[1\] | \[1\] |
$(A \wedge (A \rightarrow B)) \rightarrow B)$가 모든 assignment에서 진릿값 1을 가짐을 알 수 있다. 따라서 $(A \wedge (A \rightarrow B)) \rightarrow B)$는 satisfiable일 뿐만 아니라 valid.
이론상 임의의 formula $F$가 주어졌을 때, 진리표만 확인하면 $F$가 valid인지, satisfiable인지, unsatisfiable인지 확인이 가능하다.
그러나 이 방법이 효율적이라고 하기는 어려운데, 만일 $F$가 $n$개의 atomic formula를 포함한다면 총 $2^{n}$개 행을 갖는 진리표를 일일이 계산해 보아야 하기 때문이다. 진리표 없이 validity/satisfiability problem을 해결할 방법은 없을까?