Undergrad Using Logical Equivalences to Simplify a Statement

[Of Mike and Men]

Hey everyone, I am in a discrete math course, and I was reading pre-reading the textbook (Discrete Mathematics with Applied Applications by Epp 4th Ed.), but didn't understand their example, I don't understand, specifically, the distributive portion. I don't see how they distributed it like that, if someone could expound on it, it'd be great.

Verify ~(~p ∧ q) ∧ (p ∨ q) ≡ p

~(~p ∧ q ) ∧ (p ∨ q) ≡ (~(~p) ∨ ~q) ∧ (p∨q) De Morgan's Laws
≡(p ∨ ~q) ∧ (p ∨ q) Double Negative Law
≡p ∨ (~q ∧ q) Distributive Law (the part I don't understand)
≡ p ∨ ℂ Negation Law
≡ p Identity Law

 

[Mark44]

Hey everyone, I am in a discrete math course, and I was reading pre-reading the textbook (Discrete Mathematics with Applied Applications by Epp 4th Ed.), but didn't understand their example, I don't understand, specifically, the distributive portion. I don't see how they distributed it like that, if someone could expound on it, it'd be great.

Verify ~(~p ∧ q) ∧ (p ∨ q) ≡ p

~(~p ∧ q ) ∧ (p ∨ q) ≡ (~(~p) ∨ ~q) ∧ (p∨q) De Morgan's Laws
≡(p ∨ ~q) ∧ (p ∨ q) Double Negative Law
≡p ∨ (~q ∧ q) Distributive Law (the part I don't understand)

x ∧ (y ∨ z) ≡ ( x ∧ y) ∨ (x ∧ z), right? Each side is equivalent to the other, so you can replace either one with the other. The full name of this property is Distributivity of ∧ over ∨.

≡ p ∨ ℂ Negation Law
≡ p Identity Law

 

[Of Mike and Men]

x ∧ (y ∨ z) ≡ ( x ∧ y) ∨ (x ∧ z), right? Each side is equivalent to the other, so you can replace either one with the other. The full name of this property is Distributivity of ∧ over ∨.

I understand your example, but I'm not seeing it with the example from my op. I guess I'm confused in how this 'distributes' when x = (y ∧ z). Does it foil? Because when following the same method of your post I get:

((p ∨ ~q) ∧ p) ∨ ((p ∨ ~q) ∧ q)), which just turns into a vicious cycle of the same thing over and over when 'simplifying.' I'm obviously not understanding something fundamental with the distributive property, as I'm sure what I wrote is incorrect. I guess my confusion is when your 'x' in your example has multiple terms, so-to-speak i.e. where in algebra it'd be foiled.

 

[Mark44]

Verify ~(~p ∧ q) ∧ (p ∨ q) ≡ p

~(~p ∧ q ) ∧ (p ∨ q) ≡ (~(~p) ∨ ~q) ∧ (p∨q) De Morgan's Laws
≡(p ∨ ~q) ∧ (p ∨ q) Double Negative Law
≡p ∨ (~q ∧ q) Distributive Law (the part I don't understand)

I don't understand the last line either (I misread it in my earlier post), and I think there might be a typo. I believe the last line above should instead be
≡p ∧ (~q ∨ q) Distributive Law
Is what you wrote exactly what is shown in your book?

The next to last line in what I quoted becomes
p ∧ (~q ∨ q)
according to the Distributive Property.

Further simplifying,
~q ∨ q is always true (a tautology), so p ∧ (~q ∨ q) simplifies to just p.

 

[Of Mike and Men]

I don't understand the last line either (I misread it in my earlier post), and I think there might be a typo. I believe the last line above should instead be
≡p ∧ (~q ∨ q) Distributive Law
Is what you wrote exactly what is shown in your book?

The next to last line in what I quoted becomes
p ∧ (~q ∨ q)
according to the Distributive Property.

Further simplifying,
~q ∨ q is always true (a tautology), so p ∧ (~q ∨ q) simplifies to just p.

I double-checked what I had typed, and that line IS correct: p ∨ (~q ∧ q)

However, this isn't the part I'm confused about, forgive me if that's what it seemed like. The confusion is actually from line 2 of the solution to line 3 of the solution, that is the De Morgan's:

≡(p ∨ ~q) ∧ (p ∨ q) Double Negative Law
≡p ∨ (~q ∧ q) Distributive Law (the part I don't understand)

I get this is the part that is a 'typo', however, what I don't understand is how to distribute from the double negative law. When I do so I get: ((p ∨ ~q) ∧ p) ∨ ((p ∨ ~q) ∧ q)). I'm fine with what you've said, and the way the book goes about simplifying with what they have. It's just the distribution I don't understand. Other than the: x ∧ (y ∨ z) ≡ ( x ∧ y) ∨ (x ∧ z).

As for the 'typo' they got that it becomes p or contradiction which is equivalent to p.

 

[Mark44]

However, this isn't the part I'm confused about, forgive me if that's what it seemed like. The confusion is actually from line 2 of the solution to line 3 of the solution, that is the De Morgan's:

≡(p ∨ ~q) ∧ (p ∨ q) Double Negative Law
≡p ∨ (~q ∧ q) Distributive Law (the part I don't understand)

Just to be clear, the text description on each line is the justification for going from the previous line to the line with the description. Maybe you understand that, but I'm not sure.

The Distributive Law takes two forms:
x ∧ (y ∨ z) ≡ (x ∧ y) ∨ (x ∧ y)
and
x ∨ (y ∧ z) ≡ (x ∨ y) ∧ (x ∨ y)

If the latter formula is reversed, you get
(x ∨ y) ∧ (x ∨ y) ≡ x ∨ (y ∧ z)

In the line marked "Double Negative Law" they are using this formulation to rewrite the expression of that line to its revised form on the line below (the line marked "Distributive Law").

I get this is the part that is a 'typo', however, what I don't understand is how to distribute from the double negative law. When I do so I get: ((p ∨ ~q) ∧ p) ∨ ((p ∨ ~q) ∧ q)). I'm fine with what you've said, and the way the book goes about simplifying with what they have. It's just the distribution I don't understand. Other than the: x ∧ (y ∨ z) ≡ ( x ∧ y) ∨ (x ∧ z).

As for the 'typo' they got that it becomes p or contradiction which is equivalent to p.

 

[Stephen Tashi]

≡p ∨ (~q ∧ q) Distributive Law (the part I don't understand)

Do you understand that the distributive law can be used "backwards"? Not only can you go from $A \lor( B \land C)$ to $(A \lor B) \land (A \lor C)$, you can also go from $(A \lor B) \land (A \lor C)$ "back" to $A \lor( B \land C)$.