I'm studying for my upcoming discrete math test and I'm having trouble understanding some equivalences...

valtricotinevh

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:
( n o t   P   a n d   n o t   Q )   o r   ( n o t   Q   a n d   n o t   R )
⇐⇒ ( n o t   P   o r   ( n o t   Q   o r   n o t   R ) )   a n d   ( n o t   Q   o r   ( n o t   Q   o r   n o t   R ) )
⇐⇒ ( n o t   P   o r   n o t   Q   o r   n o t   R )   a n d   ( n o t   Q   o r   n o t   Q   o r   n o t   R )
⇐⇒ ( n o t   P   o r   n o t   Q   o r   n o t   R )   a n d   ( n o t   Q   o r   n o t   R )

Answer & Explanation

Selden1f

Selden1f

Expert

2022-07-17Added 14 answers

Step 1
The only step that should cause any trouble is the first, the equivalence of
( ¬ P ¬ Q ) ( ¬ Q ¬ R )
with ( ¬ P ( ¬ Q ¬ R ) ) ( ¬ Q ( ¬ Q ¬ R ) ) ;
from that to ( ¬ P ¬ Q ¬ R ) ( ¬ Q ¬ Q ¬ R )
is just removing redundant parentheses, and from that to ( ¬ P ¬ Q ¬ R ) ( ¬ Q ¬ R )
just uses the fact that X 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 ( ¬ P ¬ Q ) ( ¬ Q ¬ R ) ;
if that is indeed the case, the first step is just an application of distributivity of ∨ over ∧, i.e., of the equivalence of ( X Y ) Z with ( X Z ) ( Y Z ); ¬ P is the X, ¬ Q is the Y, and ( ¬ Q ¬ R ) is the Z.
kadejoset

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?
(1) ( ¬ P ¬ Q ) ( ¬ Q ¬ R ) ( ¬ P ( ¬ Q ¬ R ) ) ( ¬ Q ( ¬ Q ¬ R ) ) (2) ( ¬ P ¬ Q ¬ R ) ( ¬ Q ¬ Q ¬ R ) (3) ( ¬ P ¬ Q ¬ R ) ( ¬ Q ¬ R )
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:
( ϕ ψ ) σ ( ϕ σ ) ( ψ σ )
should state that:
(1*) ( ¬ P ϕ ¬ Q ψ ) ( ¬ Q ¬ R ) σ ( ¬ P ϕ ( ¬ Q ¬ R ) σ ) ( ¬ Q ψ ( ¬ Q ¬ R ) σ )
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
( n o t   P   a n d   n o t   Q )   o r   ( n o t   Q   a n d   n o t   R )
⇐⇒ ( n o t   P   o r   ( n o t   Q   a n d   n o t   R ) )   a n d   ( n o t   Q   o r   ( n o t   Q   a n d   n o t   R ) )
⇐⇒ ( n o t   P   o r   n o t   Q   a n d   n o t   R )   a n d   ( n o t   Q   o r   n o t   Q   a n d   n o t   R )
⇐⇒ ( n o t   P   o r   n o t   Q   a n d   n o t   R )   a n d   ( n o t   Q   a n d   n o t   R )
or ( n o t   P   a n d   n o t   Q )   o r   ( n o t   Q   o r   n o t   R )
⇐⇒ ( n o t   P   o r   ( n o t   Q   o r   n o t   R ) )   a n d   ( n o t   Q   o r   ( n o t   Q   o r   n o t   R ) )
⇐⇒ ( n o t   P   o r   n o t   Q   o r   n o t   R )   a n d   ( n o t   Q   o r   n o t   Q   o r   n o t   R )
⇐⇒ ( n o t   P   o r   n o t   Q   o r   n o t   R )   a n d   ( n o t   Q   o r   n o t   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:
(1') ( ¬ P ¬ Q ) ( ¬ Q ¬ R ) ( ¬ P ( ¬ Q ¬ R ) ) ( ¬ Q ( ¬ Q ¬ R ) ) (2') ( ¬ P ¬ Q ¬ R ) ( ¬ Q ¬ Q ¬ R ) (3') ( ¬ P ¬ Q ¬ R ) ( ¬ Q ¬ R )
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?

Recalculate according to your conditions!

Ask your question.
Get your answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?