Question

Prove the following holds without using a truth table.
(p → q) ⇒ [(q → r) → (p → r)]

Answer 1

R.H.S=(q->r)->(p->r)
=(~qvr)->(~pvr) |since: p->q=~pVq------>(1)
=~(~qvr)v(~pvr)
=(q^~r)v(~pvr)
=(~p)v(q^(r v~r) |pV~p=1 or T
=(~p)V(q^1)
=~pvq since (1)
=p->q
=L.H.S
Hence LHS=RHS

Answer 2

Regrouping the R is where I messed up. Thank you!

Answer 3

The main key to this problem is to understand statements of the form A implies B, which are written as A →B (and also A ⇒ B).

A implies B means that whenever A is true, B must be true.

Let's unpack that a bit: Whenever you try to prove a statement in the form A → B. The way to do it is to assume A and then prove B.

As the statement you want to prove is a nested collection of implications, you simply need to apply the previous sentence several times (recursively).

So, how do we interpret your entire statement as A → B? What is A, and what is B in your whole statement?

Your statement is:
(p → q) ⇒ [(q → r) → (p → r)]

So p → q is A. What then is B?

It's the statement in brackets. So let's assume A (the statement p → q) and try to prove B (which is [(q → r) → (p → r)] ).

Let's rewrite B, which itself is an implication (i.e. a statement of the form A → B):
(q → r) → (p → r)

What is A in this statement? It's q → r. Let's assume it's true. We then need to prove the B in this statement (which is p → r).

So, it comes down to proving this final implication:
p → r.

:) You probably are getting the hang of this by now. What is it that we need to assume? (i.e. what is A in this statement?) And what is B?

A is p, and B is r.
So we assume p is true and want to prove that r is too.

Let's recap the assumptions we've made so far:
p → q
q → r
p

So then, can we now assert that r is true?

Yes, we can. Because p is true and so is p → q, q also must be true. And now, since q is true, r must be true because q → r.