Propositional Logic : Why is ((p $\Rightarrow$ r) $\land$ (q $\Rightarrow$ r)) $\equiv$ ((p $\lor$ q) $\Rightarrow$ r)

Question

I was working my way through some Propositional Logic and had the following doubt :

Why is this true :

((p $\Rightarrow$ r) $\land$ (q $\Rightarrow$ r)) $\equiv$ ((p $\lor$ q) $\Rightarrow$ r)

Please provide an intuitive explanation and not one that uses a truth table or logic identities to simplify the expression . I have already done both of them :)

Answer 1

From $\;((p\implies r) \wedge (q\implies r))\;$, we know if $p$ is true then $r$ is true, and if $q$ is true then $r$ is true.

This means that if either $p$ or $q$ are true then $r$ is true. (If one is false and the other true, we still know $r$ must be true; only if both are false do we not know what $r$ is.)

Which is $\;(p\vee q) \implies r\;$ so they are equivalent statements.

$$\therefore ((p\implies r) \wedge (q\implies r)) \equiv ((p\vee q) \implies r)$$

---

Alternatively, since $\;x\implies y\;$ is equivalent to $\;\neg x \impliedby \neg y\;$ then we can substitute a contraposition for each implication.

Thus $\;((p\implies r) \wedge (q\implies r))\;$ is equivalent to $\;((\neg p\impliedby \neg r) \wedge (\neg q\impliedby \neg r))\;$, and hence we know if $r$ is false then $p$ is false, and if $r$ is false then $q$ is false.

To simplify, this means that if $r$ is false then both $p$ and $q$ are false.

Which is $\;(\neg p\wedge \neg q) \impliedby \neg r\;$, and this is equivalent to: $\;(p\vee q) \implies r\;$.

$$\because ((\neg p\impliedby \neg r) \wedge (\neg q\impliedby \neg r)) \equiv ((\neg p\wedge \neg q) \impliedby \neg r)$$

$$\therefore ((p\implies r) \wedge (q\implies r)) \equiv ((p\vee q) \implies r)$$

---

Gregor de Cillia put this rather more succinctly in the comments.

If every penny is a remedy and every quarter is a remedy, then everything that is a penny or a quarter is a remedy. The inverse can be stated similary – Gregor de Cillia

Answer 2

Here is a no nonsense approach that should be quite easy to follow: \begin{align} [(p\to r)\land(q\to r)] &\equiv [(\neg p\lor r)\land (\neg q\lor r)]\tag{$p\to q \equiv \neg p \lor q$}\\[0.5em] &\equiv [(\neg p\land \neg q)\lor r] \tag{distributivity}\\[0.5em] &\equiv [(\neg(\neg p\land \neg q)\to r]\tag{$p\to q \equiv \neg p \lor q$}\\[0.5em] &\equiv (p\lor q)\to r\tag{DeMorgan} \end{align} Thus, we have that $$ [(p\to r)\land(q\to r)]\equiv (p\lor q)\to r, $$ as desired.

Answer 3

As noted by @GregordeCillia in the comments , the intuitive explanation would be something on these lines :

• If every penny is a remedy and every quarter is a remedy $\equiv$ ((p $\Rightarrow$ r) $\land$ (q $\Rightarrow$ r))

• then everything that is a penny or a quarter is a remedy $\equiv$ ((p $\lor$ q) $\Rightarrow$ r)

• The inverse can be stated similary