valtricotinevh

2022-07-16

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:

Selden1f

Expert

Step 1
The only step that should cause any trouble is the first, the equivalence of
$\left(\mathrm{¬}P\wedge \mathrm{¬}Q\right)\vee \left(\mathrm{¬}Q\wedge \mathrm{¬}R\right)$
with $\left(\mathrm{¬}P\vee \left(\mathrm{¬}Q\vee \mathrm{¬}R\right)\right)\wedge \left(\mathrm{¬}Q\vee \left(\mathrm{¬}Q\vee \mathrm{¬}R\right)\right)\phantom{\rule{thickmathspace}{0ex}};$
from that to $\left(\mathrm{¬}P\vee \mathrm{¬}Q\vee \mathrm{¬}R\right)\wedge \left(\mathrm{¬}Q\vee \mathrm{¬}Q\vee \mathrm{¬}R\right)$
is just removing redundant parentheses, and from that to $\left(\mathrm{¬}P\vee \mathrm{¬}Q\vee \mathrm{¬}R\right)\wedge \left(\mathrm{¬}Q\vee \mathrm{¬}R\right)$
just uses the fact that $X\vee 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 $\left(\mathrm{¬}P\wedge \mathrm{¬}Q\right)\vee \left(\mathrm{¬}Q\vee \mathrm{¬}R\right)\phantom{\rule{thickmathspace}{0ex}};$
if that is indeed the case, the first step is just an application of distributivity of ∨ over ∧, i.e., of the equivalence of $\left(X\wedge Y\right)\vee Z$ with $\left(X\vee Z\right)\wedge \left(Y\vee Z\right)$; $\mathrm{¬}P$ is the X, $\mathrm{¬}Q$ is the Y, and $\left(\mathrm{¬}Q\vee \mathrm{¬}R\right)$ is the Z.

Expert

Step 1
(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 '¬' stand for negation, '∧' for conjunction and '∨' for disjunction. Is the reasoning below what you mean?
$\begin{array}{r}\text{(1)}& \left(\mathrm{¬}P\wedge \mathrm{¬}Q\right)\vee \left(\mathrm{¬}Q\wedge \mathrm{¬}R\right)& \equiv \left(\mathrm{¬}P\vee \left(\mathrm{¬}Q\vee \mathrm{¬}R\right)\right)\wedge \left(\mathrm{¬}Q\vee \left(\mathrm{¬}Q\vee \mathrm{¬}R\right)\right)\text{(2)}& & \equiv \left(\mathrm{¬}P\vee \mathrm{¬}Q\vee \mathrm{¬}R\right)\wedge \left(\mathrm{¬}Q\vee \mathrm{¬}Q\vee \mathrm{¬}R\right)\text{(3)}& & \equiv \left(\mathrm{¬}P\vee \mathrm{¬}Q\vee \mathrm{¬}R\right)\wedge \left(\mathrm{¬}Q\vee \mathrm{¬}R\right)\end{array}$
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:
$\models \left(\varphi \wedge \psi \right)\vee \sigma \equiv \left(\varphi \vee \sigma \right)\wedge \left(\psi \vee \sigma \right)$
should state that:
$\begin{array}{}\text{(1*)}& \left(\underset{\varphi }{\underset{⏟}{\mathrm{¬}P}}\wedge \underset{\psi }{\underset{⏟}{\mathrm{¬}Q}}\right)\vee \underset{\sigma }{\underset{⏟}{\left(\mathrm{¬}Q\wedge \mathrm{¬}R\right)}}& \equiv \left(\underset{\varphi }{\underset{⏟}{\mathrm{¬}P}}\vee \underset{\sigma }{\underset{⏟}{\left(\mathrm{¬}Q\wedge \mathrm{¬}R\right)}}\right)\wedge \left(\underset{\psi }{\underset{⏟}{\mathrm{¬}Q}}\vee \underset{\sigma }{\underset{⏟}{\left(\mathrm{¬}Q\wedge \mathrm{¬}R\right)}}\right)\end{array}$
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

or

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{array}{r}\text{(1')}& \left(\mathrm{¬}P\wedge \mathrm{¬}Q\right)\vee \left(\mathrm{¬}Q\vee \mathrm{¬}R\right)& \equiv \left(\mathrm{¬}P\vee \left(\mathrm{¬}Q\vee \mathrm{¬}R\right)\right)\wedge \left(\mathrm{¬}Q\vee \left(\mathrm{¬}Q\vee \mathrm{¬}R\right)\right)\text{(2')}& & \equiv \left(\mathrm{¬}P\vee \mathrm{¬}Q\vee \mathrm{¬}R\right)\wedge \left(\mathrm{¬}Q\vee \mathrm{¬}Q\vee \mathrm{¬}R\right)\text{(3')}& & \equiv \left(\mathrm{¬}P\vee \mathrm{¬}Q\vee \mathrm{¬}R\right)\wedge \left(\mathrm{¬}Q\vee \mathrm{¬}R\right)\end{array}$
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 ∨.

Do you have a similar question?