1. Dec 9, 2008

### jax122

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.

Thanks
Jax

2. Dec 9, 2008

### Damir

If I'm interpreting your notation correctly, we have the following equation:
____Y_________-Y__
____+__-______+__-
X+__T__F______T__F
____F__T__OR__F__T

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,

3. Dec 10, 2008

### jax122

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??

Thanks

4. Dec 10, 2008

### arildno

jax:

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.

5. Dec 10, 2008

### jax122

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.

6. Dec 10, 2008

### 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
7. Dec 10, 2008

### Office_Shredder

Staff Emeritus
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.