Can the logic associative law be applied here?

Question

$\big(p \rightarrow (q \rightarrow r)\big)$ is logically equivalent to $\big(q \rightarrow (p \rightarrow r)\big)$

I am a little confused when dealing with the 'implies' operator $\rightarrow$ and the logic laws. To prove that these are logically equivalent, can I just apply associative law and be done with it? Or do I need to apply more laws?

Answer 1

Since $P \rightarrow Q$ is equivalent to $\neg P \vee Q$, you can eliminate all implications and use the fact that $\vee$ is associative.

$p \rightarrow (q \rightarrow r)$

$\neg p \vee (q\rightarrow r)$

$\neg p \vee (\neg q \vee r)$

$(\neg p \vee \neg q) \vee r \quad$ by associativity

$(\neg q \vee \neg p) \vee r \quad$ by commutativity

Do the same to $q \rightarrow (p \rightarrow r)$ to get $(\neg q \vee \neg p) \vee r$.

Answer 2

$\neg p \vee (\neg q \vee r) \equiv \neg p \vee \neg q \vee r \equiv \neg q \vee \neg p \vee r \equiv \neg q \vee (\neg p \vee r) $

The key is that a implies b is the same as not a or b.

Answer 3

If your logic laws include $a\rightarrow(b\rightarrow c)\equiv (a\wedge b)\rightarrow c$ (which is in fact a correct logical equivalence, called the law of importation), that could be another approach.

Answer 4

First, associativity fails to hold for a chain of implications:

$$p\rightarrow (q \rightarrow r) \not \equiv (p \rightarrow q) \rightarrow r$$

Rather, what we can use is the following equivalence $$p \rightarrow (q\rightarrow r) \iff (p\land q) \rightarrow r$$ This equivalence is a valid rule of replacement in propositional logic, and is known as importation/exportation, depending on the direction of the biconditional that is being cited.

Using this equivalence, a very concise proof of your equivalence follows:

$$\begin{align} \big(p \rightarrow (q \rightarrow r)\big) & \equiv (p\land q) \rightarrow r \tag{1}\\ & \equiv (q\land p) \rightarrow r\tag{2}\\ &\equiv q\rightarrow(p \rightarrow r)\tag{3} \end{align}$$

$(1),\; (3)$ by importation,exportation,

$(2)$ by the commutativity of $\land$.

Answer 5

$\big(p \rightarrow (q \rightarrow r)\big)$ is logically equivalent to $\big(q \rightarrow (p \rightarrow r)\big)$

Hint for alternative proof suggestion:

'$\to$'

1. $p \rightarrow (q \rightarrow r)$ (Premise)

2. $q$ (Premise)

3. $p$ (Premise)

4. $q \rightarrow r$ (Detachment, 1, 3)

etc.