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: http://tomcuchta.com/teach/classes/2018/MATH-2510-Spring-2018-FairmontState/notes/problem1.27b.php
