Exercise A.1.1

Q. What is the negation of the statement "either x is true, or y is true, but not both"?

A. Our answer to this question is "neither X is true nor Y is true or both are true".

Proof Show that the negation of the statement "either x is true, or y is true, but not both" is "neither X is true nor Y is true or both are true".

• – Logical expression for "either X is true or Y is true" is \(X \lor Y\)

• – Logical expression for "not both" is \(\lnot(X \land Y)\)

• – Logical expression for "either X is true or Y is true, but not both" is \((X \lor Y) \land\lnot(X\land Y)\)

• – Logical expression for "neither X is true nor Y is true" is \(\lnot X \land \lnot Y\)

• – Logical expression for "both are true" is \(X\land Y\)

• \(\Vdash\) \(\lnot((X \lor Y) \land\lnot(X\land Y))\)

• \(\equiv\) { Distribution of negation over \(\land\): \(\lnot (p \land q) \equiv (\lnot p \lor \lnot q)\) }

  • \(\lnot(X \lor Y) \lor \lnot(\lnot(X\land Y))\)

• \(\equiv\) { Double negation: \(\lnot \lnot p \equiv p\) }

  • \(\lnot(X \lor Y) \lor (X\land Y)\)

• \(\equiv\) { Distribution of negation over \(\lor\): $ ¬ (p ∨ q) ≡ (¬ p ∧ ¬ q)$ }

  • \((\lnot X \land \lnot Y) \lor (X\land Y)\)

• \(\equiv\) { By converting the logical expression into a sentence }

  • Neither X is true nor Y is true or both are true

• \(\square\)