# Converting formula from CNF to DNF

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. ?
• What have you done so far? This site is strictly not for completion of homework, hence I suggest you show us some of your attempts in this question. – астон вілла олоф мэллбэрг Mar 23 '16 at 13:38

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?