# Boolean algebra - Converting DNF form to CNF

I've tried at least a dozen ways to convert this DNF to CNF, yet I always end up with something unusable. Here is the DNF:

$$y= (A \wedge B \wedge \neg C \wedge D) \vee (A \wedge B \wedge C \wedge \neg D) \vee (\neg A \wedge C \wedge D) \vee (\neg A \wedge \neg C \wedge \neg D) \vee (\neg B \wedge C \wedge D) \vee (\neg B \wedge \neg C \wedge \neg D).$$

Could you please help me to at least get on the right track?

HINT

Are you familiar with FOIL, that says that $$(A+B)(C+D) = AC+AD+BC+BD$$?

Well, that principle generalizes more larger or more terms, simply by systematically taking all possible ways of taking 1 member from each term. For example:

$$(A+B + E)(C+D) = AC+AD+BC+BD + EC + ED$$

or

$$(A+B + E)(C+D + F) = AC+AD+AF+BC+BD + BF+EC + ED+EF$$

or

$$(A+B)(C+D)(E+F) = ACE+ACF+ADE+ADF+BCE+BCF+BDE+BDF$$

See how this works?

Well, using Distribution of conjunctions ovder disjunctions (or vice versa) you can do the exact same thing. For example:

$$(A \lor B \lor E) \land (C \lor D) = (A \land C) \lor (A \land D) \lor (B \land C) \lor (B \land D) \lor (E \land C) \lor (E \land D)$$

$$(A \land B) \lor (C \land D) \lor (E \land F) = (A \lor C \lor E) \land (A \lor C \lor F) \land (A \lor D \lor E) \land (A \lor D \lor F) \land (B \lor C \lor E) \land (B \lor C \lor F) \land (B \lor D \lor E) \land (B \lor D \lor F)$$

Etc.

Of course, in your case that means you get $$4 \cdot 4 \cdot 3 \cdot 3 \cdot 3 \cdot 3 = 1296$$ terms ....

... so, we probably want to be a bit smarter about this....

OK, let's first establish a basic equivalence that will be quite useful:

$$(C \land D) \lor (\neg C \land \neg D) \overset{Distribution}{=}$$

$$(C \lor \neg C) \land (C \lor \neg D) \land (D \lor \neg C) \land (D \lor \neg D) \overset{Complement}{=}$$

$$\top \land (C \lor \neg D) \land (D \lor \neg C) \land \top \overset{Identity}{=}$$

$$(C \lor \neg D) \land (\neg C \lor D)$$

So, we have:

$$(C \land D) \lor (\neg C \land \neg D) = (C \lor \neg D) \land (\neg C \lor D) \tag{1}$$

and, by duality of the $$\land$$ and the $$\lor$$, we therefore also have:

$$(C \lor D) \land (\neg C \lor \neg D) = (C \land \neg D) \lor (\neg C \land D) \tag{2}$$

OK, with that:

$$(A \land B \land \neg C \land D) \lor (A \land B \land C \land \neg D) \lor (\neg A \land C \land D) \lor (\neg A \land \neg C \land \neg D) \lor (\neg B \land C \land D) \lor (\neg B \land \neg C \land \neg D) \overset{Commutation, Association}{=}$$

$$[(A \land B \land \neg C \land D) \lor (A \land B \land C \land \neg D)] \lor [(\neg A \land C \land D) \lor (\neg B \land C \land D)] \lor [(\neg A \land \neg C \land \neg D) \lor (\neg B \land \neg C \land \neg D)]\overset{Distribution}{=}$$

$$[(A \land B) \land ((\neg C \land D) \lor (C \land \neg D))] \lor [(\neg A \lor \neg B) \land (C \land D)] \lor [(\neg A \lor \neg B) \lor (\neg C \land \neg D)]\overset{DeMorgan}{=}$$

$$[(A \land B) \land ((\neg C \land D) \lor (C \land \neg D))] \lor [\neg (A \land B) \land (C \land D)] \lor [\neg (A \land B) \lor (\neg C \land \neg D)]\overset{Distribution}{=}$$

$$[(A \land B) \land ((\neg C \land D) \lor (C \land \neg D))] \lor [\neg (A \land B) \land ((C \land D) \lor (\neg C \land \neg D))]\overset{(1)}{=}$$

$$[(A \land B) \land ((\neg C \land D) \lor (C \land \neg D))] \lor [\neg (A \land B) \land ((C \lor \neg D) \land (\neg C \lor D))]\overset{Double \ Negation}{=}$$

$$[(A \land B) \land ((\neg C \land D) \lor (C \land \neg D))] \lor [\neg (A \land B) \land \neg \neg ((C \lor \neg D) \land (\neg C \lor D))]\overset{DeMorgan}{=}$$

$$[(A \land B) \land ((\neg C \land D) \lor (C \land \neg D))] \lor [\neg (A \land B) \land \neg ((\neg C \land D) \lor (C \land \neg D))]\overset{Distribution}{=}$$

$$=[(A \land B) \lor \neg (A \land B)] \land [(A \land B) \lor \neg ((\neg C \land D) \lor (C \land \neg D))] \land [\neg (A \land B) \lor ((\neg C \land D) \lor (C \land \neg D))] \land [((\neg C \land D) \lor (C \land \neg D)) \lor \neg ((\neg C \land D) \lor (C \land \neg D))]\overset{Complement}{=}$$

$$\top \land [(A \land B) \lor ((C \lor \neg D) \land (\neg C \lor D))] \land [\neg (A \land B) \lor ((\neg C \land D) \lor (C \land \neg D))] \land \top\overset{Identity}{=}$$

$$[(A \land B) \lor ((C \lor \neg D) \land (\neg C \lor D))] \land [\neg (A \land B) \lor ((\neg C \land D) \lor (C \land \neg D))] \overset{(2}{=}$$

$$[(A \land B) \lor ((C \lor \neg D) \land (\neg C \lor D))] \land [\neg (A \land B) \lor ((C \lor D) \land (\neg C \lor \neg D))]\overset{Distribution}{=}$$

$$[(A \land B) \lor (C \lor \neg D)] \land [(A \land B) \lor (\neg C \lor D)] \land [(\neg A \lor \neg B) \lor ((C \lor D) \land (\neg C \lor \neg D))]\overset{Distribution}{=}$$

$$(A \lor C \lor \neg D) \land (B \lor C \lor \neg D) \land (A \lor \neg C \lor D) \land (B \lor \neg C \lor D) \land (\neg A \lor \neg B \lor C \lor D) \land (\neg A \lor \neg B \lor \neg C \lor \neg D)$$

• okay i understand, i will try it. thank you – Andrej Šereš Oct 1 '19 at 19:17