Converting formula from CNF to DNF How do i convert this formula from CNF to DNF?


*

*$(¬a \vee b) ∧ (¬b ∨ c) ∧ (¬a ∨ ¬c)$

*$(¬a ∨ b) ∧ (¬b ∨ c) ∧ ¬(a ∧ c)$ DeMorgan

*?

 A: 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?
A: 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:

*

*CNF: you take truth rows and do an $\lor$ (disjunction) of those rows-defined assignments

*DNF: you take false rows and do an $\land$ (conjunction) of the negation of each variable in those rows-defined assignments

