# Convert to Conjunctive Normal Form exercise

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)

$$1.¬(((a→b)→a)→a)$$
$$2.¬((p→(q→r)))→((p→q)→(p→r))$$

• 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 $?$ – Manx Nov 22 '19 at 0:40
• 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) – HellfireWorld Nov 22 '19 at 0:53
• 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))$$ – Manx Nov 22 '19 at 0:58
• Sorry for my bad syntax I am new here... they are 2 different exercises – HellfireWorld Nov 22 '19 at 0:59
• Should I wait? I would be really thankful if you could help – 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
• @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. – Manx Nov 22 '19 at 11:28