Identifying laws in a discrete math example

Question

I'm studying for my upcoming discrete math test and I'm having trouble understanding some equivalences I found in a book on the subject. I guess I'm not really familiar with these rules and I would like someone to walk me through the steps if they don't mind.

I know the elementary laws, De-Morgan's, absorption, distribution, associativity, symmetry, and idempotent laws. But I don't recognize how this person transforms the predicates. Could someone point out the name of the law I need to study?

The transformations are as follows:

$$(not\ P\ and\ not\ Q)\ or\ (not\ Q\ and\ not\ R)$$ $$\Leftarrow\Rightarrow (not\ P\ or\ (not\ Q\ or\ not\ R))\ and\ (not\ Q\ or\ (not\ Q\ or\ not\ R))$$ $$\Leftarrow\Rightarrow (not\ P\ or\ not\ Q\ or\ not\ R)\ and\ (not\ Q\ or\ not\ Q\ or\ not\ R)$$ $$\Leftarrow\Rightarrow (not\ P\ or\ not\ Q\ or\ not\ R)\ and\ (not\ Q\ or\ not\ R)$$

Edit:

So I looked back at the book and the typo is in the book itself.

Answer 1

Corrected. (Thanks to B Bentzen for pointing out that I failed to notice the typo in the question.

The only step that should cause any trouble is the first, the equivalence of

$$(\neg P\land\neg Q)\lor(\neg Q\land\neg R)$$

with

$$\big(\neg P\lor(\neg Q\lor\neg R)\big)\land\big(\neg Q\lor(\neg Q\lor\neg R)\big)\;;$$

from that to

$$(\neg P\lor\neg Q\lor\neg R)\land(\neg Q\lor\neg Q\lor\neg R)$$

is just removing redundant parentheses, and from that to

$$(\neg P\lor\neg Q\lor\neg R)\land(\neg Q\lor\neg R)$$

just uses the fact that $X\lor X$ is equivalent to $X$.

The first step is actually impossible as it stands: if $Q$ is false and $P$ and $R$ are true, the second line is true, but the first is false. It appears from the bulk of the problem that the first line was supposed to read

$$(\neg P\land\neg Q)\lor(\neg Q\lor\neg R)\;;$$

if that is indeed the case, the first step is just an application of distributivity of $\lor$ over $\land$, i.e., of the equivalence of $(X\land Y)\lor Z$ with $(X\lor Z)\land(Y\lor Z)$; $\neg P$ is the $X$, $\neg Q$ is the $Y$, and $(\neg Q\lor\neg R)$ is the $Z$.

Answer 2

(1) Put the argument in adequate symbolism:

Statements in ordinary language like the above reasoning may be misleading, ambiguous confusing. Therefore, let us prove it an adequate symbollism. Let '$\neg$' stand for negation, '$\wedge$' for conjunction and '$\vee$' for disjunction. Is the reasoning below what you mean?

$$\begin{align} (\lnot P \wedge \lnot Q) \lor (\lnot Q \land \lnot R) & \equiv (\lnot P \lor (\lnot Q \lor \lnot R)) \land (\lnot Q \lor (\lnot Q \lor \lnot R)) \tag{1} \\ &\equiv (\lnot P \lor \lnot Q \lor \lnot R) \land (\lnot Q \lor \lnot Q \lor \lnot R) \tag{2} \\ &\equiv (\lnot P \lor \lnot Q \lor \lnot R) \land (\lnot Q \lor \lnot R) \tag{3}\\ \\ \end{align}$$

One might say that the first step (1) is an application of distributivity of ∨ over ∧. I am afraid this would be incorrect.

As we know, the distributivity of ∨ over ∧, in symbols:

$\vDash (\phi \land \psi)\lor \sigma \equiv (\phi \lor \sigma)\land(\psi \lor \sigma)$

should state that: $$\begin{align} (\underbrace{\lnot P}_{\phi} \wedge \underbrace{\lnot Q}_{\psi}) \lor \underbrace{(\lnot Q \land \lnot R)}_{\sigma} & \equiv (\underbrace{\lnot P}_{\phi} \lor \underbrace{(\lnot Q \land \lnot R)}_{\sigma}) \land (\underbrace{\lnot Q}_{\psi} \lor \underbrace{(\lnot Q \land \lnot R)}_{\sigma}) \tag{1*} \\ \end{align}$$

Which as we see in the formalism above, is not the case. In fact (1) is not a logical equivalence at all (you can check it by a simple truth table).

(2) Typo:

We probably have a typo in the OP's question: presumably, it was supposed to be either

$$(not\ P\ and\ not\ Q)\ or\ (not\ Q\ and\ not\ R)$$ $$\Leftarrow\Rightarrow (not\ P\ or\ (not\ Q\ \color{red}{and}\ not\ R))\ and\ (not\ Q\ or\ (not\ Q\ \color{red}{and}\ not\ R))$$ $$\Leftarrow\Rightarrow (not\ P\ or\ not\ Q\ \color{red}{and}\ not\ R)\ and\ (not\ Q\ or\ not\ Q\ \color{red}{and}\ not\ R)$$ $$\Leftarrow\Rightarrow (not\ P\ or\ not\ Q\ \color{red}{and}\ not\ R)\ and\ (not\ Q\ \color{red}{and}\ not\ R)$$

or

$$(not\ P\ and\ not\ Q)\ or\ (not\ Q\ \color{red}{or}\ not\ R)$$ $$\Leftarrow\Rightarrow (not\ P\ or\ (not\ Q\ or\ not\ R))\ and\ (not\ Q\ or\ (not\ Q\ or\ not\ R))$$ $$\Leftarrow\Rightarrow (not\ P\ or\ not\ Q\ or\ not\ R)\ and\ (not\ Q\ or\ not\ Q\ or\ not\ R)$$ $$\Leftarrow\Rightarrow (not\ P\ or\ not\ Q\ or\ not\ R)\ and\ (not\ Q\ or\ not\ R)$$

Given the argument's structure, I bet in the second one (the first one is nonsense). In this case, we have the following correction of the formal reasoning above:

$$\begin{align} (\lnot P \wedge \lnot Q) \lor (\lnot Q \lor \lnot R) & \equiv (\lnot P \lor (\lnot Q \lor \lnot R)) \land (\lnot Q \lor (\lnot Q \lor \lnot R)) \tag{1'} \\ &\equiv (\lnot P \lor \lnot Q \lor \lnot R) \land (\lnot Q \lor \lnot Q \lor \lnot R) \tag{2'} \\ &\equiv (\lnot P \lor \lnot Q \lor \lnot R) \land (\lnot Q \lor \lnot R) \tag{3'}\\ \\ \end{align}$$

In (1') we have an application of the distributivity of ∨ over ∧.

In (2') we are justified by the associativity of ∨.

In (3') we have an application of the idempotency of ∨.