Don't understand the following equivalence after distributivity for $(\neg p\vee \neg q)\wedge(p\vee q)$

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.

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

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.

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)$$.

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