1
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Please try to think of a more descriptive title. 99% of questions z in this site also ask for a proof of something... $\endgroup$ Commented Oct 4, 2015 at 4:58
  • $\begingroup$ I edited it for him. $\endgroup$ Commented Oct 4, 2015 at 5:07
  • $\begingroup$ @hermes: You shouldn't add text to the answer. Edits are acceptable, adding content is not. $\endgroup$
    – copper.hat
    Commented Oct 4, 2015 at 5:33
  • $\begingroup$ @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. $\endgroup$ Commented Oct 4, 2015 at 6:09
  • 1
    $\begingroup$ 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.) $\endgroup$ Commented Oct 4, 2015 at 10:33

2 Answers 2

2
$\begingroup$

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).

$\endgroup$
6
  • $\begingroup$ @MartinSleziak: Thanks for adding the link! And do you know how can I get notified of edits to my posts? $\endgroup$
    – user21820
    Commented Oct 9, 2015 at 15:27
  • $\begingroup$ You mean that you do not have notification about the edit of your post in the inbox? That seems strange: meta.stackexchange.com/questions/2305/… (You can go back to your global inbox and check there whether there was a notification, as described here.) $\endgroup$ Commented Oct 9, 2015 at 15:33
  • $\begingroup$ @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 (stackexchange.com/users/1131127/user21820?tab=inbox) either. $\endgroup$
    – user21820
    Commented Oct 11, 2015 at 3:27
  • $\begingroup$ @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. $\endgroup$
    – user21820
    Commented Oct 11, 2015 at 9:47
  • $\begingroup$ 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.) $\endgroup$ Commented Oct 11, 2015 at 14:29
2
$\begingroup$

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}

$\endgroup$
0

Not the answer you're looking for? Browse other questions tagged .