2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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)$

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

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.