I am looking for a way to prove that the statement, $[(p \to q) \land (q \to r)] \to (p \to r)$, is a tautology without the help of the truth table. By using only Laws and Theorems like De Morgan's Law, Domination Law, etc. Also, I can't use the rules of inference. Please help, thank you.
Tautology Proof – How to Prove (p -> q) ? (q -> r) -> (p -> r) Without Truth Table
boolean-algebradiscrete mathematicslogicpropositional-calculus
Related Solutions
In general, in propositional classical logic (which is the logic where truth tables make sense), a standard way to prove that a formula is a tautology without using truth table is:
- to derive the formula in some derivation system for propositional classical logic, such as sequent calculus, natural deduction, Hilbert system.
This is sufficient since, thanks to the soundness theorem, every formula that is provable in such a system is a tautology.
More specifically, concerning your question, a derivation of $\big( (p \lor q) \land ((p \to r) \land (q \to r)) \big) \to r$ in propositional classical natural deduction is the following:
Thus, by the soundness theorem for propositional classical natural deduction, the formula $\big( (p \lor q) \land ((p \to r) \land (q \to r)) \big) \to r$ is a tautology.
(Remark: Actually, the derivation above does not use the rule RAA (reductio ad absurdum), hence the formula is provable in intuitionistic propositional logic, which is weaker that propositional classical logic.)
Another way (equivalent to the previous one and closer to your approach) to prove that $\big( (p \lor q) \land ((p \to r) \land (q \to r)) \big) \to r$ is a tautology is the following argument, where $\equiv$ stands for logical equivalence, and $\top$ for truth (or tautology):
\begin{align} &\quad \big( (p \lor q) \land (p \to r) \land (q \to r) \big) \to r \\ &\equiv \lnot \big( (p \lor q) \land (p \to r) \land (q \to r) \big) \lor r \\ &\equiv \big( \lnot(p \lor q) \lor \lnot(p \to r) \lor \lnot(q \to r) \big) \lor r \\ &\equiv (\lnot p \land \lnot q) \lor (p \land \lnot r) \lor (q \land \lnot r) \lor r \\ &\equiv (\lnot p \land \lnot q) \lor (p \land \lnot r) \lor ((q \lor r) \land (\lnot r \lor r)) \\ &\equiv (\lnot p \land \lnot q) \lor (p \land \lnot r) \lor ((q \lor r) \land \top) \\ &\equiv (\lnot p \land \lnot q) \lor (p \land \lnot r) \lor q \lor r \\ &\equiv ((\lnot p \land \lnot q) \lor q) \lor ((p \land \lnot r) \lor r) \\ &\equiv ((\lnot p \lor q) \land (\lnot q \lor q)) \lor ((p \lor r) \land (\lnot r \lor r)) \\ &\equiv ((\lnot p \lor q) \land \top) \lor ((p \lor r) \land \top) \\ &\equiv \lnot p \lor q \lor p \lor r \\ &\equiv (\lnot p \lor p) \lor q \lor r \\ &\equiv \top \lor q \lor r \\ &\equiv \top \end{align}
Best Answer
As correctly suggested by Wuestenfux, first you should decompose $\to$. Then, you should apply several logical equivalences to simplify your formula to $\top$ (a formula that is always true). A complete simplification of your formula, using the logical equivalences listed here, is the following:
\begin{align} &\big((p \to q) \land (q \to r) \big) \to (p \to r) \\ \equiv \ & \lnot \big( (\lnot p \lor q) \land (\lnot q \lor r) \big) \lor (\lnot p \lor r) &\text{decomposition of }\to \\ \equiv \ & \lnot (\lnot p \lor q) \lor \lnot (\lnot q \lor r) \lor \lnot p \lor r&\text{De Morgan} \\ \equiv \ & (\lnot\lnot p \land \lnot q) \lor (\lnot\lnot q \land \lnot r) \lor \lnot p \lor r &\text{De Morgan} \\ \equiv \ & \lnot p \lor (\lnot\lnot p \land \lnot q) \lor (\lnot\lnot q \land \lnot r) \lor r &\text{commutativity} \\ \equiv \ & \big((\lnot p \lor \lnot\lnot p) \land (\lnot p \lor \lnot q)\big) \lor \big((\lnot\lnot q \lor r) \land (\lnot r \lor r) \big) &\text{distributivity} \\ \equiv \ & \big(\top \land (\lnot p \lor \lnot q)\big) \lor \big((\lnot\lnot q \lor r) \land \top \big) &\text{negation law} \\ \equiv \ & (\lnot p \lor \lnot q) \lor (\lnot\lnot q \lor r) &\text{identity law} \\ \equiv \ & \lnot p \lor (\lnot q \lor \lnot\lnot q) \lor r &\text{associativity} \\ \equiv \ & \lnot p \lor \top \lor r &\text{negation law} \\ \equiv \ & \top &\text{domination law} \\ \end{align}