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
add comment

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
    
Good morning, now it's 13:06 at Tunis. –  Sami Ben Romdhane Jan 10 at 12:07
add comment

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
add comment

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
add comment

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
add comment

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
add comment

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.