# Why is this part of the composed proposition false?

Currently I'm studying logic, but I do not understand a certain step. It is the step from row $$2$$ to $$3$$. I see that $$-q$$ is the common factor on both sides of the middle or operator, but I did not succeed in factoring out.

\begin{aligned} (p \wedge q) \rightarrow \neg(r \vee q) & \equiv \neg(p \wedge q) \vee \neg(r \vee q) \\ & \equiv \neg p \vee \neg q \vee(\neg r \wedge \neg q) \\ & \equiv \neg p \vee \neg q \end{aligned}

I understand that

\begin{aligned} &\equiv \mathbb{F} \vee(p \wedge q) \\ &\equiv(p \wedge q) \end{aligned}

so that implies that

$$$$(\neg \boldsymbol{r} \wedge \neg q)$$$$

is false.

Do I miss a rule or should it be obvious from the K-map?

Whole question + solution:

• Thanks for the feedback, I included the whole question to make sure I didnot include essential information
– Tim
Mar 9, 2022 at 15:42
• It's definitely an equivalence. Do you know what absorption is? Mar 9, 2022 at 16:03
• @TenO'Four Now it looks correct I added a proof. Mar 9, 2022 at 16:20
• @Tim, here's proof of the law (see the last answer) Mar 9, 2022 at 17:17
• Thanks for the help!
– Tim
Mar 9, 2022 at 17:45

## 2 Answers

$$\neg p\lor \neg q\equiv \neg p \vee \neg q \vee(\neg r \wedge \neg q) \\$$

Is indeed true, one direction of the equivalence is trivial, for the other direction suppose that $$\neg p \lor \neg q \lor (\neg r \land \neg q)$$ is true then we must have that at least one of the disjuncts is true. Now suppose that $$(\neg r \land \neg q$$) is true then we immediately have that $$\neg q$$ is true and so we get $$\neg p\lor \neg q$$ is true. If the other disjunct is true then we have a triviality.

First, I want to point out a mistake in your reasoning. You say:

I understand that

\begin{aligned} &\equiv \mathbb{F} \vee(p \wedge q) \\ &\equiv(p \wedge q) \end{aligned}

so that implies that

$$$$(\neg \boldsymbol{r} \wedge \neg q)$$$$

is false.

No, that does not follow. (and obviously $$\neg r \land \neg q$$ is not equivalent to $$False$$)

Consider: $$p \lor p \equiv p$$ ... so by your logic, we would have to have that $$p \equiv False$$?

Clearly something is wrong with your logic. At its core, what you are doing is this:

We know that if $$\psi \equiv False$$, then $$\phi \lor \psi \equiv \phi$$. But the converse is not true: if $$\phi \lor \psi \equiv \phi$$, then $$\psi \equiv False$$. In effect, you are making the logical fallacy of affirming the consequent.

OK, but why does the converse not hold? What follows below will provide some further insight.

As a general helpful principle, note that $$p \lor (p \land q) \equiv p$$:

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

$$\overset{Identity}{\equiv}$$

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

$$\overset{Distribution}{\equiv}$$

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

$$\overset{Annihilation}{\equiv}$$

$$p \land \top$$

$$\overset{Identity}{\equiv}$$

$$p$$

That first step is a little tricky, but you can also think of this as:

$$p + pq = p(1+q) = p1 = p$$

This principle is so common, that is has a name:

Absorption

$$p + pq = p$$

and its dual: $$p(p+q) = p$$

So, if you apply Absorption to your statement, you get:

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

$$\overset{Absorption}{\equiv}$$

$$\neg p \vee \neg q$$

Yeah, it's that easy. So make sure to put Absorption in your Boolean Algebra toolkit!

Also if you look at what happens in a K-Map, you'll immediately notice why it's called Absorption: The one term is 'absorbed' by the other term: that's why it can be removed!

So, going back to your earlier mistake: $$p \lor p \equiv p$$ not because $$p \equiv False$$, but because the second $$p$$ is already covered by the first $$p$$. Put differently: it's not that the second $$p$$ is doing nothing but because the second $$p$$ term isn't doing anything over and above the first term.

Likewise, $$\neg q \lor (\neg r \land \neg q) \equiv \neg q$$ not because $$\neg r \land \neg q$$ is doing nothing, but because it is doing nothing over and above $$\neg q$$ by itself: the $$\neg q$$ 'covers', and thus 'absorbs' the $$\neg r \land \neg q$$ term

• Thank you for the elaborate answer!
– Tim
Mar 12, 2022 at 14:31
• @Tim You’re welcome! Mar 12, 2022 at 20:26
• It’s a great answer that deserves to be accepted! Mar 13, 2022 at 8:56
• Thanks @VoiletFlame ! Mar 14, 2022 at 0:06