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

Having trouble with Logic Derivation - please help

  1. Dec 9, 2008 #1
    Hey everyone,

    Thanks for the help in advance. I am having trouble deriving a tautology from no premises.

    I am trying to derive:
    (X <-> Y) v (X <-> -Y) "-" meaning not.

    However, I keep getting stuck. It seems very similar to the Law of the Excluded Middle but I am having trouble changing that derivation. Any help or suggestions of where to start would be appreciated.

  2. jcsd
  3. Dec 9, 2008 #2
    If I'm interpreting your notation correctly, we have the following equation:

    Because we have a contradiction (+Y&-Y) the equation will always be false. I also assume that you are considering that -((X<->Y)v(X<->-Y)) will always be true (tautology).

    In real life, though, double negation does not mean always afirmation (+). And this is one of shortcomings of binary logic you might be trying to transcend. Good luck, but I doubt...

    Kind regards,
  4. Dec 10, 2008 #3
    I agree completely that is seems intuitive that the equation is false. However, I know for a fact that the equation is a tautology. I am using a proofs program that indicates that (X <-> Y) v (X <-> -Y) is a tautology. I believe it is some version of X v -X/law of the excluded middle.

    Any other suggestions??

  5. Dec 10, 2008 #4


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed


    Remember that "v" is false only if both component statements are false.

    Now, the component "if-and-only if"'s are are true only when the truth values of THEIR components are equal.

    In order to prove that the "v"-statement is necessarily true, i.e, a tautology, we start off with assuming that X<->Y is FALSE.
    If we now can prove that this assumption implies that X<->-Y is TRUE, then we have proven the tautology half-ways:

    So, if X<->Y is false, therefore, X and Y has opposite truth values.
    But that means X and -Y MUST have equal truth values, and therefore, X<->-Y is TRUE, and the "v" statement is true as well.

    The other half of the proof assumes that X<->-Y is FALSE.
    Therefore, X and -Y have different truth values, and hence, X and Y have equal truth values, and therefore X<->Y is true, and the QED concerning the proof of the tautological nature of the "v" is within grasp.

    As you suspected, the tautology has everything to do with the excluded middle. :smile:
  6. Dec 10, 2008 #5
    Thank you so much. That explanation makes complete sense. However, I am having trouble formalizing the notion of "since X and Y have opposite truth values, X and -Y have equal truth values". Any suggestions of how to do that via proof? Do I first need to derive X<->Y or should my first assumption just be X<->Y is false and derive X<->-Y from that assumption?

    Again, thanks a lot. I really appreciate the help trying to understand this.
  7. Dec 10, 2008 #6


    Staff: Mentor

    Just do a truth table
    Code (Text):
    X   Y   ~Y   X<->Y   X<->-Y   (X<->Y)v(X<->-Y)
    T   T    F     T       F             T
    T   F    T     F       T             T
    F   T    F     F       T             T
    F   F    T     T       F             T
    Since it is true for all possible values of the premises it is a tautology.
    Last edited: Dec 10, 2008
  8. Dec 10, 2008 #7


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It looks like he's not trying to prove it's a tautology, but rather is trying to derive it using a propositional calculus formal proof system.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook