3.6 XOR Gate: Detecting Difference
Define the XOR gate's 'inputs differ' behavior, derive its Boolean expression from AND/OR/NOT, read its truth table, and connect it to its central role in binary addition.
The XOR (exclusive OR) gate outputs 1 when its two inputs are different from each other, and 0 when they are the same. This is subtly but importantly distinct from plain OR, which outputs 1 whenever at least one input is 1 (including when both are 1); XOR specifically excludes that both-1 case, which is exactly where its name comes from. XOR matters enormously in digital design because 'are these two bits different?' is precisely the question that comparators, parity checkers, and — most importantly — binary adders need answered, making XOR one of the most functionally significant two-input gates in this course despite not being one of the three foundational primitives (NOT, AND, OR) itself.
Core Concept: Exclusive OR — Inputs Must Differ
The spec gives XOR's Boolean expression in two equivalent forms: Y = A ⊕ B (using the dedicated XOR symbol, ⊕) and, expanded into AND/OR/NOT terms, Y = A'B + AB'. Reading the expanded form directly: the output is 1 either when A is 0 and B is 1 (A'B), or when A is 1 and B is 0 (AB') — exactly the two rows where the inputs differ — and 0 in the two rows where they match (both 0, or both 1). This expanded form is important precisely because it proves XOR is not a fourth foundational primitive; it is fully expressible using only AND, OR, and NOT, the three gates already established as sufficient to build anything.
XOR's truth table has two 1-rows and two 0-rows for two inputs, an even split unlike AND (one 1-row) or OR (one 0-row). This structural difference is a useful memory aid: AND and OR are each 'almost always one value, with a single exceptional row', while XOR is exactly half-and-half, driven entirely by whether the two inputs agree or disagree.
• Y = A ⊕ B = A'B + AB' — two equivalent notations for the same function. • Output is 1 exactly when A and B differ; output is 0 exactly when A and B match. • Fully expressible from AND, OR, NOT — XOR is a derived gate, not a fourth primitive. • Truth table is an even 2-and-2 split, unlike AND's and OR's single-exceptional-row structure.
Step-by-Step: From the Expanded Expression to the Truth Table
To evaluate Y = A'B + AB' by hand for a given A and B, compute each product term separately, then OR the two results together. For A=0, B=1: A'B = 1·1 = 1 and AB' = 0·0 = 0, so Y = 1+0 = 1 (inputs differ, output 1, matching the direct 'differ' rule). For A=1, B=1: A'B = 0·1 = 0 and AB' = 1·0 = 0, so Y = 0+0 = 0 (inputs match, output 0). Working through all four rows this way is a useful exercise precisely because it demonstrates, mechanically, that the AND/OR/NOT expansion and the direct 'do the inputs differ?' intuition always agree.
This equivalence — a compact symbol (⊕) standing in for a longer AND/OR/NOT expression — is a pattern you will see repeatedly in this course: every derived gate symbol is shorthand for some combination of the three foundational primitives, and being able to expand a symbol back into that combination on demand is what lets you actually build (or simplify) a circuit rather than just naming it.
• Step 1: Compute A'B (1 only when A=0, B=1). • Step 2: Compute AB' (1 only when A=1, B=0). • Step 3: OR the two results — Y is 1 if either product term is 1, i.e., exactly when A and B differ.
Practical and Real-World Application: The Heart of the Half-Adder
The spec's own example states this directly and it is the single most important real-world fact about XOR in this entire course: XOR is central to half-adders, where SUM = A ⊕ B. Adding two single bits by hand, A + B produces a sum bit and possibly a carry bit; the sum bit is exactly 1 when the two input bits differ (0+1=1, 1+0=1) and exactly 0 when they match (0+0=0, and 1+1=0 with a separate carry of 1) — which is precisely XOR's definition. This direct correspondence is why every binary adder circuit built later in this course (Module 6: Half Adder, Full Adder, Parallel Adder) has an XOR gate at its core.
Beyond addition, XOR is also the standard building block for bit-difference detection generally: comparator circuits use XOR to flag exactly which bit positions differ between two binary numbers, parity generators use chained XOR gates to compute a parity bit over many data bits at once, and the simple 'XOR cipher' in cryptography relies on the fact that XOR-ing a value twice with the same key returns the original value (A ⊕ K ⊕ K = A).
Common Mistake and the Tricky Concept
The spec's flagged tricky point is precise and easy to overlook: XOR means 'inputs are different', not simply 'one input is 1' — and critically, this distinction only becomes visible (and only matters) once you move beyond two inputs. For exactly two inputs, 'differ' and 'exactly one is 1' happen to describe the same thing, which can lull learners into thinking those two phrasings are always equivalent. They are not: for three or more inputs, XOR is defined as computing odd parity (an odd number of 1s among the inputs), not 'exactly one input is 1' — three inputs of 1,1,1 have an odd count (three 1s) and XOR outputs 1, even though it is clearly not the case that 'one input is 1'.
Because of this, always reason about multi-input XOR using the parity definition (does the total count of 1-inputs come out odd?) rather than trying to extend the two-input 'inputs differ' phrasing directly, which stops being well-defined once there are more than two inputs to compare against each other.
XOR Gate Notation and Truth Table
⊕ is the dedicated XOR operator symbol, distinct from + (OR) and · (AND). For more than two inputs, XOR generalizes to an odd-parity function, not a simple 'inputs differ' rule.
Boolean expression:
Y = A ⊕ B
= A'B + AB'
Truth Table:
A | B | Y
---+---+---
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0
Symbol: OR body with an extra curved line at the input sideCode Examples
Adding two single bits by hand, the sum digit is exactly XOR of the two inputs: it is 1 whenever the bits differ, and 0 whenever they match — including the both-1 case, where the true arithmetic result (2, or binary 10) needs a separate carry bit that XOR alone does not produce. This is exactly why the half-adder (Module 6.2) pairs an XOR gate (for SUM) with an AND gate (for CARRY). Expected result: SUM = 1 exactly when A and B differ
SUM = A ⊕ B; a separate AND gate is needed for the carry bit
This confirms the expanded form Y = A'B + AB' agrees with the direct 'inputs differ' rule for A=1, B=0: the two product terms isolate the two 'differ' rows individually (A=0,B=1 and A=1,B=0), and OR-ing them together reproduces the full XOR truth table using only AND, OR, and NOT.
A'B + AB' = 1 whenever exactly one of A, B is 1
SUM = A ⊕ B
A=0, B=0 → SUM = 0 (0+0 = 0, no difference)
A=0, B=1 → SUM = 1 (0+1 = 1, bits differ)
A=1, B=0 → SUM = 1 (1+0 = 1, bits differ)
A=1, B=1 → SUM = 0 (1+1 = 10 → sum bit 0, carry 1)A=1, B=0
A'B = 0 · 0 = 0
AB' = 1 · 1 = 1
Y = A'B + AB' = 0 + 1 = 12-Input XOR Gate
1 exactly on the two rows where A and B differ.
A ══╮
)── Y (OR shape with an extra curved input line)
B ══╯
A | B | Y
---+---+---
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0Important Rules
Y = A ⊕ B = A'B + AB' — two equivalent notations for the same function.
XOR is 1 exactly when its two inputs differ, 0 exactly when they match.
XOR is fully derivable from AND, OR, NOT — not a fourth foundational primitive.
For more than two inputs, XOR generalizes to odd parity (an odd count of 1-inputs), not 'inputs differ'.
Adders, Comparators, and Parity
XOR is the SUM-bit gate of every binary adder (half adders and full adders, Module 6), the core comparison element in bit-difference detectors, the building block of parity generators/checkers used for basic error detection in data transmission, and the operation behind simple XOR-based ciphers, since XOR-ing twice with the same key restores the original value.
How It's Built From Other Gates
both AND outputs How XOR is built from AND/OR/NOT gates: Y = A·B′ + A′·B. Invert each input, AND every original input with the other input's complement, then OR the two AND results together — the output is 1 exactly when A and B differ.
Assuming a 3-input XOR outputs 1 only when exactly one of the three inputs is 1.
For n > 2 inputs, XOR computes odd parity: it outputs 1 whenever an odd number of inputs are 1 (one 1, or all three 1s in a 3-input case), not only when exactly one input is 1.
The spec's tricky point states XOR means 'inputs are different', 'not simply one input is 1' for more than two inputs. A 3-input case with A=B=C=1 has three (an odd count) 1-inputs and XOR outputs 1, even though it is false that only one input is 1 — the two-input intuition does not extend directly.
[tricky-problem] A 3-input XOR circuit has inputs A=1, B=1, C=1. What is the output, and why? A. 0, because more than one input is 1 B. 1, because an odd number (three) of the inputs are 1 — multi-input XOR computes odd parity, not 'exactly one input is 1' C. Undefined, because XOR only accepts two inputs D. 1, because at least one input is 1, same as OR
B. 1, because an odd number (three) of the inputs are 1 — multi-input XOR computes odd parity, not 'exactly one input is 1' — The spec warns that XOR means 'inputs are different', not simply 'one input is 1', for more than two inputs. With three inputs, XOR generalizes to odd parity: output is 1 when an odd count of inputs are 1. Here all three inputs are 1 (an odd count), so the output is 1, even though it's false that 'only one' input is 1.
[interview] Why is XOR described as not being a fourth foundational Boolean primitive alongside NOT, AND, and OR? A. Because XOR gates are more expensive to manufacture. B. Because XOR can be fully expressed as A'B + AB' using only AND, OR, and NOT — it is a derived function, not an independent primitive. C. Because XOR only works with one input. D. Because XOR gates cannot be implemented in CMOS.
B. Because XOR can be fully expressed as A'B + AB' using only AND, OR, and NOT — it is a derived function, not an independent primitive. — The spec gives XOR's expression as Y = A ⊕ B = A'B + AB', explicitly showing it decomposes into AND, OR, and NOT operations. Since those three gates are already sufficient to build any Boolean function, XOR (and XNOR) are convenience symbols for common derived functions, not additional primitives.
Two 4-bit binary numbers, 1011 and 1001, are compared bit by bit with XOR gates, one gate per bit position. At which bit position(s) does the XOR output read 1, and what does that tell you?
1011 vs 1001, compared bit by bit (MSB to LSB): 1⊕1=0, 0⊕0=0, 1⊕0=1, 1⊕1=0. Only the third bit position (from the left) outputs 1, correctly identifying that this is the only bit where the two numbers differ.
XOR outputs 1 only where the corresponding bits of the two numbers differ.