1
$\begingroup$

Prove equivalence $((P \Rightarrow Q) \land (P \Rightarrow R)) \iff (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.

  • 0
    @user937897 You might want to edit your question.2012-12-13

4 Answers 4

5

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

1

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

0

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}

0

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.