# Proving $[(P\lor Q)\land(P\to R)\land(Q\to R)]\to R$ is a tautology without using a truth table?

$$[(P\lor Q)\land(P\to R)\land(Q\to R)]\to R\tag{1}$$

How can I prove that $(1)$ is a tautology without using a truth table? I used the identity $$(P\to R)\land(Q\to R)\equiv(P\lor Q)\to R$$ but from there I get stuck and can't figure out where to go.

• what inference rules do you have? surely implication elimination, i.e. $(a\rightarrow b)\land a\implies b$ Sep 1 '15 at 16:13
• open $(p \rightarrow q)$ and use the implication elimination. Sep 1 '15 at 16:15
• This is probably less formalized than you want, but it's how I'd see that this is a tautology. The antecedent $(P\lor Q)\land(P\to R)\land(Q\to R)$ tells you that at least one of $P$ and $Q$ is true and, whichever one it is, it implies $R$. So $R$ has to be true. Sep 1 '15 at 17:51
• Implication elimination? Isn't that just called modus ponens? Or is that something else? Sep 1 '15 at 21:08
• doesn't that only work if A must be true? otherwise if (a) is false and (b) is true then the left side evaluates to true and the right side evaluates to false, does it not? Sep 1 '15 at 21:24

Here are the steps $$((P \lor Q) \land (P \to R) \land (Q \to R))\to R$$ $$\equiv((\lnot(\lnot P) \lor Q) \land (P \to R) \land (Q \to R))\to R$$ $$\equiv((\lnot P \to Q) \land (Q \to R)\land (P \to R))\to R$$ $$\equiv((\lnot P \to R) \land (P \to R))\to R$$ $$\equiv((P \lor R) \land (\lnot P \lor R))\to R$$ $$\equiv(R\lor R)\to R$$ $$\equiv R\to R$$ $$\equiv \rm{true}$$

$$\begin{array}{ll} &(P\vee Q) \wedge (P \Rightarrow R) \wedge (Q \Rightarrow R)\\ \equiv&\hspace{1cm}\{ \text{ by the tautology mentioned in the question }\}\\ &(P\vee Q) \wedge ( (P\vee Q) \Rightarrow R) \\ \equiv&\hspace{1cm}\{ \text{ } A \wedge (A \Rightarrow B ) \equiv A \wedge B, \text{ see below }\}\\ &(P\vee Q) \wedge R \\ \Rightarrow&\hspace{1cm}\{ \text{ } A \wedge B \Rightarrow B \text{ } \}\\ &R\\ \\ \\ &A \wedge (A \Rightarrow B)\\ \equiv&\hspace{1cm}\{ \text{ using the disjunctive definition of \Rightarrow }\}\\ &A \wedge (\neg A \vee B) \\ \equiv&\hspace{1cm}\{ \text{ distribution of \wedge over \vee }\}\\ &(A\wedge\neg A)\vee(A \wedge B)\\ \equiv&\hspace{1cm}\{ \text{ law of excluded middle } \}\\ &\mathbf{false}\vee(A \wedge B)\\ \equiv&\hspace{1cm}\{ \text{ \mathbf{false} is the unit of \wedge } \}\\ &A\wedge B\\ \end{array}$$

I'll outline one fairly easy way of solving this problem without a truth table; however, the solution is not one that you obtain deduction by deduction (which is what it seems you want).

Using DeMorgan's law and the fact that $y\to z\equiv\neg y\lor z$, we may write your implication as follows: $$\underbrace{(\neg p\land\neg q)}_{(1)}\lor\underbrace{(p\land\neg r)}_{(2)}\lor\underbrace{(q\land\neg r)}_{(3)}\lor r.$$ If $r$ is true, then you're done. Thus, suppose $r$ is not true. If either $p$ or $q$ (or both) is true, then either $(2)$ or $(3)$ is true (or both). If, however, neither $p$ nor $q$ is true, then $(1)$ is true. Thus, regardless of the truth values for $p,q,r$, we must have a tautology. $\blacksquare$

$$[(P\lor Q)\land(P\implies R)\land(Q\implies R)]\implies R$$ $$\iff\neg((P\vee Q)\wedge \neg(P\wedge\neg R)\wedge\neg(Q\wedge\neg R)\wedge\neg R)$$ $$\iff\neg((P\vee Q)\wedge\neg R\;\wedge \neg(P\wedge\neg R)\wedge\neg(Q\wedge\neg R))$$ $$\iff\neg((P\vee Q)\wedge\neg R\; \wedge(\neg P\vee R)\wedge(\neg Q\vee R))$$ $$\iff\neg((P\vee Q)\wedge\neg R \;\wedge((\neg P \wedge \neg Q)\vee R))$$ $$\iff\neg((P\vee Q)\wedge\neg R \;\wedge(\neg(P\vee Q)\vee R))$$ $$\iff\neg(\underbrace{(P\vee Q)\wedge\neg R\;}_{S} \wedge\underbrace{\neg ((P\vee Q)\wedge\neg R)}_{\neg S})$$ $$\iff\neg(S\wedge \neg S)=1$$

If the formula is not a tautology, there is ( at least) one truth-value assignment in which it is false.

The formula is a conditional which can't be false unless the consequent is false and the antecedent true.

So, in case the whole conditional is false

• R is false

• (P OR Q) , (P --> R) and ( Q --> R) are 3 true formulas ( since a conjunction is true iff alll its conjuncts are true)

• since (P--> R) is true with a false consequent ( R being false) P ( the antecedent) must be false

• since ( P OR Q) is true with a false first disjunct ( P being false), Q ( the second disjunct) must be true

• now, (Q --> R) is supposed to be true, but its antecedent ( namely : Q) is true and its consequent ( that is : R) is false ; hence a contradiction.

So the hypothesis that the formula is false has led us to an impossible truth-value assignment ; in other words, there is no truth value assignment that can make the formula false.