The conditional statement is

$[(p \rightarrow q) \land (q \rightarrow r)] \rightarrow (p \rightarrow r)$

Here are the steps I took in an attempt to prove the above statement a tautology, but I can't seem to understand what kind of reasoning I have to use to complete this problem.

LINK TO A TABLE OF LOGICAL EQUIVALENCES FOR YOUR CONVENIENCE : http://en.wikipedia.org/wiki/Logical_equivalence

$\lnot[(p \rightarrow q) \land (q \rightarrow r)] \lor (p \rightarrow r)$ (Because $p \rightarrow q = \lnot p \lor q$ )

$\lnot (p \rightarrow q) \lor \lnot ( q \rightarrow r) \lor (p \rightarrow r)$ (Because $ \lnot(p \land q) = \lnot p \lor \lnot q $ )

At this point I just isolate and focus on the portion of the above that is:

$\lnot ( q \rightarrow r) \lor (p \rightarrow r)$

Then that can become:

$ (p \rightarrow r)\lor \lnot ( q \rightarrow r)$ (Because of the commutative law)

$(p \rightarrow r) \lor q \land \lnot r$ (Because $\lnot(p \rightarrow q) = p \land \lnot q$)

$(p \rightarrow r) \lor \lnot r \land q$ (Because of the commutative law)

$(\lnot p \lor r) \lor \lnot r \land q$ (Because $p \rightarrow q = \lnot p \lor q$)

$\lnot p \lor ( r \lor \lnot r) \land q$ (Because of the associative law)

$\lnot p \lor T \land q$ (Because of negation)

$T \land q$ (Because $\lnot p \lor T$ is true no matter what)

I don't know how to get from this point to "and this is why the original conditional statement is true no matter what".


$(p \rightarrow r) \lor (q \land \lnot r)$ is not equivalent to $((p \rightarrow r) \lor \lnot r) \land q$.

$\lnot ( q \rightarrow r) \lor (p \rightarrow r)=\text{(...as you did...)}=(p \rightarrow r) \lor (q \land \lnot r)$

  • $=(\lnot p \lor r) \lor (q \land \lnot r)$
  • $=(\lnot p \lor (r \lor (q \land \lnot r))$
  • $=(\lnot p \lor ((r \lor q) \land (r \lor \lnot r)))$
  • $=(\lnot p \lor (r \lor q))$

So $\lnot (p \rightarrow q) \lor \lnot ( q \rightarrow r) \lor (p \rightarrow r)$

  • $=\lnot (p \rightarrow q) \lor (\lnot p \lor (r \lor q))$
  • $=(p \land \lnot q) \lor \lnot p \lor r \lor q$
  • $=((p \lor \lnot p) \land (\lnot q \lor \lnot p)) \lor r \lor q$
  • $=\lnot q \lor \lnot p \lor r \lor q$
  • $=(\lnot q \lor q) \lor \lnot p \lor r$
  • $=T$

I used the distributive law $p \lor (q \land r)=(p \lor q) \land (p \lor r)$ but the fact we needed is actually $p \lor (\lnot p \land q)=p \lor q$, which I believe is the absorption law.

  • $\begingroup$ I didn't... it starts a new statement, the one you left off when you said to focus on the right two terms. $\endgroup$ – user1537366 Jan 25 '15 at 7:29
  • $\begingroup$ I'm sorry I just don't see how (-p v (r v q)) is equivalent to -(q -> r) v ( p -> r) $\endgroup$ – user11892 Jan 25 '15 at 9:29
  • $\begingroup$ @RogerVillanueva I proved it in the previous lines. You focused on those terms so I just did the same! $\endgroup$ – user1537366 Jan 25 '15 at 9:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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