# Negation of “Either X is true, or Y is true, but not both”

Negation of "Either X is true, or Y is true, but not both"

My attempt:

If seems that let X be true and Y be true, not X for X is false and not Y for Y is false. In order for the above statement to be True, we need:

The negation of both X and Y to be true: negate(X and Y) -> not X or not Y

For "Either X is true, or Y is true, but not both" is equivalent to below:

((X or Y) and (not X or not Y))

The negation of the above (negation turns "and" into "or", and turns "or" into "and"):

((not X and not Y) or (X and Y))

Is this logical or? I am pretty lost...

• This would be logical biconditional, i.e., the negation is true if and only if $X$ and $Y$ have the same truth value. But your work is correct. An easier way to try to visualize this might be with a truth table. – Hayden Jun 3 at 22:06
• This proof tree might help. – Shaun Jun 3 at 22:24
• Why not just X=Y? – n0rd Jun 4 at 22:09

A basic approach is to see there only are 4 possibilities:

1. $$X$$ and $$Y$$
2. $$X$$ and not $$Y$$
3. not $$X$$ and $$Y$$
4. not $$X$$ and not $$Y$$

Your statement was (2) or (3), so its negation is (1) or (4).

I give a solution by formal calculation: translate the phrase into logical symbols, we have $$\text{negation}\rightarrow\neg$$, $$\text{either X or Y is true}\rightarrow X\lor Y$$, $$\text{but not both}\rightarrow\land\neg(X\land Y)$$. Then

$$\neg((X\lor Y)\land\neg(X\land Y)=\neg(X\lor Y)\lor(\neg\neg(X\land Y))=(\neg X\land\neg Y)\lor(X\land Y)$$

The final result is identical to yours.

Either $$X$$ is true, or $$Y$$ but not both is

($$X$$ OR $$Y$$) AND (NOT [$$X$$ AND $$Y$$])

Now the negation of $$A$$ AND $$B$$ is:

(not A) OR (not B).

So the negation is:

[NOT (X OR Y)] OR (NOT(NOT([X AND Y]))

And NOT(NOT(A)) is .. A so

[NOT (X OR Y)] OR [X AND Y]

And the negation of A OR B is: (NOT A) AND (NOT B).

So

(NOT X AND NOT Y) OR (X AND Y)

So the negation is

Either both X and Y are true, or both X and Y are false.

Maybe that is what it intuitively what you would have thought.