1

Show that $(p \to q)\land(q \to r)\to (p \to r)$ is a tautology.

How to prove this without using truth table? I think it need some existing tautologies like $p\to q\iff \neg p\lor q, \:\: p\land p\iff p,\:\:p\land q\iff q\land p$, etc, but I am sure how to do it. It would be best if someone post the complete procedure here.

Martin Sleziak
  • 53,687
Ahmed Faraz
  • 31
  • Please try to think of a more descriptive title. 99% of questions z in this site also ask for a proof of something... – Mariano Suárez-Álvarez Oct 04 '15 at 04:58
  • I edited it for him. – Akiva Weinberger Oct 04 '15 at 05:07
  • @hermes: You shouldn't add text to the answer. Edits are acceptable, adding content is not. – copper.hat Oct 04 '15 at 05:33
  • @Ahmed Faraz, you are new to this site. You should always add your own thought on how to do this problem and where you stuck. – Eugene Zhang Oct 04 '15 at 06:09
  • 1
    Your question was put on hold, the message above (and possibly comments) should give an explanation why. (In particular, this link might be useful.) You might try to edit your question to address these issues. Note that the next edit puts your post in the review queue, where users can vote to reopen this. (Therefore it would be good to avoid minor edits and improve your question as much as possible with the next edit.) – Martin Sleziak Oct 04 '15 at 10:33
  • Did you have a look on some older questions about the same equivalence? Just a few examples found after a quick search: http://math.stackexchange.com/questions/257486, http://math.stackexchange.com/questions/758111, http://math.stackexchange.com/questions/1429023, http://math.stackexchange.com/questions/279741, http://math.stackexchange.com/questions/637407. – Martin Sleziak Oct 04 '15 at 10:40
  • @MartinSleziak: Actually in this case I don't think that it is enough to look at the older questions, since none of them offer the natural natural deduction proof, which is more instructive than the boolean algebra proof or the model-theoretic approach, since as one person commented on one of the answers in one of your links, this theorem is true even in intuitionistic logic, for good reason. But I do agree that the asker should have given more of his/her thoughts, though this time I gave more benefit of doubt. – user21820 Oct 04 '15 at 13:10
  • @user21820 We will not know until the OP clarifies what they mean by: "How to prove this without using truth table?" It is possible that some of the answers posted there would be sufficient for the OP's purposes. – Martin Sleziak Oct 04 '15 at 13:46

2 Answers2

2

There are infinitely many different possible formal systems, each with different rules and axioms. So technically your question cannot be answered. However, here is the standard way of proving the tautology using natural deduction Fitch-style. $\def\imp{\rightarrow}$

If $( p \imp q ) \land ( q \imp r )$:

  $p \imp q$. [Conjunction elimination]

  $q \imp r$. [Conjunction elimination]

  If $p$:

    $q$. [Implication elimination; also called Modus Ponens]

    $r$. [Implication elimination]

  $p \imp r$. [Implication introduction]

$( p \imp q ) \land ( q \imp r ) \imp ( p \imp r )$. [Implication introduction]

It should be a simple thing to convert this to a proof in any other reasonable formal system. The reason I present it as above is because it is so utterly natural in following our intuitive understanding (which is why it is called natural deduction).

Martin Sleziak
  • 53,687
user21820
  • 57,693
  • 9
  • 98
  • 256
  • @MartinSleziak: Thanks for adding the link! And do you know how can I get notified of edits to my posts? – user21820 Oct 09 '15 at 15:27
  • You mean that you do not have notification about the edit of your post in the inbox? That seems strange: http://meta.stackexchange.com/questions/2305/notify-us-when-one-of-our-posts-is-edited/135961#135961 (You can go back to your global inbox and check there whether there was a notification, as described here.) – Martin Sleziak Oct 09 '15 at 15:33
  • @MartinSleziak: Yup I got a notification of your comment to me under the question, but was not notified of your edit 3 minutes later. This is not the only instance, as some other posts of mine have also been edited, which I only accidentally discover a long time later (and so I don't know what else have been edited). It does not appear in my global inbox (http://stackexchange.com/users/1131127/user21820?tab=inbox) either. – user21820 Oct 11 '15 at 03:27
  • @MartinSleziak: I realized that I can see it under "User page > Activity > Responses > Revisions" despite it not being in the global inbox. I guess I'll just have to check there once in a while. – user21820 Oct 11 '15 at 09:47
  • I have asked in chat to see whether some more experienced users will know more about this. I was directed to this answer, which says that minor edits do not go to inbox. (But it seems that they are at least shown among responses.) – Martin Sleziak Oct 11 '15 at 14:29
  • @MartinSleziak: Ah I see thanks a lot! I appreciate that you took the time to help me ask. =) – user21820 Oct 11 '15 at 14:33
2

One way to prove it is to use $p\to q\iff \neg p\lor q$. \begin{align} (p \to q)\land(q \to r)\to (p \to r)&\iff \neg((p \to q)\land(q \to r))\lor (p \to r) \\ &\iff\neg((\neg p \lor q)\land(\neg q \lor r))\lor (\neg p \lor r) \\ &\iff((p \land \neg q)\lor(q\land \neg r))\lor (\neg p \lor r) \\ &\iff(p \land \neg q)\lor((q\land \neg r)\lor (\neg p \lor r)) \\ &\iff(p \land \neg q)\lor((q\lor \neg p \lor r)\land (\neg r\lor \neg p \lor r)) \\ &\iff(p \land \neg q)\lor((q\lor \neg p \lor r)\land (1\lor \neg p)) \\ &\iff(p \land \neg q)\lor((q\lor \neg p \lor r)\land 1) \\ &\iff(p \land \neg q)\lor(q\lor \neg p \lor r) \\ &\iff(p\lor(q\lor \neg p \lor r)) \land (\neg q\lor(q\lor \neg p \lor r)) \\ &\iff((p\lor \neg p)\lor q \lor r) \land ((\neg q\lor q)\lor \neg p \lor r) \\ &\iff(1\lor q \lor r) \land (1\lor \neg p \lor r) \\ &\iff 1\land 1 \\ &\iff 1 \end{align}

Eugene Zhang
  • 16,805