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.

Question

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.

Answer 1

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

Answer 2

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