0
$\begingroup$

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. ?
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – астон вілла олоф мэллбэрг Mar 23 '16 at 13:38
0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Yes, thanks a lot for your answer i will manage the rest. I didn't know i could use distributive law, since two of them were not mended into parentheses... Eg . (P ∧ Q) ∨ (R ∧ S) ∨ (T ∧ U) and not like: ((P ∧ Q) ∨ (R ∧ S)) ∨ (T ∧ U) $\endgroup$ – George Mar 23 '16 at 14:37

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.