# Proof via equivalence laws; $(a \lor b) \equiv (b \lor a)$?

Is this a correct progression to prove that $p \rightarrow (q \rightarrow r) \equiv q \rightarrow (p \rightarrow r)$?

\begin{align} p \rightarrow (q \rightarrow r) & \equiv p \rightarrow (q \rightarrow r) \\ & \equiv \neg p \lor (q \rightarrow r) \text{ implication law}\\ & \equiv \neg p \lor (\neg q \lor r) \text{ implication law}\\ & \equiv \neg q \lor (\neg p \lor r) \text { associative law}\\ & \equiv \neg q \lor (p \rightarrow r) \text{ implication law}\\ p \rightarrow (q \rightarrow r)& \equiv q \rightarrow (p \rightarrow r) \text{ implication law} \end{align}

For step 4, I've interpreted Associative Laws assuming $(q \lor r) \equiv (r \lor q)$. Is this an assumption I can make?

$$\neg p \lor (\neg q \lor r) \equiv (\neg p \lor \neg q) \lor r \equiv \neg q \lor (\neg p \lor r)?$$

Can I interpret Associative Laws such that $a \lor (b \lor c) \equiv \text{either } b \lor (a \lor c) \text{ or } c \lor (a \lor b)?$

• Wouldn't a truth table help here; you can try to falsify one side and have the other side be true, to falsify the statement itself. – user99680 Nov 4 '13 at 9:31
• Looks good to me. – Hunan Rostomyan Nov 4 '13 at 9:34
• @user99680, truth tables are far from accurate because some of the nuance of the logic can yield $\top$ for both sides even if both sides are not logically equivalent. – gator Nov 4 '13 at 9:36
• Why would you be asked to prove a simple relation using more advanced identities? This is what's wrong with math. – Chuck Franklin Nov 4 '13 at 9:36
• @AustinRannow, it's a course in introductory logic. While it may seem elementary to some, I'm trying to practice for a test and it helps to know the logic behind it. – gator Nov 4 '13 at 9:39

## 1 Answer

This one doesn't rely on the associativity of disjunction:

If you replace Qs with Ps everywhere you'll have the other direction.

Explanation. To show that $p \rightarrow (q \rightarrow r) \equiv q \rightarrow (p \rightarrow r)$, it will suffice to do two things:

1. assume $p \rightarrow (q \rightarrow r)$ and derive $q \rightarrow (p \rightarrow r)$
2. assume $q \rightarrow (p \rightarrow r)$ and derive $p \rightarrow (q \rightarrow r)$

The image shows how (1) is done. We assume $p \rightarrow (q \rightarrow r)$. Now we want to derive something (viz. $q \rightarrow (p \rightarrow r)$) that is a conditional, so we assume its antecedent (viz. $q$) with the hope of deriving its consequent (viz. $(p \rightarrow r)$). But that consequent is also a conditional, so to derive that we assume its antecedent, namely: $p$. Now $p$ with the initial assumption (Premise 1 in the image), by modus ponens gives us $(q \rightarrow r)$ (this is Premise 4 in the image). Next we use the $q$ we assumed (in Premise 2) with that $(q \rightarrow r)$, by modus ponens again, to obtain $r$. Now, to wrap things up. Since we assumed $p$ and obtained $r$, we can conclude that $p \rightarrow r$ (Premise 6). Lastly, since we assumed $q$ and obtained $p \rightarrow r$, we can conclude that $q \rightarrow (p \rightarrow r)$.

The same thing is done for step (2).

• I haven't come across this kind of method before; I don't particularly understand what the image you've linked is trying to represent. – gator Nov 4 '13 at 9:47
• I'll explain what's going on with words in a minute. – Hunan Rostomyan Nov 4 '13 at 9:48