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

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 :)

• If every penny is a remedy and every quarter is a remedy, then eveything that is a penny or a quarter is a remedy. The inverse can be stated similary Jan 29, 2015 at 2:59
• Oh, that is nice and succinct, @GregordeCillia Jan 29, 2015 at 3:48
• Your comment should go before the question in this case, I think. It is important for the answerer to know that you're not looking for a strict proof using logical equivalences (like the one I provided). Of course, I should ideally read the entire question first, but you greatly emphasized the question at hand as opposed to your real question which was italicized under it. My proof is very clean logically I feel, but I am not sure you are going to get a more intuitive explanation than the one Gregor de Cillia provided. Jan 29, 2015 at 4:01
• Hi , @GregordeCillia , that is a really wonderful way of expressing this . Thanks a bunch :) Jan 29, 2015 at 4:01

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

• @pranav That is what is says. "if $p$ then $r$" and "$r$ whenever $p$" are both equivalent statements for, $p\implies r$. They mean that the truth of $p$ is sufficient for the truth of $r$. Jan 30, 2015 at 1:11

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.

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