1.3 Consequence and Equivalence
Definition 1.3.1
모든 assignment $\mathcal{A}$에 대해 [$\mathcal{A} \models F$이면, $\mathcal{A} \models G$]가 성립하면, formula $G$가 formula $F$의 consequence(귀결)이라고 한다. 이를 $F \models G$로 쓴다.
정의에 사용된 기호 $\models$는 Sec 1.2에서 사용된 것과 같다. 차이점은 왼쪽에 assignment 대신 다른 formula가 있다는 것. $``–\models F”$라고 쓸 때에는 $\models$의 왼쪽에 무엇이 오느냐에 따라 해석이 달라지게 된다.
- $\mathcal{A}\models F$는 $\mathcal{A}(F)=1$이라는 뜻이다. 이를 $``\mathcal{A} \textrm{ models } F”$라고 읽는다.
- $G \models F$는 $G$를 model하는 모든 assignment가 $F$ 역시 model한다는 뜻이다. 즉, $F$는 $G$의 귀결이다.
- $\models F$1는 모든 assignment가 $F$를 model한다는 뜻이다. 즉, $F$는 tautology이다.
Consequence의 개념은 Sec 1.1의 $``\textrm{implies}”$와 밀접한 연관이 있다.
Proposition 1.3.2
임의의 formula $F$, $G$에 대해,
\[F \models G \textrm{ iff } F \rightarrow G\textrm{ is tautology.}\]
Proof.
대우 명제를 보이자. 즉, $F \rightarrow G$가 tautology가 아닌 것과 $G$가 $F$의 conseqeunce가 아닌 것이 동치임을 보이자.
tautology의 정의에 의해, $F \rightarrow G$가 tautology가 아니다. $\Leftrightarrow$ Assignment $\mathcal{A}$가 존재하여 $\mathcal{A}\models \neg(F \rightarrow G)$.
기호 $\rightarrow$의 정의에 의해, $\mathcal{A}\models \neg(F \rightarrow G)$ $\Leftrightarrow$ $\mathcal{A}\models \neg(\neg F \vee G)$.
명제 논리의 semantics에 따르면, $\mathcal{A}\models \neg(\neg F \vee G)$ $\Leftrightarrow$ both $\mathcal{A}\models F$ and $\mathcal{A}\models \neg G$
마지막으로 consequence의 정의에 의해 $\mathcal{A}\models F$ 이고 $\mathcal{A}\models \neg G$인 assignment $\mathcal{A}$가 존재 $\Leftrightarrow$ $G$는 $F$의 consequence가 아니다. $\square$
Formula $G$가 formula $F$의 consequence인지 아닌지 판정하고 싶다고 하자. 이러한 문제를 consequence problem(귀결 문제)라고 한다. Prop 1.3.2로부터, 이는 validity problem이 된다. ($F \models G$ iff $F \rightarrow G \textrm{ is valid}$) 이러한 문제는 진리표로부터 해결 가능. $F \rightarrow G$의 모든 진릿값이 1이면, $G$는 $F$의 consequence. 특히, $F$가 contradiction이면, $G$는($G$가 무엇이든 관계없이) $F$의 consequence.
Example 1.3.3
$F$, $G$가 formula라고 하자. 다음은 진리표로부터 보일 수 있다.
\[(F \wedge G) \models F\]
\[F \models (F \vee G)\]
\[(F \wedge \neg F) \models G\]
Definition 1.3.4
$G$가 $F$의 consequence이고 $F$가 $G$의 consequence이면, $F$와 $G$가 equivalent(동치)라고 한다. 이를 $F \equiv G$라고 쓴다.
Prop 1.3.2로부터, 두 formula $F$, $G$가 동치 iff $F \leftrightarrow G$가 tautology. 즉 두 formula $F$, $G$가 동치인지 판정하는 것 역시 진리표로 계산할 수 있다.
이하는 중요한 동치인 formula들.
Example 1.3.5
임의의 formula $F$, $G$와 임의의 tautology $\top$, 임의의 contradiction $\perp$에 대해,
\[(F \wedge G) \equiv (G \wedge F) \textrm{ and } (F \vee G) \equiv (G \vee F)\]
\[(F \wedge \top) \equiv F \textrm{ and } (F \vee \top) \equiv \top\]
\[(F \wedge \perp) \equiv \perp \textrm{ and } (F \vee \perp) \equiv F\]
Example 1.3.6 [Distributivity Rules]
임의의 formula $F$, $G$, $H$에 대해,
\[(F \wedge (G \vee H)) \equiv ((F \wedge G) \vee (F \wedge H))\]
\[(F \vee (G \wedge H)) \equiv ((F \vee G) \wedge (F \vee H))\]
Example 1.3.7 [De Morgan’s Rules]
임의의 formula $F$, $G$에 대해
\[\neg(F \wedge G) \equiv (\neg F \vee \neg G)\]
\[\neg(F \vee G) \equiv (\neg F \wedge \neg G)\]
위 규칙들을 사용해 복잡한 formula를 정리해 보자.
Example 1.3.8
\[((C \wedge D) \vee A) ((C \wedge D)\vee B) \wedge (E \vee \neg E) \equiv (A \wedge B) \vee (C \wedge D)\]
를 보이자. 좌측 formula부터 시작. $(E \vee \neg E)$는 tautology이므로, Ex 1.3.5에 의해 좌변은 $((C \wedge D) \vee A) ((C \wedge D)\vee B)$와 같다. Ex 1.3.6의 두 번째 distribution rule을 사용하면 이는 $(C \wedge D)\vee(A \wedge B)$와 동치이다. 끝으로 Ex 1.3.5로부터 이는 $(A \wedge B)\vee(C \wedge D)$와 동치.
Ex 1.3.8의 식은 임의의 formula $A$, $B$, $C$, $D$, $E$에서 성립. 만일 진리표를 사용했다면 $2^{5}=32$개 행을 계산해야 했을 것이다.
Sec 1.4에서는 이 idea를 확장해 formal proof(형식 증명)의 개념을 소개한다. 형식 증명은 formula들의 집합으로부터 formula를 derive(유도)하는 방법을 제공한다. 미리 consequence의 개념을 확장하자.
Definition 1.3.9
$\mathcal{F}=\{F_1, F_2, F_3,\cdots \}$를 formula들의 집합이라고 하자.
임의의 assignment $\mathcal{A}$에 대해, $\mathcal{F}$의 각 formula $F_i$가 $\mathcal{A}\models F_i$이면, $\mathcal{A}$가 $\mathcal{F}$를 model한다고 말하며 $\mathcal{A}\models \mathcal{F}$로 나타낸다.
모든 assignment $\mathcal{A}$에서 $\mathcal{A}\models \mathcal{F}$가 $\mathcal{A}\models G$를 함의하면, formula $G$가 $\mathcal{F}$의 consequence라고 한다.
$G$가 formula들의 집합 $\mathcal{F}$의 consequence가 되는지 판정하고 싶다고 하자. 만약 $\mathcal{F}$가 유한하다면 $\mathcal{F}$의 모든 formula들의 conjunction $\bigwedge \mathcal{F}$를 생각하여 $\bigwedge \mathcal{F} \rightarrow G$의 진리표를 계산해 보면 될 것이다. 집합 $\mathcal{F}$가 너무 크지만 않다면…
만약 집합 $\mathcal{F}$가 무한하다면… 아예 안 통할 것이다. $\mathcal{F}$로부터 $G$를 유도하는 다른 접근법을 생각해 보자.
Example 1.3.10
$\mathcal{F}=\{F_1, F_2, F_3,\cdots \}$가 다음 formula들의 집합이라고 하자.
\[\{A, (A \rightarrow B), (B \rightarrow C), (C \rightarrow D), (D \rightarrow E), (E \rightarrow F), (F \rightarrow G)\}\]
$\mathcal{F}$ 내의 7개 formula가 모두 참이라고 가정하자. 그러면 $A$와 $(A \rightarrow B)$가 참이므로, $B$도 참. $B$와 $(B \rightarrow C)$가 참이므로, $C$도 참이고…
만약 $\mathcal{F}$의 각 formula들이 참이라면 $A$, $B$, $C$, $D$, $E$, $F$, $G$ 역시 참이다. 진리표를 그릴 필요도 없이 이들은 모두 $\mathcal{F}$의 consequence이다.
이번에는 $\mathcal{F}$의 모든 formula들의 conjunction $\bigwedge \mathcal{F}$를 생각해 보자.
\[\bigwedge \mathcal{F} = A \wedge(A \rightarrow B)\wedge (B \rightarrow C)\wedge (C \rightarrow D)\wedge (D \rightarrow E)\wedge (E \rightarrow F)\wedge (F \rightarrow G)\]
$\bigwedge \mathcal{F}\rightarrow G$의 진리표는 128행. 계산할 필요 없이 각 행은 진릿값 1을 갖는다. $\bigwedge \mathcal{F}\rightarrow G$는 tautology이며, 이는 $G$가 $\mathcal{F}$의 consequence인 것과 동치.
위 Example에서, 우리는 $F$와 $F \rightarrow G$가 모두 참이면 $G$ 역시 참이라는 사실을 이용했다. 즉, $G$는 $F \wedge (F \rightarrow G)$의 consequence. 이는 Ex 1.2.7의 진리표로부터 알 수 있다.
128개 행의 진리표를 일일이 계산하기보다 이미 알려진 4행짜리 진리표를 이용한 것. 다시 말해, 이전에 밝혀진 rule을 사용해 $\mathcal{F}$로부터 $G$를 유도해 낸 것이다.
-
기호 왼쪽에 공집합이 온 것. ↩