younghwanjoo1608

ㅎㅇ

5 minute read


Example 1.3.8에서 $((C \wedge D) \vee A) ((C \wedge D)\vee B) \wedge (E \vee \neg E)$이 $(A \wedge B) \vee (C \wedge D)$와 동치임을 보였다. 이는 두 conjunction($\wedge$, 연언)의 disjunction($\vee$, 선언)이다. 이것이 이번 section의 주제. 모든 formula는 disjunction들의 conjunction과 동치이다!


Definition 1.6.1

Literal은 atomic formula나 atomic formula의 negation을 말한다. 이에 따라 literal이 positive, 또는 negative라고 한다.


Example 1.6.2

$A$가 atomic formula이면, $A$는 positive literal이며 $\neg A$는 negative literal이다.


Definition 1.6.3

Formula $F$가 literal들의 disjunction들의 conjunction일 때, $F$는 conjunctive normal form (CNF)에 속해 있다고 한다.

\[ F=\bigwedge_{i=1}^{n} \Bigg( \bigvee_{j=1}^{m} L_{i,j} \Bigg)\]

여기서 각 $L_{i,j}$는 atomic이거나 negated atomic이다.


Definition 1.6.4

Formula $F$가 literal들의 conjunction들의 disjunction일 때, $F$는 disjunctive normal form (DNF)에 속해 있다고 한다.

\[ F=\bigvee_{i=1}^{n} \Bigg( \bigwedge_{j=1}^{m} L_{i,j} \Bigg)\]

여기서 각 $L_{i,j}$는 atomic이거나 negated atomic이다.


Example 1.6.5

\[ \begin{align*} &(A \vee B) \wedge (C \vee D) \wedge (\neg A \vee \neg B \vee \neg D) \textrm{ is in CNF,} \\ &(\neg A \wedge B) \vee C \vee (B \wedge \neg C \wedge D) \textrm{ is in DNF, and} \\ &(A \vee B) \wedge ((A \wedge C) \vee (B \wedge D))\textrm{ is neither CNF nor DNF.} \end{align*} \]


Lemma 1.6.6

$F$가 CNF, $G$가 DNF의 formula라고 하자.

그러면 $\neg F$는 DNF의 어느 formula와 동치이며 $\neg G$는 CNF의 어느 formula와 동치이다.


Proof.


$F$가 CNF formula이면, 어떤 literal $L_{i,j}$에 대해

\[ F=\bigwedge_{i=1}^{n} \Bigg( \bigvee_{j=1}^{m} L_{i,j} \Bigg)\]

이다. $F$의 negation은 Proposition 1.5.2에 의해,

\[ \begin{align*} \neg F &= \neg \bigwedge_{i=1}^{n} \Bigg( \bigvee_{j=1}^{m} L_{i,j} \Bigg) \\ &\equiv \bigvee_{i=1}^{n} \neg \Bigg( \bigvee_{j=1}^{m} L_{i,j} \Bigg) \\ &\equiv \bigvee_{i=1}^{n} \Bigg( \bigwedge_{j=1}^{m} \neg L_{i,j} \Bigg) \end{align*} \]

이는 DNF formula. $\neg G$도 같은 방법으로. $\square$

Theorem 1.6.7

모든 formula $F$는 CNF의 어떤 formula $F_{1}$, DNF의 어떤 formula $F_{2}$와 동치이다.


Proof.


$F$에 대한 induction on the complexity.

[Base case] $F$가 atomic이라고 가정, $F$는 그 자체로 이미 CNF, DNF이므로 $F = F_{1} = F_{2}$.

[Induction hypothesis] Formula $G$, $H$에 대해 정리의 결론이 성립한다고 하자. 즉, CNF formula $G_{1}$, $H_{1}$과 DNF formula $G_{2}$, $H_{2}$가 존재해 $H \equiv H_{1} \equiv H_{2}$, $G \equiv G_{1} \equiv G_{2}$이다.

CNF, DNF의 어느 formula와 동치라는 성질은 보존된다. $F \equiv G$이면, induction hypothesis에 의해 $F_{1} = G_{1}$, $F_{2} = G_{2}$를 취할 수 있다. 따라서, 두 case ($\neg$, $\wedge$)만 더 고려하면 OK.

먼저, $F$가 $\neg G$ 형태라고 가정. 그러면 $F \equiv \neg G_{1} \equiv \neg G_{2}$. $G_{1}$이 CNF이므로, Lemma 1.6.6에 의해 $\neg G_{1}$는 어느 DNF formula $G_3$과 동치이다. 마찬가지로 $\neg G_{2}$는 어느 CNF formula $G_4$과 동치. 따라서 $F_{1} = G_{4}$, $F_{2} = G_{3}$로 취하면 된다.

이제 $F$가 $G \wedge H$ 형태라고 하자. 그러면 Substitution(Theorem 1.5.4)에 의해 $F \equiv G_1 \wedge H_1$. $G_1$과 $H_1$은 CNF이므로, 그 conjunction도 CNF.

남은 건 $F =G \wedge H$가 어느 DNF formula와 동치임을 보이는 것. 다시 Substitution(Theorem 1.5.4)로부터 $F \equiv G_2 \wedge H_2$이고, 이들 각각은 DNF에 속하므로 다음과 같이 쓸 수 있다.

\[G_2 = \bigvee_{i} M_i \quad \textrm{and} \quad H_2 = \bigvee_{j} N_j \]

여기서 $M_i$, $N_j$는 literal들의 conjunction. 그러므로

\[ F \equiv \Bigg( \bigvee_{i} M_i \Bigg) \wedge \Bigg( \bigvee_{j} N_j \Bigg) \]

Proposition 1.5.3의 동치 조건 이용.

\[ F \equiv \bigvee_{i} \Bigg( \bigvee_{j} (M_i \wedge N_j) \Bigg) \]

이는 literal들의 conjunction의 disjunction이므로, DNF. $\square$

Theorem 1.6.7에 의하면, 주어진 formula $F$에 대해, $F$와 동치인 DNF의 formula가 존재함이 보장. 그러한 formula를 찾기 위한 방법 중 하나는 진리표.


\[A\] \[B\] \[F\]
\[0\] \[0\] \[1\]
\[0\] \[1\] \[0\]
\[1\] \[0\] \[1\]
\[1\] \[1\] \[0\]


$(F$가 assignment $\mathcal{A}$ 아래에서 참$)$ iff $(\mathcal{A}$가 진리표의 첫 번째, 또는 세 번째 행에 부합$)$

이는 formula가 DNF에 속한다는 뜻으로 이어지는데,

$(F$가 참$)$ iff $(A$와 $B$가 둘 다 거짓(1행) $\textrm{or}$ $A$가 참이고 $B$가 거짓(3행)$)$

즉, $F$는 $( \neg A \wedge \neg B) \vee (A \wedge \neg B)$와 동치이고, 이는 conjunction들의 disjunction이므로 DNF.

마찬가지로 $F$가 거짓인 행을 생각해 보자. 이로부터 CNF를 얻을 수 있다.

$(F$가 거짓$)$ iff $(\mathcal{A}$가 진리표의 두 번째와 네 번째 행에 부합하지 않음$)$

iff $(A$ 또는 $\neg B$가 성립(not 2행) $\textrm{and}$ $\neg A$ 또는 $\neg B$가 성립(not 4행)$)$

따라서 $F$는 $( A \vee \neg B) \wedge (\neg A \vee \neg B)$와 동치이고, 이는 disjunction들의 conjunction이므로 CNF.


이 방법은 실제로 Theorem 1.6.7의 대체 증명이라고 할 수 있다. 임의의 formula $F$를, 진리표를 이용하면 CNF 또는 DNF로 만들 수 있다!

다음 알고리즘은 $F$와 동치인 CNF formula를 찾는 또 다른 방법. 항상은 아니지만 대체로 진리표 계산보다 효과적이다.


CNF Algorithm

  • Step 1 : $F \rightarrow G$ 형태의 모든 subformula를 $(\neg F \vee G)$로,
    $F \leftrightarrow G$ 형태의 모든 subformula를 $(\neg F \vee G) \wedge (\neg G \vee F)$로 대체한다.
    $\rightarrow$ , $\leftrightarrow$가 나타나지 않으면, Step 2로 진행한다.

  • Step 2 : 모든 double negation을 제거하고, 가능할 때마다 De Morgan’s Rules를 적용한다. 다시말해,
    $\neg \neg G$를 $G$로,
    $\neg (G \wedge H)$를 $(\neg G \vee \neg H)$로,
    $\neg (G \vee H)$를 $(\neg G \wedge \neg H)$로 대체한다.
    이러한 형태의 subformula가 없다면, Step 3로 진행한다.

  • Step 3 : 가능할 때마다 $\vee$에 대한 Distributivity Rules를 적용한다. 다시말해,
    $(G \vee (H \wedge K))$ 또는 $((H \wedge K) \vee G)$를 $((G \vee H) \wedge (G \vee K))$로 대체한다.
    이러한 subformula를 모두 제거하면, 남겨진 formula는 CNF이다.
    만약 $\wedge$에 대한 Distributivity Rules를 적용한다면, DNF를 얻는다.


Example 1.6.8

CNF Algorithm을 적용하자.

\[F = (A\vee B) \rightarrow (\neg B \wedge A)\]


Proof.


[Step 1] $\rightarrow$를 제거.

\[\neg (A \vee B) \vee (\neg B \wedge A)\]

[Step 2] De Morgan’s Rules

\[(\neg A \wedge \neg B) \vee (\neg B \wedge A)\]

[Step 3] 위 formula는 DNF. Distributivity Rules로부터

\[((\neg A \wedge \neg B) \vee \neg B) \wedge ((\neg A \wedge \neg B) \vee A)\]

한 번 더,

\[(\neg A \vee \neg B) \wedge (\neg B \vee \neg B) \wedge (\neg A \vee A) \wedge (\neg B \vee A)\]

이로부터 CNF를 얻었다. 조금 정리하자면, $(\neg A \vee A)$가 tautology이므로, 위 formula는

\[(\neg A \vee \neg B) \wedge (\neg B) \wedge (\neg B \vee A)\]

와 동치. 다시,

\[(A \vee \neg B) \wedge (\neg A \vee \neg B)\]

와 동치. 이는 위쪽 진리표에서 얻었던 formula와 동일하다. $\square$

CNF Algorithm의 관점에서 보면, Theorem 1.6.7을 강화시킬 수 있을 것 같다. Theorem 1.6.7은 임의의 formula $F$에 대해 $F$와 동치인 CNF formula $F_{1}$과 DNF formula $F_{2}$가 존재한다고 말하고 있다. 이제 $F_{1}$과 $F_{2}$가 $F$와 provably equivalent라고 주장할 수 있다! 알고리즘의 각 단계에서 특정 formula를 동치인 다른 formula로 대체했으므로, formal proof가 가능.

이제 편의상, notation $F \dashv \vdash G$를 $``F \textrm{ and } G \textrm{ are provably equivalent}”$라는 의미로 사용하자.

CNF Algorithm


이제 Thm. 1.5.5에 의해 이 알고리즘의 결과로 얻은 CNF formula $F_{1}$, DNF formula $F_{2}$는 $F$와 provably equivalent. 이것으로 Thm. 1.6.7의 강화된 버전을 얻었다.


Proposition 1.6.9

모든 formula $F$는 CNF의 어떤 formula $F_{1}$, DNF의 어떤 formula $F_{2}$와 증명 가능하게 동치이다.

You may also enjoy