0
$\begingroup$

In my logic course I saw the following equivalence, but I don't understand how they get there.$(\neg p\vee \neg q)\wedge(p\vee q)\, \Longleftrightarrow \, (\neg p\wedge p)\vee (\neg p\wedge q)\vee(\neg q\wedge p)\vee(\neg q\wedge q)$

I can see it's equivalent by setting up a truth table, but I just don't understand how they used the logical equivalence for distributivity which is $\varphi \vee (\psi \wedge \chi )\Longleftrightarrow (\varphi \vee \psi )\wedge (\varphi \vee \chi )$ to reach the formula on the right side.

Thanks in advance!

$\endgroup$
2
  • $\begingroup$ Remember that there are two distributive laws: one for AND over OR, and one for OR over AND. $\endgroup$
    – MPW
    Feb 16, 2020 at 12:37
  • $\begingroup$ This is just like FOIL $\endgroup$
    – Bram28
    Feb 16, 2020 at 17:00

2 Answers 2

1
$\begingroup$

They used it twice, once the left distributivity, then again the right distributivity.

$$\begin{array}{rcl}(p\lor q)\land(r\lor s)&\Leftrightarrow &((p\lor q)\land r)\lor((p\lor q)\land s)\\&\Leftrightarrow &(p\land r)\lor (q\land r)\lor(p\land s)\lor(q\land s)\end{array}$$

This is no different from using identities such as $(a+b)(c+d)=ac+ad+bc+bd$ in arithmetic.

$\endgroup$
1
$\begingroup$

First step: we have to distribute $(p∨q)$ over $(¬p∨¬q)$ to get:

$[(p∨q) \land \lnot p] \lor [(p∨q) \land \lnot q]$.

Second setp: apply Distributivity again twice to get:

$(\lnot p \land p) \lor (\lnot p \land q) \lor (p \land \lnot q) \lor (q \land \lnot q)$.

Finally, we may use $(\lnot p \land p) \equiv (q \land \lnot q) \equiv \text {FALSE }$ and $(\text { FALSE} \lor \alpha) \equiv \alpha$ for a formula $\alpha$ whatever to get the equivalent:

$(\lnot p \land q) \lor (p \land \lnot q)$.

$\endgroup$
1
  • $\begingroup$ It’s nothing but distributivity. Your last paragraph is irrelevant, isn’t it? $\endgroup$
    – MPW
    Feb 16, 2020 at 12:28

Your Answer

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

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