# Prove equivalence $(P \Rightarrow Q) \land (P \Rightarrow R) \Leftrightarrow P\Rightarrow(Q\land R)$

Prove equivalence $$(P \Rightarrow Q) \land (P \Rightarrow R) \Leftrightarrow P\Rightarrow(Q\land R)$$

What is the step by step for the equivalence of these equations. I can first break down the implications and use the distributive property, but then I get stuck.

-
Have you tried creating a truth table? – Ayman Hourieh Dec 12 '12 at 22:37
why don't you show what you've done, so we can help you get "unstuck" – amWhy Dec 12 '12 at 22:38
Are you sure? If $P$ is true and $Q$ is false, then $(P\to Q)\land (P\to R)$ is false, but $(P\land Q)\to R$ is true. – Hagen von Eitzen Dec 12 '12 at 22:50
Are you sure you do not mean $(q \Rightarrow r) \vee (p \Rightarrow r) \Leftrightarrow p \wedge q \Rightarrow r$? – glebovg Dec 12 '12 at 22:57
Sorry, i miss wrote the question. I meant to write P=>(Q^R) – user937897 Dec 12 '12 at 23:28

EDIT: Given updated edit to question, it seems we want to prove:

$[P \rightarrow (Q\land R)] \iff [(P\rightarrow Q) \land (P\rightarrow R)]$

It's usually best to prove $\iff$ equivalence-statements by proving each direction of the double implication $(\;\Rightarrow\;$ AND $\;\Leftarrow\;)$, so you don't make an inadvertent mistake by using a rule of inference that might go only one direction.

So you want to prove each of the following two implications:

$$[(P\rightarrow Q) \land (P\rightarrow R)] \implies [(P \rightarrow (Q\land R)] \tag{1}$$

$$[P\rightarrow (Q\land R)] \implies [(P \rightarrow Q) \land (P \rightarrow R)]\tag{2}$$

• Hints:

• for both (1) and (2): Use the identity that

$(A \rightarrow B) \equiv (\lnot A \lor B)\quad$ for each of the inner implications ($\rightarrow$).

• Then you can use distribution:

$[(A\lor B) \land C] \equiv [(A \land C) \lor (B \land C)];\quad[(A\land B) \lor C] \equiv [(A\lor C) \land (B \lor C)]$

• And use DeMorgan's Laws;

$\lnot (A \land B) \equiv (\lnot A \lor \lnot B),\quad \text{and} \quad \lnot (A \lor B) \equiv (\lnot A \land \lnot B)$

• Once you prove $(1)$, in this case you can prove $(2)$ by "undoing" what you did to prove $(1)$, starting with "undoing" the last step in the proof of $(1)$, and working backwards.

Note that each implication $(1)$ and $(2)$ is a tautology: both implications are true for all possible truth-value assignments to $P, Q, R$:

-

Let $P=1(true),Q=R=0(false)$, then $[(P\rightarrow Q) \land (P\rightarrow R)] \implies [(P \land Q) \rightarrow R]$ is true, but $[(P\land Q) \rightarrow R)] \implies [(P \rightarrow Q) \land (P \rightarrow R)]$ is not true. So the proposition is not true.

You can also check Wolframalpha: Link

-

The easier way to show logical equivalence is to use truth tables.

Edit: I think you are trying to prove a false statement. If you mean $(q \Rightarrow r) \vee (p \Rightarrow r) \Leftrightarrow p \wedge q \Rightarrow r$, the proof is easy: \begin{align} (q \Rightarrow r) \vee (p \Rightarrow r) &\Leftrightarrow ({\sim} p \vee r) \vee ({\sim} q \vee r)\\ &\Leftrightarrow ({\sim}p \vee {\sim}q) \vee (r \vee r)\\ &\Leftrightarrow {\sim}(p \wedge q) \vee r\\ &\Leftrightarrow p \wedge q \Rightarrow r\\ \end{align}

Edit: The proof of $(p \Rightarrow q) \wedge (p \Rightarrow r) \Leftrightarrow p \Rightarrow (q \wedge r)$ is also easy: \begin{align} (p \Rightarrow q) \wedge (p \Rightarrow r) &\Leftrightarrow ({\sim}p \vee q) \wedge ({\sim}p \vee r)\\ &\Leftrightarrow (({\sim p}\vee q) \wedge {\sim}p) \vee (({\sim}p \vee q) \wedge r)\\ &\Leftrightarrow ({\sim}p) \vee (({\sim}p \wedge r) \vee (q \wedge r))\\ &\Leftrightarrow ({\sim}p) \vee ({\sim}p \wedge r) \vee (q \wedge r)\\ &\Leftrightarrow {\sim}p \vee (q \wedge r)\\ &\Leftrightarrow p \Rightarrow (q \wedge r) \end{align}

-

Since you meant $P \rightarrow (Q \land R)$ instead of $(P \land Q) \rightarrow R$, according to your comment, then you can proceed as follows:

$$(P \rightarrow Q) \land (P \rightarrow R)$$ $$(\neg P \lor Q) \land (\neg P \lor R)$$ $$\neg P \lor (Q \land R)$$ $$P \rightarrow (Q \land R)$$

via the equivalence $P \rightarrow Q \leftrightarrow \neg P \lor Q$ and the distributive laws. For the converse, just reverse the above steps.

-