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\)
\(X\) | \(Y\) | \(X \lor Y\) | \(X\land Y\) | \(\lnot(X\land Y)\) | \(\lnot(X \lor Y)\) | \((X \lor Y) \land\lnot(X\land Y)\) | \((\lnot X\land\lnot Y)\lor (X\land Y)\) |
---|---|---|---|---|---|---|---|
T | T | T | T | F | F | F | T |
T | F | T | F | T | F | T | F |
F | T | T | F | T | F | T | F |
F | F | F | F | T | T | F | T |