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


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: derivation in natural deduction

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}


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.