4
$\begingroup$

I'm confused on how to convert DNF to CNF. On the answer sheet my teacher gave me, she just convert it right away with no explanation.

So my teacher convert $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?

Any help would be great

|cite|improve this question
$\endgroup$
7
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank you! It's very clear although, I'm not sure on why do you do the complementation on the -A-D? Is there any particular reason? Also the expression is actually derived from K-maps, I'm just not sure how to get the CNF expression out of K-maps $\endgroup$ – Stupid Oct 23 '14 at 8:24
  • $\begingroup$ @Stud Which line? $\endgroup$ – Chantry Cargill Oct 23 '14 at 8:25
  • $\begingroup$ ¬(¬A¬B+¬A¬D(¬B+B)+B¬D) Complementation line. I understand you can multiply by -B+B since it equals 1 and it doesn't change everything. I'm just not sure why do you choose to complement the B+-B with the -A-D, why not the -A-B or B-D? Perhaps using a different set of complementation? such as A-A or D-D? $\endgroup$ – Stupid Oct 23 '14 at 8:28
  • $\begingroup$ I noticed that the two other terms contained $B$ and $\neg B$ which told me that the middle term could be eliminated due to the way the terms were matched. If I'm going to be honest, it was mainly intuition and reasoning logically. It's a trick that you can use sometimes when you're not sure how to eliminate terms. $\endgroup$ – Chantry Cargill Oct 23 '14 at 8:32
  • $\begingroup$ Ahhhh I don't quite see that the first place. Thanks for pointing it out, also thanks for the help! $\endgroup$ – Stupid Oct 23 '14 at 8:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.