I got confused in some exercises I need to convert the following to CNF step by step(I need to prove it with logical equivalence)


  • $\begingroup$ What rules you can use, and what you had tried, by the way it's a tautology $\dots$ you can use truth table method, or you want to prove it's a tautology use logical equivalence or natural deduction or any other valid methods $?$ $\endgroup$ – Manx Nov 22 '19 at 0:40
  • $\begingroup$ I just learned them and I tried so many times but I can't convert them because i am getting confused with so many negation out of parenthesis in demorgan step I don't need truth tables for example (¬p → q) → (q → ¬r) Propositional Logic Solution. ≡ ¬(¬p → q) ∨ (q → ¬r) ≡ ¬(p ∨ q) ∨ (¬q ∨ ¬r) ≡ (¬p ∧ ¬q) ∨ (¬q ∨ ¬r) ≡ (¬p ∨ ¬q ∨ ¬r) ∧ (¬q ∨ ¬r) $\endgroup$ – HellfireWorld Nov 22 '19 at 0:53
  • $\begingroup$ I see $\dots$ so you want to prove it with logical equivalence, did you missed an 'and' in your expression:$$ ¬(((a→b)→a)→a)\color{orange}\land¬((p→(q→r)))→((p→q)→(p→r))$$ $\endgroup$ – Manx Nov 22 '19 at 0:58
  • $\begingroup$ Sorry for my bad syntax I am new here... they are 2 different exercises $\endgroup$ – HellfireWorld Nov 22 '19 at 0:59
  • $\begingroup$ Should I wait? I would be really thankful if you could help $\endgroup$ – HellfireWorld Nov 22 '19 at 1:26

Use Logical equivalences we have: \begin{align} &¬(((a→b)→a)→a)\\ &\equiv\neg(\neg(\neg(\neg a \lor b)\lor a)\lor a)\tag*{Conditional equivalence}\\ &\equiv((a \land\neg b)\lor a)\land\neg a\tag*{De Morgan's law}\\ &\equiv((a\lor a) \land(\neg b\lor a))\land\neg a\tag*{Distributive law}\\ &\equiv(a \land(\neg b\lor a))\land\neg a\tag*{Idempotent law}\\ &\equiv((\neg b\lor a)\land a)\land\neg a\tag*{Commutative law}\\ &\equiv(\neg b\lor a)\land(a\land\neg a)\tag*{Associative law}\\ &\equiv(\neg b\lor a)\land\bot\tag*{Negation law}\\ &\equiv\bot\tag*{Identity law}\\ \\ &¬((p→(q→r)))→((p→q)→(p→r))\\ &\equiv(\neg p\lor(\neg q\lor r))\tag*{Conditional equivalence}\\ &\lor(\neg(\neg p\lor q)\lor(\neg p\lor r))\\ &\equiv(\neg p\lor(\neg q\lor r))\tag*{De Morgan's law}\\ &\lor((p\land\neg q)\lor(\neg p\lor r))\\ &\equiv(\neg p\lor(\neg q\lor r))\tag*{Distributive law}\\ &\lor((p\lor(\neg p\lor r))\land(\neg q\lor(\neg p\lor r)))\\ &\equiv(\neg p\lor(\neg q\lor r))\tag*{Associative law}\\ &\lor(((p\lor\neg p)\lor r)\land(\neg q\lor(\neg p\lor r)))\\ &\equiv(\neg p\lor(\neg q\lor r))\tag*{ Negation law}\\ &\lor((\top\lor r)\land(\neg q\lor(\neg p\lor r)))\\ &\equiv(\neg p\lor(\neg q\lor r))\tag*{Domination law}\\ &\lor(\top\land(\neg q\lor(\neg p\lor r)))\\ &\equiv(\neg p\lor(\neg q\lor r))\lor(\neg q\lor(\neg p\lor r))\tag*{Identity law}\\ &\equiv((\neg p\lor\neg q)\lor r)\lor((\neg q\lor\neg p)\lor r)\tag*{Associative law}\\ &\equiv((\neg p\lor\neg q)\lor r)\lor((\neg p\lor\neg q)\lor r)\tag*{Commutative law}\\ &\equiv(\neg p\lor\neg q)\lor r\tag*{Idempotent law}\\ \end{align}

Hence $(1)$ has $\bot$ as its minimal CNF & DNF, and $(2)$ has $(\neg p\lor\neg q)\lor r$ as its minimal CNF & DNF

  • $\begingroup$ really thank you, I will try to understand it now because I really messed up with the negations and parenthesis $\endgroup$ – HellfireWorld Nov 22 '19 at 1:43
  • $\begingroup$ Manx correct me if I am wrong in the second exercise the 4rth equals its Associative law, after distributive? also I haven't done the negation law and identity law $\endgroup$ – HellfireWorld Nov 22 '19 at 11:17
  • $\begingroup$ @HellfireWorld you are right, the distributive law is a typo, was trying to copy the previous line, but forgot to change the tag, thanks $\endgroup$ – Manx Nov 22 '19 at 11:20
  • $\begingroup$ nice they haven't learned me the identity law and negation law with ⊤ ⊥ is it correct to skip those steps in the second ? and in the first one should i let it ≡(¬b∨a)∧(a∧¬a) $\endgroup$ – HellfireWorld Nov 22 '19 at 11:23
  • $\begingroup$ @HellfireWorld If you have rules like $(p\lor \neg p)\land q\equiv q$, you can use this instead of the Identity laws, but $\top$ simply stand for true and $\bot$ for false, and $(¬b∨a)∧(a∧¬a)$ is in CNF form, but not in minimal CNF form, since it can still be simplify further. $\endgroup$ – Manx Nov 22 '19 at 11:28

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.