Prove or disprove (p→q)→r and p→(q→r) are equivalent using Logical Equivalence Laws (no truth table)

discrete mathematicslogic

I was able to show using a truth table that the two statements (p→q)→r and p→(q→r) are NOT equivalent, I need to now verify using equivalence laws, and I'm stuck. Any guidance would be very appreciated. Here's what I got so far;

(p → q) → r ≡ (¬p ∨ q) → r — By Logical equivalence involving conditional statements

(¬p ∨ q) → r ≡ ¬(¬p ∨ q) ∨ r — By Logical equivalence involving conditional statements

¬(¬p ∨ q) ∨ r ≡ (¬¬p ∧ ¬q) ∨ r — By De Morgans Law

(¬¬p ∧ ¬q) ∨ r ≡ (p ∧ ¬q) ∨ r — By Double Negation Law

Where do I go from here?

Best Answer

I present one demonstration that the given propositions are not equivalent using the equivalences of propositional calculus only.

Since conjunction and disjunction have full properties of commutativity, associativity and distributivity, I shall omit parentheses when there is no risk of ambiguity for the sake of better readability:

  1. $\qquad (p\rightarrow q)\rightarrow r$
  2. $\qquad\equiv\neg(\neg p\vee q)\vee r$
  3. $\qquad\equiv(p\wedge\neg q)\vee r$
  4. $\qquad\equiv((p\wedge\neg q)\vee (p\wedge\neg p))\vee r$
  5. $\qquad\equiv((p\wedge (\neg q\vee\neg p))\vee r$
  6. $\qquad\equiv(p\vee r)\wedge\mathbf{(\neg q\vee\neg p\vee r)}$
  1. $\qquad p\rightarrow (q\rightarrow r)$
  2. $\qquad\equiv\neg p\vee\neg q\vee r$
  3. $\qquad\equiv\neg p\vee((\neg q\vee r)\wedge (\neg r\vee r))$
  4. $\qquad\equiv\neg p\vee((\neg q\wedge\neg r)\vee r)$
  5. $\qquad\equiv(\neg p\vee(\neg q\wedge\neg r))\vee r$
  6. $\qquad\equiv((\neg p\vee\neg q)\wedge(\neg p\vee\neg r))\vee r$
  7. $\qquad\equiv(\neg p\vee\neg q\vee r)\wedge (\neg p\vee\neg r\vee r)$
  8. $\qquad\equiv\mathbf{\neg p\vee\neg q\vee r}$

The first of the given propositions has the disjunctive form of the second one (bold-faced) as one of its conjuncts. The other conjunct makes the resultant truth-table differ from the second proposition unless it is a tautology, which is not.

Related Question