# Proof of a compound proposition being a tautology

The question states the following compound proposition is a tautology, which I have to prove.

$$(p \rightarrow q) \wedge (q \rightarrow r) \rightarrow (p \rightarrow r)$$

My attempt is as follows:

$$\equiv (\neg p \vee q) \wedge (\neg q \vee r) \rightarrow (\neg p \vee r)$$ $$\equiv \neg((\neg p \vee q) \wedge (\neg q \vee r)) \vee (\neg p \vee r)$$

$$\equiv \neg[((\neg p \vee q) \wedge \neg q) \vee ((\neg p \vee q) \wedge r)] \vee (\neg p \vee r)\text{ [Distribution of conjunction over disjunction]}$$ $$\equiv \neg[((\neg p \wedge \neg q) \vee (q \wedge \neg q) \vee ((\neg p \vee q) \wedge r)] \vee (\neg p \vee r)\text{ [Distribution of conjunction over disjunction]}$$ $$\equiv \neg[((\neg p \wedge \neg q) \vee F )\vee ((\neg p \vee q) \wedge r)] \vee (\neg p \vee r)\text{ [Idempotent law]}$$ $$\equiv \neg[(\neg p \wedge \neg q) \vee ((\neg p \vee q) \wedge r)] \vee (\neg p \vee r)\text{ [Idempotent law]}$$ $$\equiv [(p \vee q) \wedge ((p \wedge \neg q) \vee \neg r)] \vee (\neg p \vee r)\text{ [De Morgan's law]}$$ $$\equiv (p \vee q) \wedge ((p \wedge \neg q) \vee \neg r) \vee (\neg p \vee r)$$ $$\equiv (p \vee q) \wedge (\neg p \vee r) \vee ((p \wedge \neg q) \vee \neg r)\text{ [Commutative law]}$$ $$\equiv [((p \vee q) \wedge \neg p) \vee ((p \vee q) \wedge r)] \vee ((p \wedge \neg q) \vee \neg r)\text{ [Conjunction over disjunction]}$$ $$\equiv [((p \wedge \neg p) \vee (q \wedge \neg p)) \vee ((p \vee q) \wedge r)] \vee ((p \wedge \neg q) \vee \neg r)\text{ [Conjunction over disjunction]}$$ $$\equiv [(F \vee (q \wedge \neg p)) \vee ((p \vee q) \wedge r)] \vee ((p \wedge \neg q) \vee \neg r)\text{ [Negation law]}$$

This goes on for quite a while, but I don't get the desired $$T$$ result. I'm guessing I've done something horribly wrong in the above calculation. I'll be so grateful for your help here. Anything regarding this text, from calculation error to using some incorrect terms. Thank yoou.

• I'd use $\lnot(a \land b) \equiv \lnot a \lor \lnot b$ in the first passages, to simplify things. Nov 21, 2020 at 18:32

A common strategy you might not have seen: labelling false as $$0$$ and true as $$1$$, $$\to$$ becomes $$\le$$ and is therefore transitive.

• That's an interesting observation. I'll keep that in mind for the future. Thank you :D
– user757852
Nov 23, 2020 at 13:50
• @debdul Then you may be interested in some quite rich theory that this gets into.
– J.G.
Nov 23, 2020 at 13:55
• I've saved the writing to my private list. Unfortunately by the looks of it I'm not yet capable of understanding it. I'm just starting out with set theory (and still brushing up the logic exercises). I'm also self taught, so probably going to take more time than usual. Anyway, I really appreciate you taking the time though :D
– user757852
Nov 23, 2020 at 14:02

Something goes wrong here:

$$\equiv [(p \vee q) \wedge ((p \wedge \neg q) \vee \neg r)] \vee (\neg p \vee r)\text{ [De Morgan's law]}$$ $$\equiv (p \vee q) \wedge ((p \wedge \neg q) \vee \neg r) \vee (\neg p \vee r)$$ $$\equiv (p \vee q) \wedge (\neg p \vee r) \vee ((p \wedge \neg q) \vee \neg r)\text{ [Commutative law]}$$

You're basically going from something of the form $$[A \land B] \lor C$$ to $$A \land B \lor C$$ to $$A \land C \lor B$$

Note that the last two statements are both ungrammatical: since $$(A \land B) \lor C$$ is not equivalent to $$A \land (B \lor C)$$, you cannot just drop those parentheses.

• Understood. I selected the other answer as the person has less reputation. Thank you again :)
– user757852
Nov 23, 2020 at 13:49
• @debdut you're welcome. And yes, share the wealth! :) Nov 23, 2020 at 14:24

The step: $$\equiv [(p \vee q) \wedge ((p \wedge \neg q) \vee \neg r)] \vee (\neg p \vee r)\text{ [De Morgan's law]}$$ $$\equiv (p \vee q) \wedge ((p \wedge \neg q) \vee \neg r) \vee (\neg p \vee r)$$ is incorrect. You need the distributive law here, so it should be $$\equiv [(p \vee q)\vee (\neg p \vee r)] \wedge [((p \wedge \neg q) \vee \neg r) \vee (\neg p \vee r)]$$ Now by commutative law $$\equiv [(p \vee \neg p)\vee q \vee r] \wedge [((p \wedge \neg q) \vee (\neg r \vee r) \vee \neg p] = T\wedge T = T$$ So it is a tautology.

• Thank you so much!
– user757852
Nov 23, 2020 at 13:47

I don't know which rules of inference you are using. The easiest would be the following using the rules that are in Understanding symbolic logic of Virginia Klenk:
$$1)(p\rightarrow q)\wedge(q\rightarrow r)$$ (Conditional Assumption)
$$2) p$$ (Conditional Assumption)
$$3) p\rightarrow q$$ (simplification 1)
$$4) q$$ (Modus Ponens 2,3)
$$5) q\rightarrow r$$ (Simplification 1)
$$6) r$$ (Modus Ponens 4,5)
$$7) p\rightarrow r$$ (Conditional Proof 2-6)
$$8) (p\rightarrow q)\wedge(q\rightarrow r)\rightarrow(p\rightarrow r)$$ (Conditional Proof 1-7)

Otherwise you can always use truth tables (Note Virginia Klenk also allows the use of the hypothetical syllogism which can reduce this proof to just a few steps)

• I'm solving chapter specific questions (Rosen's Dicrete Mathematics), and rules of inference aren't introduced yet (wrt the chapter this question is taken from), so I'm trying to not use any of those.
– user757852
Nov 21, 2020 at 18:02

Apply implication equivalence as much as possible, then deMorgan's rules (with DNE if you need to) as much as possible, before association and commutation to something useful. The path should become clear from there.

\begin{align}&((p\to q)\land(q\to r))\to(p\to r)\\&\vdots&&\text{conditional equivalence}\\&\lnot((\lnot p\lor q)\land(\lnot q\lor r))\lor(\lnot p\lor r)\\&\vdots&&\text{de Morgan's}\\&((p\land\lnot q)\lor(q\land\lnot r))\lor(\lnot p\lor r)\\&\vdots&&\text{association and commutation}\\&((p\land \lnot q)\lor \lnot p)\lor((q\land\lnot r)\lor r)\\&\vdots\\&\top\end{align}

• Seems logical. Thank you for the advice.
– user757852
Nov 23, 2020 at 13:54