ORCID iD icon

Return to the class

Homework 4
#1.7: Consider the following truth table:
$$\begin{array}{l|l|l|l} A&B&C&F \\ \hline 0&0&0&0 \\ 1&0&0&1 \\ 0&1&0&1 \\ 0&0&1&1 \\ 1&1&0&0 \\ 1&0&1&0 \\ 0&1&1&0 \\ 1&1&1&1 \end{array}$$
(a) Find a formula $F$ in CNF which has that truth table.
(b) Find a formula $F$ in DNF which has that truth table.
Solution: For part (a), the formula $$F=(A \vee B \vee C) \wedge (\neg A \vee \neg B \vee C) \wedge (\neg A \vee B \vee \neg C) \wedge (A \vee \neg B \vee \neg C)$$ does the job. How is it found? Consider the rows where $F$ has a "1". For instance, the second row: the assignment in that row has $\mathcal{A}(A)=1$, $\mathcal{A}(B)=0$, and $\mathcal{A}(C)=0$ with $\mathcal{A}(F)=1$. We need this row to "occur" in our formula, so we will encode it as $A \vee \neg B \vee \neg C$. Doing this will cause the $F$ row there to be a $1$. We want all the rows with a "1" to be "true", so we mimic this process everywhere there is a "1" in column $F$ and then form the conjunction of those rows. This leads to the formula written.

For part (b), we do a similar thing to above --- guaranteeing that the rows containing $F$ are true by taking conjunctions in the three columns will guarantee it. For example, in row 2, we need $A \wedge \neg B \wedge \neg C$ in order for $F$ to give a true there. Doing this for all rows containing a "1" in the $F$ column yields the answer $$F = (A \wedge \neg B \wedge \neg C) \vee (\neg A \wedge B \wedge \neg C) \vee (\neg A \wedge \neg B \wedge C) \vee (A \wedge B \wedge C).$$

#1.11: Give formal proofs demonstrating that the formulas $(F \wedge (F \vee G))$ and $(F \vee (F \wedge G))$ are provably equivalent.
Solution: We must prove both $\{F \wedge (F \vee G)\} \vdash F \vee (F \wedge G)$ and $\{F \vee (F \wedge G)\} \vdash F \wedge (F \vee G)$. First let $\mathcal{F} = \{F \wedge (F \vee G)\}$. We shall prove $\mathcal{F} \vdash F \vee (F \wedge G)$:
$$\begin{array}{l|l} \mathrm{Statement} & \mathrm{Justification} \\ \hline 1. \mathcal{F} \vdash F \wedge (F \vee G) & \text{Assumption} \\ 2. \mathcal{F} \vdash F & \vee\text{-elimination on line 1} \\ 3. \mathcal{F} \vdash F \vee (F \wedge G) & \vee\text{-introduction on line 2} \end{array}$$ That completes that proof. Now let $\mathcal{F}=\{F \vee (F \wedge G)\}$. We shall now prove this $\mathcal{F} \vdash F \wedge (F \vee G)$: $$\begin{array}{l|l} \text{Statement} & \text{Justification} \\ \hline 1. \mathcal{F} \vdash F \vee (F \wedge G) & \text{Assumption} \\ 2. \mathcal{F} \vdash \neg (\neg F \wedge \neg (F \wedge G)) & \vee\text{-definition on line 1} \\ 3. \mathcal{F} \vdash \neg \neg F \vee \neg \neg (F \wedge G) & \text{deMorgan law on line 2} \\ 4. \mathcal{F} \vdash \neg F \rightarrow \neg \neg (F \wedge G) & \rightarrow\text{-definition on line 3} \\ 5. \mathcal{F} \cup \{\neg F\} \vdash \neg F \rightarrow \neg\neg(F \wedge G) & \text{Monotonicity on line 4} \\ 6. \mathcal{F} \cup \{\neg F\} \vdash \neg F & \text{Assumption} \\ 7. \mathcal{F} \cup \{\neg F\} \vdash \neg \neg (F \wedge G) & \rightarrow\text{-elimination on lines 5 and 6} \\ 8. \mathcal{F} \cup \{\neg F\} \vdash (F \wedge G) & \text{reverse double negation on line 7} \\ 9. \mathcal{F} \cup \{\neg F\} \vdash F \wedge G & \text{(,)-elimination on line 8} \\ 10. \mathcal{F} \cup\{\neg F\} \vdash F & \wedge\text{-elimination on line 9} \\ 11. \mathcal{F} \vdash F & \text{Proof by contradiction on lines 6 and 10} \\ 12. \mathcal{F} \vdash F \vee G & \vee\text{-introduction on line 11} \\ 13. \mathcal{F} \vdash F \wedge (F \vee G) & \wedge\text{-introduction on lines 11 and 12} \end{array}$$

#1.18: For each formula in Exercise 1.3, find an equivalent formula in CNF.
Solution: First we do it for (a): $(\neg A \rightarrow B) \vee ((A \wedge \neg C) \leftrightarrow B)$. Following step 1 of the CNF algorithm, we do $$\underbrace{(\neg A \rightarrow B)}_{\neg \neg A \vee B} \bigvee \underbrace{[((A \wedge \neg C) \leftrightarrow B)]}_{[\neg(A \wedge \neg C) \vee B] \wedge [\neg B \vee (A \wedge \neg C)]} $$ This gives us the following formula to which we apply step 2: $$(\underbrace{\neg \neg A}_{A} \vee B) \vee \Big[ [\underbrace{\neg(A \wedge \neg C)}_{\underbrace{\neg A \vee \neg \neg C}_{\neg A \vee C}} \vee B)] \wedge [\neg B \vee (A \wedge \neg C) \Big].$$ This gives us the following formula: $$(A \vee B) \vee \Big[ [\neg A \vee C \vee B] \wedge [\neg B \vee (A \wedge \neg C)] \Big].$$ To do step 3, we first distribute $\neg B$ into $A \wedge \neg C$ to get $$(A \vee B) \vee \Big[ [\neg A \vee C \vee B] \wedge [(\neg B \vee A) \wedge (\neg B \vee \neg C)] \Big].$$ To complete step 3, we distribute $A \vee B$ into the rest to get $$[A \vee B \vee \neg A \vee C \vee B] \wedge [A \vee B \vee \neg B \vee A] \wedge [A \vee B \vee \neg B \vee \neg C].$$ The other parts work similarly.

#1.24: Prove Proposition 1.45 by providing two formal proofs.
Solution: We must show $\{F \wedge (G \vee H)\} \vdash (F \wedge G) \vee (F \wedge H)$ and we must show $\{(F \wedge G) \vee (F \wedge H) \} \vdash F \wedge(G \vee H)$.

Let $\mathcal{F}=\{F \wedge (G \vee H) \}$. Now prove $$\begin{array}{l|l} \text{Statement} & \text{Justification} \\ \hline 1. \mathcal{F} \vdash F \wedge (G \vee H) & \text{Assumption} \\ 2. \mathcal{F} \vdash F & \wedge\text{-elimination on line 1} \\ 3. \mathcal{F} \cup \{G\} \vdash F & \text{Monotonicity on line 2} \\ 4. \mathcal{F} \cup \{G\} \vdash G & \text{Assumption} \\ 5. \mathcal{F} \cup \{G\} \vdash F \wedge G & \wedge\text{-introduction on lines 3 and 4} \\ 6. \mathcal{F} \cup \{G\} \vdash (F \wedge G) \vee (F \wedge H) & \vee\text{-introduction on line 5} \\ 7. \mathcal{F} \vdash (G \vee H) \wedge F & \wedge\text{-symmetry on line 1} \\ 8. \mathcal{F} \vdash G \vee H & \wedge\text{-elimination on line 7} \\ 9. \mathcal{F} \cup \{\neg G\} \vdash G \vee H & \text{Monotonicity on line 8} \\ 10. \mathcal{F} \cup \{\neg G\} \vdash \neg G & \text{Assumption} \\ 11. \mathcal{F} \cup \{\neg G\} \vdash H & \text{2nd } \vee\text{-modus ponens on lines 9 and 10} \\ 12. \mathcal{F} \cup \{\neg G\} \vdash F & \text{Monotonicity on line 2} \\ 13. \mathcal{F} \cup \{\neg G\} \vdash F \wedge H & \wedge\text{-introduction on lines 11 and 12} \\ 14. \mathcal{F} \cup \{\neg G\} \vdash (F \wedge H) \vee (F \wedge G) & \vee\text{-introduction on line 13} \\ 15. \mathcal{F} \cup \{\neg G\} \vdash (F \wedge G) \vee (F \wedge H) & \vee\text{-symmetry on line 14} \\ 16. \mathcal{F} \vdash (F \wedge G) \vee (F \wedge H) & \text{Proof by cases on lines 6 and 15} \end{array}$$ We now let $\mathcal{F}=\{(F \wedge G) \vee (F \wedge H)\}$ and we must prove $\mathcal{F} \vdash F \wedge (G \vee H)$: $$\begin{array}{l|l} \text{Statement} & \text{Justification} \\ \hline 1. \mathcal{F} \vdash (F \wedge G) \vee (F \wedge H) & \text{Assumption} \\ 2. \mathcal{F} \vdash \neg(\neg (F \wedge G) \wedge \neg(F \wedge H)) & \vee\text{-definition} \\ 3. \mathcal{F} \vdash \neg \neg (F \wedge G) \vee \neg \neg (F \wedge H) & \text{deMorgan on line 2} \\ 4. \mathcal{F} \vdash \neg(F \wedge G) \rightarrow \neg \neg (F \wedge H) & \rightarrow\text{-definition on line 3} \\ 5. \mathcal{F} \cup \{\neg(F \wedge G)\} \vdash \neg (F \wedge G) & \text{Assumption} \\ 6. \mathcal{F} \cup \{\neg(F \wedge G)\} \vdash \neg(F \wedge G) \rightarrow \neg \neg (F \wedge H) & \text{Monotonicity on line 4} \\ 7. \mathcal{F} \cup \{\neg (F \wedge G)\} \vdash \neg \neg (F \wedge H) & \rightarrow\text{-elimination on lines 5 and 6} \\ 8. \mathcal{F} \cup \{\neg (F \wedge G) \} \vdash F \wedge H & \text{Reverse double negation on line 7} \\ 9. \mathcal{F} \cup \{\neg (F \wedge G) \} \vdash H \wedge F & \wedge\text{-symmetry on line 8} \\ 10. \mathcal{F} \cup \{\neg (F \wedge G) \} \vdash H & \wedge\text{-elimination on line 9} \\ 11. \mathcal{F} \cup \{\neg (F \wedge G) \} \vdash H \vee G & \vee\text{-introduction on line 10} \\ 12. \mathcal{F} \cup \{\neg (F \wedge G) \} \vdash G \vee H & \vee\text{-symmetry on line 11} \\ 13. \mathcal{F} \cup \{F \wedge G\} \vdash F \wedge G & \text{Assumption} \\ 14. \mathcal{F} \cup \{F \wedge G\} \vdash G \wedge F & \wedge\text{-symmetry on lin 13} \\ 15. \mathcal{F} \cup \{F \wedge G\} \vdash G & \wedge\text{-elimination on line 14} \\ 16. \mathcal{F} \cup \{F \wedge G\} \vdash G \vee H & \vee\text{-introduction on line 15} \\ 17. \mathcal{F} \vdash G \vee H & \text{Proof by cases on lines 12 and 16} \\ 18. \mathcal{F} \cup \{\neg(F \wedge G)\} \vdash F & \wedge\text{-elimination on line 8} \\ 19. \mathcal{F} \cup \{F \wedge G\} \vdash F & \wedge\text{-elimination on line 13} \\ 20. \mathcal{F} \vdash F & \text{Proof by cases on lines 18 and 19} \\ 21. \mathcal{F} \vdash F \wedge (G \vee H) & \wedge\text{-introduction on lines 17 and 20} \end{array}$$

#1.27(a): Prove by induction: $$\left( \displaystyle\bigwedge_{i=1}^n F_i \right) \vee \left( \displaystyle\bigwedge_{j=1}^m G_j \right) \equiv \displaystyle\bigwedge_{i=1}^n \left( \displaystyle\bigwedge_{j=1}^m (F_i \vee G_j) \right)$$
Solution: proof essentially the same as the proof of 1.27(b) here: