Server Bug Fix: Negation of “Either X is true, or Y is true, but not both”

Original Source Link

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…

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}rightarrowneg$, $text{either X or Y is true}rightarrow Xlor Y$, $text{but not both}rightarrowlandneg(Xland Y)$. Then

$neg((Xlor Y)landneg(Xland Y)=neg(Xlor Y)lor(negneg(Xland Y))=(neg Xlandneg Y)lor(Xland 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.

Tagged : /

Leave a Reply

Your email address will not be published. Required fields are marked *