# Prove $\;\big((p\rightarrow q) \lor (p \rightarrow r)\big) \rightarrow (q\lor r)\equiv p \lor q \lor r$ without use of a truth table.

Without using the truth table, I need to prove:

$$\big((p\rightarrow q) \lor (p \rightarrow r)\big) \rightarrow (q\lor r)\equiv p \lor r \lor q$$

Up until now, we've been using truth-tables to verify equivalences. So I'm a bit lost on where to begin without using a truth-table.

• You should precise a little bit the question: ((p → q) ∨ (p → r)) → (q ∨ r) and (p → q) ∨ ( (p → r) → (q ∨ r) ) are a priori two distinct propositions. Which one do you mean? – Taladris Oct 17 '14 at 10:57
• I mean this ((p → q) ∨ (p → r)) → (q ∨ r) – tolly Oct 17 '14 at 11:04
• @Taladris: The question is valid, in principle, but seriously you know that $p\to q$ doesn't imply $p\lor q\lor r$ and so why even bother asking. It's not like you'll encounter here the request to prove a falsity, just by the nature of this site. – Nikolaj-K Oct 17 '14 at 11:05
• show that (p → q) ∨ (p → r) → (q ∨ r) and P∨q∨r are logically equivalent – tolly Oct 17 '14 at 11:11

\begin{align}\big((p\rightarrow q) \lor (p \rightarrow r)\big) \rightarrow (q\lor r) &\equiv \lnot\big((\lnot p \lor q) \lor (\lnot p \lor r)\big) \lor (q \lor r)\tag{1}\\ \\ &\equiv \big(\lnot(\lnot p \lor q) \land \lnot (\lnot p \lor r)\big) \lor (q\lor r)\tag{2}\\ \\ &\equiv \big((p \land\lnot q)\land (p \land \lnot r)\big) \lor (q \lor r)\tag{3} \\ \\ &\equiv (p \land \lnot q \land \lnot r) \lor (q \lor r)\tag{4}\\ \\ &\equiv (p \land \lnot(q\lor r)) \lor (q\lor r)\tag{5} \\ \\ &\equiv (p \lor (q\lor r)) \land (\lnot (q \lor r) \lor (q \lor r))\tag{6}\\ \\ &\equiv (p \lor q \lor r) \land T\tag{7}\\ \\ &\equiv (p \lor q \lor r)\tag{8} \end{align}

In $(1)$, we replace every occurrence of $\varphi \rightarrow \tau$ with its equivalent $\lnot \varphi \lor \tau$.

$(1)\to (2)$ Application of DeMorgan's.

$(2)\to (3)$ More DeMorgan's (used twice)

$(3) \to (4)$ Implicit use of associativity and commutativity and the fact that $p \land p\equiv p$:

$(4)\to (5)$ DeMorgan's

$(5)\to (6)$ Distributive Law

$(6)\to (7)$ tautology: $\varphi \lor \lnot \varphi \equiv T$

• You're welcome, tolly. With newer users, I cut some slack (for example, by modeling how to work with proofs). But in the future, your posts will be much better received by users if you include a bit more context in your posts, and show your attempts, even if those attempts get you stuck or lead to undesired results. – amWhy Oct 17 '14 at 11:57

A solution using just words and definitions of the connectives:

Let $$\alpha = \big((p\rightarrow q) \lor (p \rightarrow r)\big) \rightarrow (q\lor r), \;\;\;\; \beta = p \lor q \lor r$$

Suppose $\alpha$ is true. Then either $\big((p\rightarrow q) \lor (p \rightarrow r)\big)$ is false, or $\big((p\rightarrow q) \lor (p \rightarrow r)\big)$ is true and so is $(q \lor r)$. Suppose the former. Then $(p \rightarrow q)$ and $(p \rightarrow r)$ must both be false which can only happen when $p$ is true and the statements $q, r$ are botth false. Since $p$ is true $\beta$ is true. Now suppose the latter. Then $(q \lor r)$ is true which means at least one of $q, r$ is true which renders $\beta$ true. Hence if $\alpha$ is true then $\beta$ is true $----(1)$

Now suppose $\beta$ is true. Then at least one of $p, q, r$ is true. If one of $q$ or $r$ is true then $\alpha$ is true since the consequent is true. So suppose not. Then $p$ must be true. It suffices to consider only the case when the antecedent of $\alpha$ is true. In this case one of $(p \rightarrow q)$ or $(p \rightarrow r)$ is true. Then at least one of $q$ or $r$ must be true since $p$ is true and hence the consequent is also true. All cases are disposed of. $(q \lor r)$ is true which means at least one of $q, r$ is true which renders $\beta$ true. Hence if $\beta$ is true then $\alpha$ is true $----(2)$

From $(1)$ and $(2)$ we may conclude that $\alpha$ is logically equivalent to $\beta$.