2
$\begingroup$

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)?$

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – user99680 Nov 4 '13 at 9:31
  • 1
    $\begingroup$ Looks good to me. $\endgroup$ – Hunan Rostomyan Nov 4 '13 at 9:34
  • $\begingroup$ @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. $\endgroup$ – gator Nov 4 '13 at 9:36
  • $\begingroup$ Why would you be asked to prove a simple relation using more advanced identities? This is what's wrong with math. $\endgroup$ – Chuck Franklin Nov 4 '13 at 9:36
  • $\begingroup$ @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. $\endgroup$ – gator Nov 4 '13 at 9:39
1
$\begingroup$

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

enter image description here

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).

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – gator Nov 4 '13 at 9:47
  • 1
    $\begingroup$ I'll explain what's going on with words in a minute. $\endgroup$ – Hunan Rostomyan Nov 4 '13 at 9:48

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.