Why is this part of the composed proposition false?

Question

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{equation} \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} \end{equation}

I understand that

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

so that implies that

\begin{equation} (\neg \boldsymbol{r} \wedge \neg q) \end{equation}

is false.

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

Whole question + solution:

Answer 1

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

Answer 2

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

I understand that

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

so that implies that

\begin{equation} (\neg \boldsymbol{r} \wedge \neg q) \end{equation}

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