XOR

XOR is a connective in logic known as the "exclusive or," or exclusive disjunction. It yields true if exactly one (but not both) of two conditions is true. The XOR operation does not have a standard symbol, but is sometimes denoted (this work) or (Simpson 1987, pp. 539 and 550-554). is read " aut ," where "aut" is Latin for "or, but not both." The circuit diagram symbol for an XOR gate is illustrated above. In set theory, is typically called the symmetric difference. The XOR function is implemented as Xor[predicate1, predicate2, ...].

The binary XOR operation is identical to nonequivalence . can be implemented using AND and OR gates as

			(1)
			(2)

where denotes AND and denotes OR, and can be implemented using only NOT and NAND gates as

(3)

(Simpson 1987), where denotes NAND.

The binary XOR operator has the following truth table.

T	T	F
T	F	T
F	T	T
F	F	F

For integers , the binomial coefficient is odd iff the bitwise XOR satisfies . This gives a way to construct Pascal's triangle modulo 2.

For multiple arguments, XOR is defined to be true if an odd number of its arguments are true, and false otherwise. This definition is quite common in computer science, where XOR is usually thought of as addition modulo 2. In this context, it arises in polynomial algebra modulo 2, arithmetic circuits with a full adder, and in parity generating or checking. While this means that the multiargument "XOR" can no longer be thought of as "the exclusive OR" operation, this form is rarely used in mathematical logic and so does not cause very much confusion. The XOR operation is associative, so is the same as . Computation of the multiargument XOR requires evaluation of all its arguments to determine the truth value, and hence there is no "lazy" special evaluation form (as there is for AND and OR).

The ternary XOR operator therefore has the following truth table.

T	T	T	T
T	T	F	F
T	F	T	F
T	F	F	T
F	T	T	F
F	T	F	T
F	F	T	T
F	F	F	F

A bitwise version of XOR can also be defined that performs a bitwise XOR on the binary digits of two numbers and and then converts the resulting binary number back to decimal. Bitwise XOR is implemented in the Wolfram Language as BitXor[n1, n2, ...]. The illustration above plots the bitwise XOR of the array of numbers from to 31 (Stewart 2000; Rangel-Mondragon; Wolfram 2002, p. 871).

For a positive integer , the binary strings of length form the vector space over the finite field under componentwise addition modulo 2 (Menezes et al. 1996, pp. 79-81). Bitwise XOR is this vector addition, so it makes the strings into an Abelian group in which the all-zero string is the identity element and every element is its own inverse element. In particular,

			(4)
			(5)
			(6)

Consequently, for a fixed string , the map is a permutation involution. If , then has no fixed points and exchanges the strings in disjoint pairs . This reversibility requires one operand to be fixed or known. The output of a two-input XOR gate alone does not determine both inputs.

For binary strings and of equal length, the Hamming distance satisfies

(7)

where denotes Hamming weight. Applying the same XOR mask to both strings preserves their Hamming distance.

In cryptography, a plaintext and a key of the same length can be combined to give the ciphertext , with decryption . A one-time pad uses a uniformly random key independent of the plaintext and never reuses it. It provides perfect secrecy, meaning that the ciphertext gives no information about the plaintext (Menezes et al. 1996, p. 192). Reversibility alone does not imply secrecy.