I am confused on how to convert DNF to CNF. On the answer sheet that my teacher gave me, she just converted it right away with no explanation. Any help would be great.
Myy teacher converted $F: (A \wedge \neg B) \vee (B \wedge D)$ to CNF form of $(A \vee B) \wedge (\neg B \vee D)$. How does that go? Is there a way of converting it without drawing the truth tables?
2 Answers
De Morgan's Law states $ \neg(a + b) \equiv \neg a\neg b $ and $\neg(ab) \equiv \neg a + \neg b$. $$\begin{equation} \begin{aligned}A\neg B + BD \equiv & \neg(\neg(A\neg B)\neg(BD)) \text{ De Morgan's outside} \\ \equiv & \neg((\neg A + B)(\neg B + \neg D)) \text{ De Morgan's inside} \\ \equiv & \neg(\neg A \neg B + \neg A \neg D + B \neg D) \text{ Distributivity} \\ \equiv & \neg(\neg A \neg B + \neg A \neg D (\neg B + B) + B \neg D) \text{ Complementation} \\ \equiv & \neg(\neg A \neg B + \neg A \neg D \neg B + \neg A \neg D B + B \neg D) \text{ Distributivity} \\ \equiv & \neg(\neg A \neg B(1 + \neg D) + B \neg D (1 + \neg A)) \text{ Distributivity} \\ \equiv & \neg(\neg A \neg B + B \neg D) \text{ Annihilator} \\ \equiv & (A + B)(\neg B + D) \text{ De Morgan's outside}\end{aligned}\end{equation} $$
You might also want to look into K-maps.
I think there is a simpler way than the accepted answer:
$$\begin{equation} \begin{aligned}A\neg B \vee BD \equiv & (A \vee B)(A \vee D)(\neg B \vee B)(\neg B \vee D) \text{ Distributivity} \\ \equiv & (A \vee B)(A \vee D) 1 (\neg B \vee D) \text{ Tertium non datur} \\ \equiv & (A \vee B)(A \vee D)(\neg B \vee D) \text{ Neutral element of $\wedge$} \\ \equiv & (A \vee B)(\neg B \vee D) \text{ middle term is redundant*} \end{aligned}\end{equation} $$
* $A\vee D$ is only false if both A and D are false but then the whole term is false anyway because it reduces to $(B)(A \vee D)(\neg B)$.
