1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Discrete Math: Proving something is logically equivalent

  1. Mar 10, 2012 #1
    1. The problem statement, all variables and given/known data
    Show that (p ∧ q) → r and (p → r) ∧ (q → r) are not
    logically equivalent.

    2. Relevant equations
    a → b = [itex]\neg[/itex]a v b

    3. The attempt at a solution
    I'm sorry. I'm completely stumped on how to go about this problem. I'm not asking for the solution since I want to know how to do this instead of just getting the answer. Any help would be appreciated. Thank you.
    Here is what I had just so no one thinks I didn't try.

    (p ∧ q) → r
    => [itex]\neg[/itex] ( p [itex]\wedge[/itex] q ) [itex]\vee[/itex] r
    => ([itex]\neg[/itex]p [itex]\wedge[/itex] [itex]\neg[/itex]q ) [itex]\vee[/itex] r
    => (switched it around) r [itex]\vee[/itex] ([itex]\neg[/itex]p [itex]\wedge[/itex] [itex]\neg[/itex]q )
    => (distributed) (r [itex]\vee[/itex] [itex]\neg[/itex]p ) [itex]\wedge[/itex] ( r v [itex]\neg[/itex] q)
    => ([itex]\neg[/itex]p v r ) [itex]\wedge[/itex] ([itex]\neg[/itex]q v r )
    => (p -> r ) [itex]\wedge[/itex] (q -> r)

    It said disprove but somehow I'm getting that they are L.E.
    Last edited: Mar 10, 2012
  2. jcsd
  3. Mar 10, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper

    If you want to prove they are not equivalent then just figure out how you can assign true and false values to p, q and r so that the two sides give you different values.
  4. Mar 10, 2012 #3
    That makes sense. Here is what I got, please correct me if I'm wrong.

    p = true
    q = false
    r = false
    then (p ∧ q) → r is true.
    and (p → r) ∧ (q → r) is false.
    Hence it's not L.E.

    Any mistakes?
  5. Mar 10, 2012 #4


    User Avatar
    Science Advisor
    Homework Helper

    Looks ok to me. true → false is false. false → false is true.
    Last edited: Mar 10, 2012
  6. Mar 10, 2012 #5


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    As far as the original logic goes...

    Your problem is here.
    not (p and q) = (not p OR not q)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook