Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is $(p \to q) \to r$ logically equivalent to $p \to (q \to r)$?

I try to simply each one, I got $\lnot ( \lnot p \lor q) \lor r$ and $\lnot p \lor ( \lnot q \lor r)$ respectively,

then I am stuck. Does that mean they aren't equivalent?

How do I know if expression cannot be further simply? Any tips to solve such questions?

I really appreciate your advise!

share|improve this question
3  
You don't even need to do any simplification if you want a proof of equivalence; just work out the truth tables for each statement and see if they're the same. –  David Zhang Sep 5 '13 at 13:56

5 Answers 5

up vote 8 down vote accepted

Since you've gotten to:

$$\lnot ( \lnot p \lor q) \lor r\tag{1}$$ $$ \lnot p \lor ( \lnot q \lor r)\tag{2},$$

we can indeed simplify further. First, by associativity, note that $$\lnot p \lor ( \lnot q \lor r)\equiv (\lnot p \lor \lnot q) \lor r\tag{2} $$

Next, using DeMorgan's Laws,

$$\lnot (\lnot p \lor q) \lor r \equiv (p \land \lnot q) \lor r\tag{1}$$ $$(\lnot p \lor \lnot q) \lor r\equiv \lnot(p \land q) \lor r\tag{2}$$

Finally, we need only see that the clauses $$p \land \lnot q \not\equiv \lnot (p \land q)$$ to see that $(1)$ and $(2)$ are not equivalent,

Indeed, when $p$ is F(alse), $p \land \lnot q \equiv F$ and $\lnot(p \land q) \equiv T$, as we can see nicely via the corresponding truth tables (source: Wolfram Alpha):

enter image description here

enter image description here

share|improve this answer
1  
Such a nice write up +1 –  Amzoti Sep 6 '13 at 0:16

No, compare $(p\implies p)\implies r$, which is equivalent to $r$, and $p\implies (p\implies r)$, which is equivalent to $p\implies r$.

share|improve this answer

It is not. Suppose $p$, $q$, $r$ are false. Then $p \rightarrow q$ and $q \rightarrow r$ are true, so $(p\rightarrow q)\rightarrow r$ is false and $p\rightarrow (q\rightarrow r)$ is true.

share|improve this answer

Good question!

No.

The second statement, namely $$p \rightarrow (q \rightarrow r)$$ can be read: "In the presence of $p$, we have that $q$ implies $r$."

Turns out this is the same as saying: "In the presence of both $p$ and $q$, we have $r$." That is

$$(p \wedge q) \rightarrow r.$$

The first statement is a little harder put words to. In the comments, Lord Farin suggests the phrasing: "If $p$ necessitates $q$, then $r$."

A bit of symbol pushing shows its equivalent to:

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

which might shed some light on its meaning. Substituting in $q = \bot$ (a contradiction) we obtain

$$(p \vee r).$$

So if $p$ necessitates a contradiction implies $r$, then either $p$ or $r$. And vice versa.

share|improve this answer
    
How about "If $p$ necessitates $q$, it follows that $r$?" A typical case is when $q$ is a contradiction and $r = \neg p$, the negation of $p$. –  Lord_Farin Sep 5 '13 at 10:43
    
@Lord_Farin, thanks I edit my answer in line with your comment. Still not totally satisfied though. Feel free to edit it as you see fit. –  goblin Sep 5 '13 at 10:49

The second formula is "if $p$, then: if $q$ then $r$" which is equivalent to "if $p$ and $q$, then $r$". So it is equivalent to $$(p\land q) \implies r.$$

On the other hand, the first is "if $p$ implies $q,$ then $r$". As we know any implication "$p$ implies $q$" is equivalent to "not $p$ or $q$", so our formula is "if not $p$ or $q$, then $r$", which written with symbols is: $$(\neg p \lor q) \implies r.$$

Because of course $\neg p \lor q \not\equiv p \land q$, the two formulas are not equivalent.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.