1
$\begingroup$

I have two parts to this question - I need to verify each of the following by writing an equivalence proof:

  1. $p \to (q \land r) \equiv (p \to q) \land (p \to r)$

  2. $(p \to q) \land (p \lor q) \equiv q$

Thank you if you can help! It's greatly appreciated.

  • 0
    thanks a lot guys :) this helped me a lot2015-01-22

1 Answers 1

1

We make extensive use of the identity $(a \to b) \equiv (\lnot a \lor b)$, and leave you to fill in the reasons for some of the intermediate steps in (2).

(1) $\quad p \to (q \wedge r) \equiv \lnot p \lor (q \land r) \equiv (\lnot p \lor q) \land (\lnot p \lor r) \equiv (p \to q) \wedge (p \to r)$.

(2) $\quad(p \to q) \land (p \lor q) \equiv q\quad?$ $(p \to q) \land (p \lor q) \equiv (\lnot p \lor q) \land (p \lor q)\tag{1}$ $\equiv \;[(\lnot p \lor q) \land p] \lor [(\lnot p \lor q) \land q]\tag{2}$ $\equiv \;[(\lnot p \land p) \lor (q \land p)] \lor [(\lnot p \land q) \lor (q \land q)]\tag{3}$ $\equiv \;F \lor (p \land q) \lor [(\lnot p \land q) \lor (q \land q)]\tag{4}$ $\equiv \;(p\land q) \lor [(\lnot p \land q) \lor (q \land q)]\tag{5}$ $\equiv \;(p\land q) \lor (\lnot p \land q) \lor q\tag{6}$ $\equiv \;[(p \lor \lnot p) \land q] \lor q\tag{7}$ $\equiv \;(T \land q) \lor q\tag{8}$ $\equiv \;q\lor q\tag{9}$ $\equiv \;q\tag{10}$

  • 0
    @amWhy: For (2), I would reason more simply\begin{align} & (p \to q) \land (p \lor q) \;\equiv\; q \\ \equiv & \;\;\;\;\;\text{"expand $\;\to\;$"} \\ & (\lnot p \lor q) \land (p \lor q) \;\equiv\; q \\ \equiv & \;\;\;\;\;\text{"factor out $\;q\;$: $\;\lor\;$ distributes over $\;\land\;$"} \\ & (\lnot p \land p) \lor q \;\equiv\; q \\ \equiv & \;\;\;\;\;\text{"excluded middle"} \\ & \text{false} \lor q \;\equiv\; q \\ \equiv & \;\;\;\;\;\text{"simplify"} \\ & \text{true} \\ \end{align}2013-07-28