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

Help with proving Biconditional equivalence

  1. Nov 11, 2011 #1
    show that P [itex]\leftrightarrow[/itex] Q is equal to (P[itex]\wedge[/itex]Q) [itex]\vee[/itex] ([itex]\neg[/itex]P [itex]\wedge[/itex][itex]\neg[/itex]Q)

    (P→Q) [itex]\wedge[/itex] (Q→P)
    ([itex]\neg[/itex]P[itex]\vee[/itex]Q) [itex]\wedge[/itex] ([itex]\neg[/itex]Q[itex]\vee[/itex]P)



    I don't know which law to use from this point on to prove the equivalence.
  2. jcsd
  3. Nov 11, 2011 #2

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    You started right with going from (P→Q) ∧ (Q→P) to (¬P∨Q) ∧ (¬Q∨P), but from there on you are taking the wrong path. Not invalid; just wrong. That path won't get you to the desired result. Try using distributivity.

    Or just use the dumb approach of showing that P ↔ Q and (P∧Q) ∨ (¬P ∧¬Q) have the identical truth tables.
  4. Nov 11, 2011 #3
    How can I use the distributive law here? I mean, I don't see a common letter with a connective to factor out.
  5. Nov 12, 2011 #4


    User Avatar
    Science Advisor

    Why not just do a truth table?
  6. Nov 12, 2011 #5

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Who said you need a common letter to factor out? All you need is a common item.

    Given a conjunctive normal form (A∨B)∧(C∨D), you can use either (A∨B) or (C∨D) as the common item in applying distributivity. Using (A∨B) as the common item yields ((A∨B)∧C)∨((A∨B)∧D) . (You'll get (A∧(C∨D))∨(B∧(C∨D)) if you use (C∨D) as the common item.) Now apply the distributive law again to put this into disjunctive normal form.

    Perhaps because the instructor said something along the lines of "You can easily prove these conjectures by showing they have the same truth tables. Do that and you will receive zero points on this homework."
  7. Nov 12, 2011 #6


    User Avatar
    Science Advisor

    distributing (¬P∨Q) over (¬Q∨P) we get:

    (¬P∨Q)∧(¬Q∨P) = [(¬P∨Q)∧¬Q]∨[(¬P∨Q)∧P]

    can you see how to continue?
  8. Dec 4, 2011 #7

    Thank you all for helping me with this. I am only self-learning basic logic from a book, and the author never worked out distribution of all of the content in the parentheses to another, so I only thought you could distribute one letter at a time.

    I have a new problem:

    Prove (P [itex]\rightarrow[/itex]Q) [itex]\wedge[/itex] (Q [itex]\rightarrow[/itex] R) = (P [itex]\rightarrow[/itex] R) [itex]\wedge[/itex] [(P [itex]\leftrightarrow[/itex] Q) [itex]\vee[/itex] (Q [itex]\leftrightarrow[/itex] R)]

    I was able to get this far:
    ([itex]\neg[/itex]P [itex]\wedge[/itex] [itex]\neg[/itex]Q) [itex]\vee[/itex] [([itex]\neg[/itex]P [itex]\vee[/itex] Q) [itex]\wedge[/itex] R] = ([itex]\neg[/itex]P [itex]\vee[/itex] R) [itex]\wedge[/itex] [(([itex]\neg[/itex]P [itex]\wedge[/itex] [itex]\neg[/itex]Q) [itex]\vee[/itex] (P [itex]\wedge[/itex] Q)) [itex]\vee[/itex] (([itex]\neg[/itex]R [itex]\wedge[/itex] [itex]\neg[/itex]Q) [itex]\vee[/itex] (R [itex]\wedge[/itex] Q))]

    How should I proceed? Should I continue to expand the left side of the equation or somehow try to reduce the right?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook