Proof of a compound proposition being a tautology

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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)

Answer 5

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}$$