$\begingroup$

$(p∨q) ∧ (p∨r) ∧ (q∨r) \iff (p∧q) ∨ (p∧r) ∨ (q∧r)$

Without using set theory, how can I prove this using logical equivalences? I've tried to approach this problem with De Morgan and I've also tried the property of distributivity but I keep reaching a dead end.

How should I approach this problem?

Thank you.

$\endgroup$

3 Answers

$\begingroup$

$\begin{array}{ll} 1. & (p\lor q)\land(p\lor r)\land(q\lor r)=\\ 2. & (p\lor(q\land r))\land(q\lor r)=\\ 3. & ((p\lor(q\land r))\land q)\lor ((p\lor(q\land r))\land r)=\\ 4. & ((p\land q)\lor((q\land r)\land q))\lor ((p\land r)\lor((q\land r)\land r))=\\ 5. & ((p\land q)\lor(q\land r))\lor ((p\land r)\lor(q\land r))=\\ 6. & (p\land q)\lor(q\land r)\lor (p\land r)\lor(q\land r)=\\ 7. & (p\land q)\lor(q\land r)\lor (p\land r) \end{array}$

2. factorize $p$
3. distribute $(q\lor r)$
4. distribute $q$ and $r$
5. simplify $(a\land b)\land a=a\land b$
6. eliminate superfluous parenthesis in a chain of $\lor$
7. simplify $a\lor a=a$

$\endgroup$ $\begingroup$

$\Leftarrow:$ Suppose $(p\wedge q)\vee(p\wedge r)\vee(q\wedge r)$. Then at least one of the statements $(p\wedge q), (p\wedge r)$ or $(q\wedge r)$. Suppose $(p\wedge q)$ is true. Then $p,q$ are true. So $p\vee q,\ p\vee r,\ q\vee r$ are true. Hence $(p\vee q)\wedge (p\vee r)\wedge( q\vee r)$ is true. Similarly handle the cases $ p\vee r$, $\ q\vee r$.

$\Rightarrow:$ Suppose $(p\vee q)\wedge (p\vee r)\wedge( q\vee r)$ is true. Then $(p\vee q), (p\vee r), ( q\vee r)$ are true. Suppose $p$ is false. Then $q$ is true since $p\vee q$ is true, and $r$ is true since $p\vee r$ is true. In a similar way show that when $q$ is false $p$ and $r$ are true, and when $r$ is false $p$ and $q$ are true. So $(p\vee q)\wedge (p\vee r)\wedge( q\vee r)$ is true. Also, observe that if $p,q,r$ all are true then $(p\vee q)\wedge (p\vee r)\wedge( q\vee r)$ is true.

Hence you have the required logical equivalence.

Note that this answer is not complete. I encourage you to fill the gaps.

$\endgroup$ $\begingroup$

$$(p \lor q) \land (p \lor r) \land (q \lor r) = \text{ (Distribution)}$$

$$(p \land p \land q) \lor (p \land p \land r) \lor (p \land r \land q) \lor (p \land r \land r) \lor (q \land p \land q) \lor (q \land p \land r) \lor (q \land r \land q) \lor (q \land r \land r) = \text{ (Idempotence)}$$

$$(p \land q) \lor (p \land r) \lor (p \land r \land q) \lor (p \land r) \lor (q \land p) \lor (q \land p \land r) \lor (q \land r \land q) \lor (q \land r) = \text{ (Idempotence)}$$

$$(p \land q) \lor (p \land r) \lor (p \land r \land q)\lor (q \land p \land r) \lor (q \land r \land q) \lor (q \land r) = \text{ (Absorption)}$$

$$(p \land q) \lor (p \land r) \lor (q \land r)$$

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy