Exclusive OR

Exclusive OR, commonly abbreviated XOR, is a binary operation in logic that returns true when its two inputs have different truth values and false when they have the same truth value. With false represented by 0 and true by 1, XOR produces 1 precisely when one input—but not both—is 1. It differs from inclusive OR, which also returns true when both inputs are true. XOR connects logical reasoning with binary computation and algebra. (xlinux.nist.gov)

Logical definition

In propositional logic, XOR is usually written $p\oplus q$. Its truth table is:

Thus, XOR is a “not equal” operation on Boolean values. (xlinux.nist.gov)

Using the standard operations of Boolean algebra, its definition can be expressed as

Equivalently, it is $(p\land\neg q)\lor(\neg p\land q)$: either the first proposition alone is true or the second alone is true. These formulas follow directly by checking the four truth-table rows. XOR’s negation, commonly called XNOR, is true when the inputs agree. (xlinux.nist.gov)

The distinction between exclusive and inclusive OR concerns whether simultaneous truth is allowed. For example, an exclusive choice between two options permits either option individually but rules out choosing both. The operation itself specifies truth conditions; it does not impose any temporal order or causal relationship between its inputs. (xlinux.nist.gov)

Algebraic structure

XOR has four fundamental properties:

It is therefore commutative and associative, has 0 as its identity, and makes every element its own inverse. In the terminology of group theory, the two Boolean values form an abelian group under XOR. These properties also hold for equal-length bit strings under componentwise XOR. (web.stanford.edu)

Cancellation consequently gives

This explains why applying the same XOR transformation twice restores the original value. XOR with 1 complements a single bit, whereas XOR with 0 leaves it unchanged. (web.stanford.edu)

For bits $a,b$, XOR is addition in modular arithmetic:

Together with AND as multiplication, it supplies the arithmetic operations of the two-element finite field, $\mathbb F_2$. Bit strings of length $n$ can accordingly be treated as elements of the vector space $\mathbb F_2^n$, with XOR as vector addition. This algebraic interpretation underlies binary coding and network-coding computations. (doi.org)

Associativity permits repeated XOR without specifying parentheses. The result is 1 exactly when an odd number of inputs are 1: each pair of 1s cancels. Importantly, this does not mean “exactly one input is true” for three or more inputs. For example, $1\oplus1\oplus1=1$. This odd-parity behavior is a consequence of the binary operation’s identities. (web.stanford.edu)

Connection with sets

In set theory, XOR corresponds to symmetric difference:

An element belongs to $A\triangle B$ exactly when it belongs to one of the sets but not both. The operation excludes their overlap, unlike ordinary union. Membership in the symmetric difference is therefore the XOR of the two membership values. (doi.org)

Symmetric difference inherits XOR’s associativity and commutativity. Its identity is the empty set, and $A\triangle A=\varnothing$. These identities allow calculations with sets to mirror calculations with Boolean values. (doi.org)

Bitwise computation and digital circuits

Bitwise XOR applies the operation independently to corresponding bits of two binary numbers. It does not propagate carries between positions. For example, direct componentwise calculation gives

The output marks positions where the inputs differ. In the programming language Python, the operator ^ performs bitwise XOR on integers; it is not an exponentiation symbol. (web.stanford.edu)

An XOR logic gate implements the same truth table electronically. In a half adder, XOR computes the sum bit $s=a\oplus b$, while AND computes the carry $c=a\land b$. Thus $1+1$ produces sum 0 and carry 1, representing the binary result $10_2$. A full adder includes an incoming carry, with sum $a\oplus b\oplus c_{\mathrm{in}}$. (www-inst.eecs.berkeley.edu)

Repeated XOR also provides parity information used in error-correcting codes. From its odd-parity rule, a parity check detects any odd number of bit flips, but an even number can leave the parity unchanged. Parity alone therefore does not identify every possible error. (web.stanford.edu)

Cryptographic use

In cryptography, XOR can combine a plaintext bit string $M$ with a key string $K$:

Recovery follows from cancellation. A binary one-time pad uses this construction with a secret, uniformly random key independent of the message, as long as the message, and never reused. Under these conditions it achieves perfect secrecy; XOR alone does not supply those conditions. (nvlpubs.nist.gov)

If the same key encrypts two messages, cancellation gives $C_1\oplus C_2=M_1\oplus M_2$. This derived identity shows that key reuse exposes a relationship between the plaintexts rather than preserving the one-time pad’s secrecy guarantee. (nvlpubs.nist.gov)

The XOR problem in machine learning

XOR is a standard example in machine learning of a classification problem lacking linear separability. The positive points $(0,1)$ and $(1,0)$ occupy opposite corners of a square, while $(0,0)$ and $(1,1)$ are negative. No straight line separates the two classes, so a single linear-threshold perceptron cannot represent XOR. (cs.cmu.edu)

A multilayer perceptron can represent it using a hidden layer with nonlinear activation functions. One construction has hidden units detect OR and AND, then combines their outputs to exclude the case where both inputs are active. This illustrates how intermediate representations allow a neural network to express a decision rule unavailable to a single linear-threshold unit. (cs.cmu.edu)