Converting formula from CNF to DNF

20.1k Views Asked by At

How do i convert this formula from CNF to DNF?

  1. $(¬a \vee b) ∧ (¬b ∨ c) ∧ (¬a ∨ ¬c)$
  2. $(¬a ∨ b) ∧ (¬b ∨ c) ∧ ¬(a ∧ c)$ DeMorgan
  3. ?
2

There are 2 best solutions below

1
On BEST ANSWER

In both CNF and DNF, negations need to be right next to the propositional variables, just as in your original formula. Thus using DeMorgan to push negations out is a bad choice, as they in the end still have to go back in. Instead use the distributive law (where I use the notation $\approx$ for saying two formulas are equivalent):

$$p \wedge(r\vee s) \approx (p\wedge r)\vee (p\wedge s)$$ If we use this formula on $(\neg a\vee b)\wedge(\neg b\vee c)$ (and consider that $p$ is $(\neg a\vee b)$, $r$ is $\neg b$ and $s$ is $c$) we get $$(\neg a\vee b)\wedge(\neg b\vee c) \approx \big((\neg a\vee b)\wedge \neg b\big)\vee \big((\neg a\vee b)\wedge c\big)$$ Now again use the distributive law, but this time inside the parentheses: $$\big((\neg a\vee b)\wedge \neg b\big)\vee \big((\neg a\vee b)\wedge c\big)\approx \big( (\neg a \wedge \neg b) \vee (b \wedge \neg b)\big) \vee \big((\neg a \wedge c)\vee (b\wedge c) \big)$$ which we may write with fewer parentheses as $$(\neg a \wedge \neg b) \vee (b \wedge \neg b) \vee (\neg a \wedge c)\vee (b\wedge c) \approx (\neg a\wedge \neg b)\vee (\neg a\wedge c)\vee (b\wedge c)$$ Now this is on disjunctive normal form, however this is not your whole exercise, this is just the left part. That is I have shown that $$(\neg a\vee b)\wedge (\neg b\vee c)\wedge (\neg a \vee \neg c)\approx \Big((\neg a\wedge \neg b)\vee (\neg a\wedge c)\vee (b\wedge c)\Big)\wedge (\neg a\vee \neg c)$$ To finnish the exercise you have to do the same method as I just showed you again on this formula. That is apply the distributive law a couple of more times. Can you do that?

0
On

For future readers, CNF to DNF (or the opposite) is not trivial (as far as I know), for short formulas you can use the truth table of the formula, where for:

  1. CNF: you take truth rows and do an $\lor$ (disjunction) of those rows-defined assignments
  2. DNF: you take false rows and do an $\land$ (conjunction) of the negation of each variable in those rows-defined assignments