How do i convert this formula from CNF to DNF?
- $(¬a \vee b) ∧ (¬b ∨ c) ∧ (¬a ∨ ¬c)$
- $(¬a ∨ b) ∧ (¬b ∨ c) ∧ ¬(a ∧ c)$ DeMorgan
- ?
How do i convert this formula from CNF to DNF?
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:
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?