1
$\begingroup$

I have a few question about converting forms to DNF, CNF and from CNF to DNF.

1) How can I convert this to DNF $(p \vee q) \wedge (q \vee \neg r) $

2) How can I convert this to CNF $(p \wedge q) \vee (q \wedge\neg r)$

3) Is there any fast way to convert one form from CNF to DNF or DNF to CNF?

$\endgroup$
  • $\begingroup$ In second item you supposed $\wedge$ in a second parentheses? $\endgroup$ – Michael Galuza Jul 1 '15 at 17:52
  • $\begingroup$ yes, my fault, i edited $\endgroup$ – hadson172 Jul 1 '15 at 18:02
1
$\begingroup$

$$ 1.\quad (p\vee q)\wedge (q\vee\neg r) = q\wedge(p\vee q) \vee\neg r\wedge(p\vee q) = q \vee \neg r p\vee \neg rq = q\vee p\neg r $$ $$ 2. \quad (p\wedge q)\vee (q\wedge\neg r) = q(p\vee\neg r) $$

$\endgroup$
  • $\begingroup$ Could you explain which rules you used to make form like this? $\endgroup$ – hadson172 Jul 1 '15 at 18:03
  • $\begingroup$ @hadson172, I used: $a\wedge(b\vee c) = a\wedge b\vee a\wedge c$ (and vise versa), $a\wedge a = a$, $a\wedge (a\vee b)=a$. $\endgroup$ – Michael Galuza Jul 1 '15 at 18:16
1
$\begingroup$

This is mechanized in Maple. For example,

with(Logic):
Export(Normalize(`&and`(`&or`(p, q), `&or`(q, `&not`(r))))), form = DNF));

$$ p \land q \lor p \land \neg r \lor q \lor q \land \neg r $$ See ?Logic for info.

PS. It should be noted that the original Maple input is not exactly represented in the above code.

$\endgroup$

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.