1
$\begingroup$

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.

$\endgroup$
4
  • 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, 2014 at 10:57
  • $\begingroup$ I mean this ((p → q) ∨ (p → r)) → (q ∨ r) $\endgroup$
    – tolly
    Oct 17, 2014 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, 2014 at 11:05
  • 1
    $\begingroup$ show that (p → q) ∨ (p → r) → (q ∨ r) and P∨q∨r are logically equivalent $\endgroup$
    – tolly
    Oct 17, 2014 at 11:11

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
  • $\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, 2014 at 11:57
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .