3
$\begingroup$

$$[(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.

$\endgroup$
5
  • $\begingroup$ what inference rules do you have? surely implication elimination, i.e. $(a\rightarrow b)\land a\implies b$ $\endgroup$
    – obataku
    Sep 1 '15 at 16:13
  • $\begingroup$ open $(p \rightarrow q)$ and use the implication elimination. $\endgroup$ Sep 1 '15 at 16:15
  • $\begingroup$ 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. $\endgroup$ Sep 1 '15 at 17:51
  • $\begingroup$ Implication elimination? Isn't that just called modus ponens? Or is that something else? $\endgroup$
    – Brian Tung
    Sep 1 '15 at 21:08
  • $\begingroup$ 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? $\endgroup$
    – xSpartanCx
    Sep 1 '15 at 21:24
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.