0

I try to transform some formulas into CNF and DNF but I am not sure how to use distributivity Law here.

Given: $$ ((C \lor D) \land (A\rightarrow D)) <-> (C \rightarrow A ) $$

I applied the rules for Implication and Biimplication and transformed it into NNF:

$$ (((\lnot C \land \lnot D) \land (A\land \lnot D)) \lor \lnot C \lor A) \land ((C \land \lnot A) \lor (C \lor D) \land (\lnot A \lor D)) $$

I knew that I have now to use Distributivity to get CNF and DNF, but I am not sure how to do it properly. I began with it and are already on the 2nd page, since I always get more Clauses :O.

Nemos
  • 31

1 Answers1

0

For an expression with just three variables, the easiest way is probably to write down the truth table. This directly represents the (non-optimized) DNF.

CNF: d & (a+!c)

DNF: ad + !cd

Karnaugh map:

             ac
       00  01  11  10
      +---+---+---+---+
   0  | 0 | 0 | 0 | 0 |
d     +---+---+---+---+
   1  | 1 | 0 | 1 | 1 |
      +---+---+---+---+

You get the CNF by looking at all terms with output value 0. Inverting all input literals gives you the CNF clauses.

Axel Kemper
  • 4,943
  • Thank´s. But I would like to knew it with the rules since I cannot be sure that I always have three Variables. So, KV is not practicable. – Nemos Nov 27 '15 at 00:22
  • For implication, you could translate "C implies A" to "A or not C" and apply the usual rules. Simililarly, you could translate bi-implication/equivalence into an and/or/not expression. – Axel Kemper Nov 27 '15 at 06:40
  • Heh? I have done that already in my starting Post. I only need to know how to apply Distibutivity Law. – Nemos Nov 27 '15 at 13:08