Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Using Logical Equivalences to Simplify a Statement

  1. Sep 5, 2016 #1
    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
     
  2. jcsd
  3. Sep 5, 2016 #2

    Mark44

    Staff: Mentor

    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 ∨.
     
    Last edited: Sep 7, 2016
  4. Sep 5, 2016 #3
    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.
     
    Last edited by a moderator: Sep 7, 2016
  5. Sep 5, 2016 #4

    Mark44

    Staff: Mentor

    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.
     
  6. Sep 5, 2016 #5
    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.
     
  7. Sep 6, 2016 #6

    Mark44

    Staff: Mentor

    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").
     
  8. Sep 6, 2016 #7

    Stephen Tashi

    User Avatar
    Science Advisor

    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) ##.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Using Logical Equivalences to Simplify a Statement
  1. Logic statements (Replies: 0)

Loading...