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.

  • 1
    $\begingroup$ 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? $\endgroup$
    – Taladris
    Oct 17 '14 at 10:57
  • $\begingroup$ I mean this ((p → q) ∨ (p → r)) → (q ∨ r) $\endgroup$
    – tolly
    Oct 17 '14 at 11:04
  • $\begingroup$ @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. $\endgroup$
    – Nikolaj-K
    Oct 17 '14 at 11:05
  • 1
    $\begingroup$ show that (p → q) ∨ (p → r) → (q ∨ r) and P∨q∨r are logically equivalent $\endgroup$
    – 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$

  • $\begingroup$ 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. $\endgroup$
    – 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$.


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.