XOR elimination: A XOR B = (A AND NOT B) OR (NOT A AND B)
XOR elimination rewrites A XOR B as (A AND NOT B) OR (NOT A AND B): the first true and the second false, or the other way round.
XOR is rewritten as “first true and second false” OR “first false and second true”.
XOR means “exactly one of the two”, and the right-hand side lists the two ways that can happen. This is the disjunctive normal form of XOR, and the law is how the engine gets from a formula with XOR to one with AND, OR and NOT before converting to a normal form or building gates. The dual rewriting, (A OR B) AND (NOT A OR NOT B), is XOR's conjunctive normal form, and the engine proves both.
The worked example on building XOR from AND, OR and NOT shows the law as a verified equivalence, and the NAND-only example shows the classic four-gate XOR that results from pushing it through De Morgan.
Keep in mind that the law is for two operands. For three, A XOR B XOR C is odd parity, not “exactly one”; the pitfall page shows the row where the two readings differ.
Statement
A XOR B = (A AND NOT B) OR (NOT A AND B) Proof by truth table: A XOR B = (A AND NOT B) OR (NOT A AND B)
| # | A | B | lhs | rhs |
|---|---|---|---|---|
| 0 | FALSE | FALSE | FALSE | FALSE |
| 1 | FALSE | TRUE | TRUE | TRUE |
| 2 | TRUE | FALSE | TRUE | TRUE |
| 3 | TRUE | TRUE | FALSE | FALSE |
The same law in four notations
A XOR BA XOR BA ⊕ BA ⊕ BA \oplus B(A AND NOT B) OR (NOT A AND B)(A && !B) || (!A && B)(A ∧ ¬B) ∨ (¬A ∧ B)(A·B') + (A'·B)\left(A \cdot \overline{B}\right) + \left(\overline{A} \cdot B\right)The common slip
Eliminating a three-input XOR as “exactly one of the three”. The elimination law applies to one binary XOR at a time; the chain means parity.
Questions
Is XOR the same as “not equal”?
On Boolean values, yes: A XOR B is true exactly when A and B differ, which is why the parser offers XOR as the repair when you type A != B.
Related
Lesson that teaches this
Pitfalls
Tools
- Boolean algebra calculator and simplifier with steps (every law named and verified)
- Logical equivalence checker: two expressions, exact verdict, counterexample
See also
- XOR gate: truth table for 2, 3 and 4 inputs (odd parity, not “exactly one”)
- XOR built from AND, OR and NOT
- XOR with four NAND gates, verified equivalent
- XOR of three inputs is odd parity, not “exactly one”
- != on Booleans is XOR
Laws
Generated from the Tangibool engine, semantics tangibool-semantics/1, engine 1.0.0, build . Every table, map, simplification and verdict on these pages was computed by the Tangibool engine when the site was built, and every claim was re-checked by the same exact checker the app uses. Limits are stated where they apply. © 2026 Foreranger LTD.