Prove without using truth table

Question

Prove that $$((p \lor q) \land (p \implies r) \land (q \implies r)) \implies r$$ is tautology without using truth table.

My work so far:

$$(\lnot p \land ¬q) \lor (p \land \lnot r) \lor (q \land \lnot r) \lor r $$ $$\equiv (\lnot p \land ¬q) \lor (p \land \lnot r) \lor (q \lor r) \land (\lnot r \lor r)$$ $$\equiv (\lnot p \land ¬q) \lor (p \land \lnot r) \lor (q \lor r) \land \top $$

Answer 1

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}