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.

Determine whether the following pairs of statements are logically equivalent or not. Give a reason.

(i) $p \to (q \to r)$ and $(p \to q) \to r$

(ii) $p \to (q \to r)$ and $q \to (p \to r)$

Can anyone point me in the right direction for this one?

share|improve this question
3  
The "right direction" will depend on the exact framework on which you are working. Do you have a list of axioms and a set of inference rules? (Which ones?) Do you have truth tables and are truth tables considered valid proofs of equivalence? –  Arturo Magidin Apr 23 '12 at 16:30

3 Answers 3

If you know how to construct truth tables (and if you know what "logically equivalent" means), that's one direction.

share|improve this answer

As the above answer suggests, try constructing the truth tables for the expressions and see if they are the same. The answer to part i is no, try setting p False and R False and see what happens. Can you work out the answer to part ii using the same method?

share|improve this answer
    
Can you explain how to construct the first truth table? –  JamieB Apr 23 '12 at 17:56
    
As said by countinghaus, truth tables consider every possible true/false assignment to each variable p, q and r. so you simply draw a table with the value of p, q, and r in it, you can then work out the value for q implies r for each row and then the value for p implies (q implies r) and similarly for the second expression, if the tables are the same then they are equivalent, but you will find that they differ on the row I mentioned. Have a look at en.wikipedia.org/wiki/Truth_table#Logical_implication for more information and an example. –  Sam Jones Apr 23 '12 at 22:00

Here is the technique. I will work with the first one. I find it helpful to think out loud "a is false or b is true" when I see $a \to b$ (as always, putting "or" between two statements doesn't preclude the possibility that both hold).

Case one: $p$ is true, $q$ is true, $r$ is true. Then $q \to r$ is true, so $p \to (q \to r)$ is true. Also, $r$ is true, so $(p \to q) \to r$ is true. Therefore the two statements take the same truth value in this case.

Case two: $p$ is false, $q$ is true, $r$ is true. The same logic as in case one shows that both statements are true (because in our analysis of case one, it never mattered that $p$ was true).

There are a total of eight cases to consider (because there are $8 = 2^3$ different ways to assign the values true or false to the 3 variables $p, q, r$), so you should check out the other 6. If the two statements agree in EVERY case, then they are logically equivalent. If they disagree in ANY case, they are not logically equivalent (and so you can stop listing the cases).

Because this process is a little tedious, most people abbreviate the cases in truth tables, which you can look up the formatting for in your book or on the Wikipedia.

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.