Tao Analysis I - A.1.1

Appendix A is about mathematical logic, which covers the meaning of specific English phrases, manipulation of logical statements and connectives, and the sturtcure of proofs.

Exercise A.1.1

What is the negation of the statement “either X is true, or Y is true, but not both”?

It is possible to do these kinds of exercises by mechanistically applying transformation rules to the symbolic representation of these statements, but it is useful to think about their actual meaning.

Here the statement expresses an exclusive-or relation between X and Y. That means the statement is true only one of A and B is true, but not both. 

X	Y	XOR
F	F	F
F	T	T
T	F	T
T	T	F

We expect the negation to have the following truth table.

X	Y	¬ XOR
F	F	T
F	T	F
T	F	F
T	T	T

We can see that for the statement to be true, both X and Y have to be true or false.

So the negation of the statement is "X and Y are both false, or X and Y are both true". $\square$

Let's see if symbolic manipulation gives us a simpler result.

Let's write out the original statement symbolically,

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

We mechanistically can negate this by negating each clause, and swapping the and/or connectives,

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

We can write this in English as "None of X or Y are true, or  both X and Y are true". $\square$

This is equivalent to the answer we arrived at, but is less readable.

We could continue the symbolic manipulation to see if it helps,

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

This can be read as "both X and Y are false, or both X and Y are true". $\square$

This is again equivalent and just as readable as the first solution.