The XOR (exclusive OR) function is a fundamental logical operation that outputs true only when exactly one of its two inputs is true. In Boolean algebra, it is typically denoted by the symbol ⊕ or the expression A ⊕ B. Unlike the standard OR, which returns true when at least one input is true, XOR distinguishes cases where both inputs are true (returning false). This property makes XOR essential in digital electronics, cryptography, and error detection, as it enables parity checking, binary addition without carry, and reversible operations.
1 Definition and truth table
1.1 Boolean expression
The XOR operation on two Boolean variables A and B can be expressed as: A ⊕ B = (A ∨ B) ∧ ¬(A ∧ B) where ∨ denotes logical OR, ∧ denotes AND, and ¬ denotes NOT. This expression captures the idea that the result is true if at least one input is true, but not both.
1.1.1 Equivalent forms (AND, OR, NOT combos)
XOR can also be written in several equivalent forms using only AND, OR, and NOT:
- A ⊕ B = (A ∧ ¬B) ∨ (¬A ∧ B)
- A ⊕ B = ¬(A ∧ B) ∧ (A ∨ B)
- A ⊕ B = (A ∨ B) ∧ (¬A ∨ ¬B)
The first form is the most direct: it expresses XOR as “A true and B false, or A false and B true.” All these forms produce the same truth table.
1.2 Truth table for two inputs
For two inputs A and B, the XOR function has the following truth table:
| A | B | A ⊕ B | |
|---|---|---|---|
| 0 | 0 | 0 | |
| 0 | 1 | 1 | |
| 1 | 0 | 1 | |
| 1 | 1 | 0 |
The output is 1 only when the inputs differ.
1.3 Truth table for multiple inputs
For three or more inputs, the XOR operation is defined as the XOR of the first two inputs, then XORed with the next, and so on, because XOR is associative and commutative. For n inputs, the result is 1 if and only if the number of true inputs is odd. For example, with three inputs A, B, C:
| A | B | C | A ⊕ B ⊕ C | |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | |
| 0 | 0 | 1 | 1 | |
| 0 | 1 | 0 | 1 | |
| 0 | 1 | 1 | 0 | |
| 1 | 0 | 0 | 1 | |
| 1 | 0 | 1 | 0 | |
| 1 | 1 | 0 | 0 | |
| 1 | 1 | 1 | 1 |
This property is the basis of parity generation.
2 Properties of XOR
2.1 Commutativity and associativity
XOR is commutative: A ⊕ B = B ⊕ A for all A, B. It is also associative: (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C). These properties allow XOR to be applied in any order to a list of values, which is useful in hardware and algorithm design.
2.2 Identity and inverse elements
The identity element for XOR is 0 (false): A ⊕ 0 = A for any A. The inverse of any element A under XOR is A itself, because A ⊕ A = 0. In other words, every element is its own inverse.
2.3 Self-inverse property (A ⊕ A = 0)
XORing a value with itself always yields 0. This self-inverse property means that applying XOR twice with the same value restores the original: (A ⊕ B) ⊕ B = A. This reversibility is crucial in cryptography and graphics.
2.4 Relationship with modulo‑2 addition
XOR is equivalent to addition modulo 2. In arithmetic modulo 2, the only possible values are 0 and 1, and addition mod 2 returns 0 for 1+1 (since 2 ≡ 0 mod 2). Thus, A ⊕ B = (A + B) mod 2. This correspondence links Boolean XOR to algebraic structures over the field GF(2).
3 Applications in logic and computing
3.1 Digital logic circuits
3.1.1 XOR gate implementation
In digital electronics, an XOR gate is a logic gate that implements the XOR function. It can be constructed from basic AND, OR, and NOT gates, or directly as a single integrated circuit (e.g., the 74LS86 quad XOR gate). The XOR gate symbol is a variation of the OR gate with an additional curved line on the input side. Its output behavior makes it a fundamental building block for arithmetic and data processing circuits.
3.1.2 Half‑adder and full‑adder
A half‑adder adds two single‑bit binary numbers and produces a sum (S) and a carry (C). The sum bit is given by A ⊕ B, and the carry by A ∧ B. A full‑adder extends this to three bits (including a carry‑in) by XORing A, B, and the carry‑in to produce the sum, while the carry‑out is generated using a combination of AND and OR gates. XOR thus lies at the heart of binary addition in digital computers.
3.2 Parity generation and error detection
3.2.1 Simple parity bit
Parity is a simple error‑detection method. A parity bit is appended to a data word such that the total number of 1s (including the parity bit) is even (even parity) or odd (odd parity). To generate an even parity bit, one computes the XOR of all data bits; the result is the required parity bit. At the receiver, XORing the data bits and the received parity bit yields 0 if no single‑bit error occurred (in even parity).
3.2.2 Longitudinal redundancy check
For multi‑byte messages, a longitudinal redundancy check (LRC) computes the XOR of all bytes (or words) in the message. The resulting LRC byte, appended to the message, allows detection of errors in corresponding bit positions across the entire block. This technique is often used in serial communication protocols.
3.3 Cryptography
3.3.1 One‑time pad (XOR with key)
The one‑time pad is a provably secure encryption method. The plaintext is XORed with a random key of equal length to produce ciphertext. Because XOR is its own inverse, decryption is performed by XORing the ciphertext with the same key. The security relies on the key being truly random, used only once, and kept secret.
3.3.2 Stream ciphers
Stream ciphers generate a pseudorandom keystream (often using a feedback shift register or other algorithm) and XOR it with the plaintext to produce ciphertext. Examples include RC4 and the A5/1 algorithm used in GSM telephony. The XOR operation provides fast, bit‑wise encryption suitable for real‑time communications.
3.4 Computer graphics and bitwise operations
3.4.1 XOR drawing mode (rubber‑banding)
In computer graphics, an XOR drawing mode toggles pixels between their current color and a drawing color. When a shape is drawn in XOR mode, drawing it a second time restores the original image. This technique is commonly used for rubber‑band lines, selection rectangles, and cursors, because it avoids the need to save and redraw the background.
3.4.2 Image blending
XOR can be used for simple image blending or masking. For instance, XORing two identical images produces a black (zero) result; XORing part of an image with a mask can highlight differences. This operation is often used in computer vision and image processing for edge detection or comparison.
4 XOR in mathematics and set theory
4.1 Symmetric difference of sets
In set theory, the symmetric difference of two sets A and B, denoted A Δ B, is the set of elements that belong to exactly one of the sets. When sets are represented by characteristic functions (1 if element present, 0 otherwise), the symmetric difference corresponds exactly to the XOR of those functions: χ<sub>A Δ B</sub> = χ<sub>A</sub> ⊕ χ<sub>B</sub> (where χ denotes the characteristic function).
4.2 XOR as addition in GF(2)
The field GF(2) (Galois field of two elements) consists of the set {0,1} with addition defined as XOR and multiplication as AND. Under these operations, GF(2) satisfies all field axioms. The XOR operation is therefore the additive operation of the smallest finite field.
4.3 Linear algebra over GF(2)
When vectors are defined over GF(2), addition of vectors is performed component‑wise using XOR. This is the basis of many coding theory constructions (e.g., Hamming codes) and linear feedback shift registers. The XOR operation preserves linearity, enabling the use of matrix algebra for error correction and cryptography.
5 Related concepts and variants
5.1 XNOR (equivalence gate)
XNOR, also called equivalence, is the logical complement of XOR. It outputs true when both inputs are equal. Its Boolean expression is ¬(A ⊕ B) or equivalently A ⊙ B, often read as “A if and only if B.” In digital logic, XNOR is used for equality checkers.
5.2 N‑input XOR and parity trees
An n‑input XOR can be built by cascading two‑input XOR gates in a tree structure. Such a tree computes the parity (odd/even) of the inputs and is known as a parity tree. Hardware implementations of parity trees are used in memory error detection (e.g., SECDED ECC) and in hashing circuits.
5.3 XOR in neural networks
5.3.1 The XOR problem (non‑linear separability)
The XOR function is famously impossible to represent with a single‑layer perceptron (a linear classifier) because the four input patterns (0,0), (0,1), (1,0), (1,1) are not linearly separable. This limitation, pointed out by Minsky and Papert in 1969, led to a temporary decline in neural network research.
5.3.2 Solving XOR with a hidden layer
A multilayer perceptron with at least one hidden layer, using a non‑linear activation function (e.g., sigmoid or ReLU), can solve the XOR problem. Standard network architecture for XOR has two inputs, two hidden neurons, and one output neuron. The hidden layer effectively transforms the input space so that the output layer can separate the classes linearly. Solving XOR remains a classic pedagogical example for backpropagation.
6 Historical and pedagogical aspects
6.1 Origin in Boolean algebra (George Boole)
The logical foundations of XOR can be traced to George Boole’s 1847 work *The Mathematical Analysis of Logic* and his 1854 *An Investigation of the Laws of Thought*. Boole introduced a system of binary algebra where the operation of “exclusive” disjunction was recognized as distinct from inclusive disjunction. He symbolised it with the “+” operator, later refined by others.
6.2 Introduction in early computing (Claude Shannon)
Claude Shannon, in his 1937 master’s thesis *A Symbolic Analysis of Relay and Switching Circuits*, showed how Boolean algebra could represent the operation of electromechanical relays. He explicitly discussed the XOR function (then often called “non‑equivalence”) and demonstrated its use in binary adders. This work laid the foundation for modern digital logic design.
6.3 Common classroom examples and puzzles
XOR appears in many educational contexts: solving puzzles like “the three‑light switch problem” or “the two‑door riddle,” explaining error detection in parity bits, and introducing the concept of one‑time pads in cryptography. The XOR of two identical images cancelling out is a popular demonstration of the self‑inverse property. In programming courses, XOR swap (swapping two variables without a temporary) is a classic trick, though now mainly of historical interest.