valtricotinevh

Answered

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:

$(not\text{}P\text{}and\text{}not\text{}Q)\text{}or\text{}(not\text{}Q\text{}and\text{}not\text{}R)$

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

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

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

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\text{}P\text{}and\text{}not\text{}Q)\text{}or\text{}(not\text{}Q\text{}and\text{}not\text{}R)$

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

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

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

Answer & Explanation

Selden1f

Expert

2022-07-17Added 14 answers

Step 1

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

$(\mathrm{\neg}P\wedge \mathrm{\neg}Q)\vee (\mathrm{\neg}Q\wedge \mathrm{\neg}R)$

with $(}\mathrm{\neg}P\vee (\mathrm{\neg}Q\vee \mathrm{\neg}R){\textstyle )}\wedge {\textstyle (}\mathrm{\neg}Q\vee (\mathrm{\neg}Q\vee \mathrm{\neg}R){\textstyle )}\phantom{\rule{thickmathspace}{0ex}};$

from that to $(\mathrm{\neg}P\vee \mathrm{\neg}Q\vee \mathrm{\neg}R)\wedge (\mathrm{\neg}Q\vee \mathrm{\neg}Q\vee \mathrm{\neg}R)$

is just removing redundant parentheses, and from that to $(\mathrm{\neg}P\vee \mathrm{\neg}Q\vee \mathrm{\neg}R)\wedge (\mathrm{\neg}Q\vee \mathrm{\neg}R)$

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 $(\mathrm{\neg}P\wedge \mathrm{\neg}Q)\vee (\mathrm{\neg}Q\vee \mathrm{\neg}R)\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 $(X\wedge Y)\vee Z$ with $(X\vee Z)\wedge (Y\vee Z)$; $\mathrm{\neg}P$ is the X, $\mathrm{\neg}Q$ is the Y, and $(\mathrm{\neg}Q\vee \mathrm{\neg}R)$ is the Z.

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

$(\mathrm{\neg}P\wedge \mathrm{\neg}Q)\vee (\mathrm{\neg}Q\wedge \mathrm{\neg}R)$

with $(}\mathrm{\neg}P\vee (\mathrm{\neg}Q\vee \mathrm{\neg}R){\textstyle )}\wedge {\textstyle (}\mathrm{\neg}Q\vee (\mathrm{\neg}Q\vee \mathrm{\neg}R){\textstyle )}\phantom{\rule{thickmathspace}{0ex}};$

from that to $(\mathrm{\neg}P\vee \mathrm{\neg}Q\vee \mathrm{\neg}R)\wedge (\mathrm{\neg}Q\vee \mathrm{\neg}Q\vee \mathrm{\neg}R)$

is just removing redundant parentheses, and from that to $(\mathrm{\neg}P\vee \mathrm{\neg}Q\vee \mathrm{\neg}R)\wedge (\mathrm{\neg}Q\vee \mathrm{\neg}R)$

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 $(\mathrm{\neg}P\wedge \mathrm{\neg}Q)\vee (\mathrm{\neg}Q\vee \mathrm{\neg}R)\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 $(X\wedge Y)\vee Z$ with $(X\vee Z)\wedge (Y\vee Z)$; $\mathrm{\neg}P$ is the X, $\mathrm{\neg}Q$ is the Y, and $(\mathrm{\neg}Q\vee \mathrm{\neg}R)$ is the Z.

kadejoset

Expert

2022-07-18Added 2 answers

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)}& (\mathrm{\neg}P\wedge \mathrm{\neg}Q)\vee (\mathrm{\neg}Q\wedge \mathrm{\neg}R)& \equiv (\mathrm{\neg}P\vee (\mathrm{\neg}Q\vee \mathrm{\neg}R))\wedge (\mathrm{\neg}Q\vee (\mathrm{\neg}Q\vee \mathrm{\neg}R))\text{(2)}& & \equiv (\mathrm{\neg}P\vee \mathrm{\neg}Q\vee \mathrm{\neg}R)\wedge (\mathrm{\neg}Q\vee \mathrm{\neg}Q\vee \mathrm{\neg}R)\text{(3)}& & \equiv (\mathrm{\neg}P\vee \mathrm{\neg}Q\vee \mathrm{\neg}R)\wedge (\mathrm{\neg}Q\vee \mathrm{\neg}R)\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 (\varphi \wedge \psi )\vee \sigma \equiv (\varphi \vee \sigma )\wedge (\psi \vee \sigma )$

should state that:

$\begin{array}{}\text{(1*)}& (\underset{\varphi}{\underset{\u23df}{\mathrm{\neg}P}}\wedge \underset{\psi}{\underset{\u23df}{\mathrm{\neg}Q}})\vee \underset{\sigma}{\underset{\u23df}{(\mathrm{\neg}Q\wedge \mathrm{\neg}R)}}& \equiv (\underset{\varphi}{\underset{\u23df}{\mathrm{\neg}P}}\vee \underset{\sigma}{\underset{\u23df}{(\mathrm{\neg}Q\wedge \mathrm{\neg}R)}})\wedge (\underset{\psi}{\underset{\u23df}{\mathrm{\neg}Q}}\vee \underset{\sigma}{\underset{\u23df}{(\mathrm{\neg}Q\wedge \mathrm{\neg}R)}})\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

$(not\text{}P\text{}and\text{}not\text{}Q)\text{}or\text{}(not\text{}Q\text{}and\text{}not\text{}R)$

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

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

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

or $(not\text{}P\text{}and\text{}not\text{}Q)\text{}or\text{}(not\text{}Q\text{}{or}\text{}not\text{}R)$

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

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

$\Leftarrow \Rightarrow (not\text{}P\text{}or\text{}not\text{}Q\text{}or\text{}not\text{}R)\text{}and\text{}(not\text{}Q\text{}or\text{}not\text{}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{array}{r}\text{(1')}& (\mathrm{\neg}P\wedge \mathrm{\neg}Q)\vee (\mathrm{\neg}Q\vee \mathrm{\neg}R)& \equiv (\mathrm{\neg}P\vee (\mathrm{\neg}Q\vee \mathrm{\neg}R))\wedge (\mathrm{\neg}Q\vee (\mathrm{\neg}Q\vee \mathrm{\neg}R))\text{(2')}& & \equiv (\mathrm{\neg}P\vee \mathrm{\neg}Q\vee \mathrm{\neg}R)\wedge (\mathrm{\neg}Q\vee \mathrm{\neg}Q\vee \mathrm{\neg}R)\text{(3')}& & \equiv (\mathrm{\neg}P\vee \mathrm{\neg}Q\vee \mathrm{\neg}R)\wedge (\mathrm{\neg}Q\vee \mathrm{\neg}R)\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 ∨.

(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)}& (\mathrm{\neg}P\wedge \mathrm{\neg}Q)\vee (\mathrm{\neg}Q\wedge \mathrm{\neg}R)& \equiv (\mathrm{\neg}P\vee (\mathrm{\neg}Q\vee \mathrm{\neg}R))\wedge (\mathrm{\neg}Q\vee (\mathrm{\neg}Q\vee \mathrm{\neg}R))\text{(2)}& & \equiv (\mathrm{\neg}P\vee \mathrm{\neg}Q\vee \mathrm{\neg}R)\wedge (\mathrm{\neg}Q\vee \mathrm{\neg}Q\vee \mathrm{\neg}R)\text{(3)}& & \equiv (\mathrm{\neg}P\vee \mathrm{\neg}Q\vee \mathrm{\neg}R)\wedge (\mathrm{\neg}Q\vee \mathrm{\neg}R)\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 (\varphi \wedge \psi )\vee \sigma \equiv (\varphi \vee \sigma )\wedge (\psi \vee \sigma )$

should state that:

$\begin{array}{}\text{(1*)}& (\underset{\varphi}{\underset{\u23df}{\mathrm{\neg}P}}\wedge \underset{\psi}{\underset{\u23df}{\mathrm{\neg}Q}})\vee \underset{\sigma}{\underset{\u23df}{(\mathrm{\neg}Q\wedge \mathrm{\neg}R)}}& \equiv (\underset{\varphi}{\underset{\u23df}{\mathrm{\neg}P}}\vee \underset{\sigma}{\underset{\u23df}{(\mathrm{\neg}Q\wedge \mathrm{\neg}R)}})\wedge (\underset{\psi}{\underset{\u23df}{\mathrm{\neg}Q}}\vee \underset{\sigma}{\underset{\u23df}{(\mathrm{\neg}Q\wedge \mathrm{\neg}R)}})\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

$(not\text{}P\text{}and\text{}not\text{}Q)\text{}or\text{}(not\text{}Q\text{}and\text{}not\text{}R)$

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

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

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

or $(not\text{}P\text{}and\text{}not\text{}Q)\text{}or\text{}(not\text{}Q\text{}{or}\text{}not\text{}R)$

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

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

$\Leftarrow \Rightarrow (not\text{}P\text{}or\text{}not\text{}Q\text{}or\text{}not\text{}R)\text{}and\text{}(not\text{}Q\text{}or\text{}not\text{}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{array}{r}\text{(1')}& (\mathrm{\neg}P\wedge \mathrm{\neg}Q)\vee (\mathrm{\neg}Q\vee \mathrm{\neg}R)& \equiv (\mathrm{\neg}P\vee (\mathrm{\neg}Q\vee \mathrm{\neg}R))\wedge (\mathrm{\neg}Q\vee (\mathrm{\neg}Q\vee \mathrm{\neg}R))\text{(2')}& & \equiv (\mathrm{\neg}P\vee \mathrm{\neg}Q\vee \mathrm{\neg}R)\wedge (\mathrm{\neg}Q\vee \mathrm{\neg}Q\vee \mathrm{\neg}R)\text{(3')}& & \equiv (\mathrm{\neg}P\vee \mathrm{\neg}Q\vee \mathrm{\neg}R)\wedge (\mathrm{\neg}Q\vee \mathrm{\neg}R)\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 ∨.

Most Popular Questions