Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
2  
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
1  
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
show 2 more comments

4 Answers

up vote 5 down vote accepted

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

enter image description here

share|improve this answer
    
+1 Nice formatting! –  copper.hat Dec 12 '12 at 23:45
add comment

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

share|improve this answer
add comment

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}

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.