0
$\begingroup$

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?

  • 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?2012-04-23

3 Answers 3

1

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

1

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?

  • 0
    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 http://en.wikipedia.org/wiki/Truth_table#Logical_implication for more information and an example.2012-04-23
1

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.