Exclusive or
The exclusive or, commonly abbreviated as XOR, is a binary logical operation in Boolean algebra that outputs true (1) if and only if exactly one of its two inputs is true, and false (0) otherwise.[1] This operation is distinct from the inclusive OR, as it excludes the case where both inputs are true.[2] XOR is symbolized by the ⊕ operator in mathematical notation and is implemented as a fundamental logic gate in digital circuits.[3][4] The truth table for the XOR operation with two inputs, A and B, is as follows: This table illustrates that the output is 1 precisely when the inputs differ.[5] For multiple inputs, XOR generalizes to produce 1 if there is an odd number of 1s among them; the operation is associative and commutative.[6][7] In programming languages like C++, Java, and Python, the bitwise XOR is denoted by the caret (^) and operates on integers bit by bit.[8] XOR plays a critical role in various fields, particularly in computing and communications, with applications including error detection, cryptography, and data processing.[9][10] Its properties, such as self-invertibility (where XORing a value with itself yields 0, as shown in the truth table), support uses in algorithms like hashing and checksums.Fundamentals
Definition
The exclusive or (XOR), also known as exclusive disjunction, is a fundamental binary logical operator in propositional logic and Boolean algebra that evaluates to true if exactly one of its two inputs is true and false otherwise.[11][12] For propositions p and q, the statement p \oplus q holds true precisely when p and q have differing truth values—one is true and the other false—making it distinct from the inclusive or, which allows both inputs to be true.[3][7] This operation captures the notion of "either... or... but not both," emphasizing mutual exclusivity in logical conditions.[11] In its standard two-input form, XOR serves as a core building block in digital circuits and computational logic, where it is often implemented using the symbol \oplus to denote the operation between Boolean variables or bits.[3] The operator is commutative, meaning p \oplus q yields the same result as q \oplus p, though detailed properties are explored elsewhere.[13] XOR generalizes to multiple inputs (n-ary XOR), where the output is true if and only if an odd number of the inputs are true, providing a parity-checking mechanism in applications like error detection.[14][15] However, the binary case remains the primary focus for defining the operation's intuitive and formal behavior.[16]Truth Table
The truth table for the exclusive or (XOR) operation with two inputs, typically denoted as p and q, exhaustively lists all possible input combinations and their corresponding outputs. The output is true (1) if and only if exactly one of the inputs is true, and false (0) otherwise.[5]| p | q | p \oplus q |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Logical Expressions
Equivalences
The exclusive or operation, denoted as p \oplus q or p XOR q, can be expressed in terms of more primitive logical connectives: conjunction (\wedge), disjunction (\vee), and negation (\neg). One primary equivalence is the disjunctive normal form:p \oplus q \equiv (p \wedge \neg q) \vee (\neg p \wedge q).
This form captures the cases where exactly one of p or q is true, by conjoining each proposition with the negation of the other and then taking their disjunction.[5] An alternative equivalence relates XOR to the inclusive or (\vee) by excluding the case where both are true:
p \oplus q \equiv (p \vee q) \wedge \neg (p \wedge q).
This conjunctive normal form emphasizes the union of p and q minus their intersection, providing a compact representation useful in certain proof contexts.[17][18] In logical proofs and circuit design, an elimination rule for XOR involves replacing instances of p \oplus q with its disjunctive form (p \wedge \neg q) \vee (\neg p \wedge q) to simplify formulas or convert to a standard normal form without the XOR connective. Conversely, an introduction rule allows inserting XOR by recognizing the conjunction-disjunction pattern (p \wedge \neg q) \vee (\neg p \wedge q) and substituting p \oplus q, facilitating modular reasoning or equivalence transformations. These rules preserve logical equivalence and are standard in propositional logic derivations.[19] Both equivalences can be verified through truth table comparison, as detailed in the truth table for XOR. Constructing a truth table for the right-hand side of each equivalence yields identical truth values to the XOR column across all four input combinations of p and q, confirming the equivalences hold tautologically.[20]
Negation
The negation of the exclusive or operation, denoted as ¬(p ⊕ q), is logically equivalent to the expression (p ∧ q) ∨ (¬p ∧ ¬q), which holds true when both propositions p and q are either true or false.[21] This form represents the exclusive nor (XNOR) operator and is also identical to the biconditional p ↔ q.[21] The equivalence arises because XOR is true only when p and q differ in truth value, so its negation is true precisely when they share the same truth value.[22] This core identity can be derived by applying De Morgan's laws to the disjunctive normal form of XOR, p ⊕ q ≡ (p ∧ ¬q) ∨ (¬p ∧ q): \begin{align*} ¬(p ⊕ q) &\equiv ¬[(p ∧ ¬q) ∨ (¬p ∧ q)] \\ &\equiv ¬(p ∧ ¬q) ∧ ¬(¬p ∧ q) \\ &\equiv (¬p ∨ q) ∧ (p ∨ ¬q) \\ &\equiv (p ∧ q) ∨ (¬p ∧ ¬q). \end{align*} [22] A symmetry property of XOR negation states that negating one input produces the same result as negating the entire operation: ¬p ⊕ q ≡ p ⊕ ¬q ≡ ¬(p ⊕ q) ≡ p ↔ q.[23] This holds because flipping the truth value of one operand in XOR inverts the overall parity, mirroring the effect of direct negation on the output.[22] De Morgan-like dualities for XOR negation emerge from the above derivation, where the outer negation distributes over the disjunction in XOR's expression, transforming OR into AND and negating the inner components—analogous to standard De Morgan rules but tailored to XOR's structure of differing inputs.[22] This duality highlights XOR's role in parity logic, enabling simplifications in circuit design and proof systems.[23] For example, negating XOR yields the biconditional, which formalizes "p if and only if q" as true only when p and q are equivalent in truth value; this is evident in applications like equivalence checking, where ¬(p ⊕ q) confirms matching states without the exclusion of XOR.[21]Algebraic Aspects
Properties
The exclusive or (XOR) operation, denoted as \oplus, exhibits several fundamental properties within Boolean algebra that distinguish it from other binary operators like AND (\wedge) and OR (\vee). These properties arise from its definition as the operator that yields true if and only if its inputs differ, and they underpin its utility in logical expressions and computations.[7] XOR is commutative, meaning the order of operands does not affect the result: p \oplus q \equiv q \oplus p. This symmetry holds because the truth value depends solely on whether the inputs differ, regardless of sequence.[24] Similarly, XOR is associative, allowing parentheses to be omitted in multi-operand expressions: (p \oplus q) \oplus r \equiv p \oplus (q \oplus r). Associativity ensures consistent evaluation across chained operations, as the overall parity of true inputs determines the outcome.[24] Unlike AND and OR, which are idempotent (p \wedge p \equiv p and p \vee p \equiv p), XOR is non-idempotent: p \oplus p \equiv \bot, where \bot denotes false. This property reflects XOR's role in toggling or canceling identical inputs. The constant false serves as the identity element for XOR: p \oplus \bot \equiv p, preserving the operand unchanged. Furthermore, each Boolean value acts as its own inverse under XOR, reinforcing the self-canceling behavior: p \oplus p \equiv \bot.[7][24] In terms of distributivity, AND distributes over XOR: p \wedge (q \oplus r) \equiv (p \wedge q) \oplus (p \wedge r), enabling factorization in expressions involving these operators. However, XOR does not distribute over OR. This selective distributivity aligns with XOR's interpretation as addition modulo 2 in the field of two elements (GF(2)), where AND corresponds to multiplication.[24][25] When extended to binary representations, XOR operates linearly bit by bit, equivalent to vector addition modulo 2. For multi-bit numbers, each bit position computes independently as a_i \oplus b_i \mod 2, without carry propagation, facilitating efficient parity checks and error detection.[24]Relation to Modern Algebra
In modern algebra, the exclusive or (XOR) operation finds a natural interpretation as the addition in the finite field \mathbb{F}_2 = \mathrm{GF}(2), whose elements are \{0, 1\} with arithmetic modulo 2. Here, addition corresponds to XOR (where $0 \oplus 0 = 0, $0 \oplus 1 = 1, $1 \oplus 0 = 1, $1 \oplus 1 = 0), and multiplication corresponds to the logical AND operation (where $0 \land 0 = 0, $0 \land 1 = 0, $1 \land 0 = 0, $1 \land 1 = 1). This structure equips \mathbb{F}_2 with the properties of a field, including distributivity: (a \oplus b) \land c = (a \land c) \oplus (b \land c). Extending this, the set of all Boolean functions on n variables, under pointwise XOR as addition and pointwise AND as multiplication, forms a Boolean ring, a commutative ring where every element is idempotent (f \land f = f for any function f).[26][27] The collection of all n-bit binary strings, denoted \{0,1\}^n, equipped with bitwise XOR as the binary operation, constitutes an abelian group isomorphic to (\mathbb{Z}/2\mathbb{Z})^n. The identity element is the zero vector (all bits 0, representing false), and the operation is commutative and associative, with every element serving as its own inverse: for any string x, x \oplus x = [0](/page/0). This group structure arises directly from the vector space properties over \mathbb{F}_2, where scalar multiplication by 0 annihilates any vector and multiplication by 1 leaves it unchanged.[28] More broadly, \{0,1\}^n forms an n-dimensional vector space over \mathbb{F}_2, with XOR as vector addition and the field scalars \{0,1\} acting componentwise. A basis for this space consists of the standard basis vectors e_i (with a 1 in the i-th position and 0s elsewhere), and linear independence of a set of vectors \{v_1, \dots, v_k\} holds if no nonempty subset sums (via XOR) to the zero vector; equivalently, the n \times k matrix formed by these vectors as columns has full column rank over \mathbb{F}_2. Any n-bit string can be uniquely expressed as a linear combination of a basis, highlighting XOR's role in encoding linear dependencies among binary data.[28][29] Systems of linear equations involving XOR operations, such as \sum_{j=1}^n a_{ij} x_j = b_i for i=1,\dots,m where coefficients and b_i are in \{0,1\} and summation is XOR, can be solved using Gaussian elimination performed modulo 2. This process row-reduces the augmented coefficient matrix over \mathbb{F}_2 to row echelon form, identifying the solution space (affine subspace if consistent) or detecting inconsistency if a row reduces to [0 \dots 0 \mid 1]. The time complexity is O(\min(m,n)^2 \max(m,n)), making it efficient for sparse systems common in algebraic contexts.[30] An important extension is the representation of Boolean functions via Zhegalkin polynomials, also known as the algebraic normal form (ANF), which express any function f: \{0,1\}^n \to \{0,1\} as a multilinear polynomial over \mathbb{F}_2: f(x_1,\dots,x_n) = \bigoplus_{S \subseteq } c_S \bigwedge_{i \in S} x_i, where \bigoplus denotes XOR (addition in \mathbb{F}_2), \bigwedge denotes AND (multiplication), and coefficients c_S \in \{0,1\} are determined by Möbius inversion on the subset lattice. This XOR-of-ANDs form is unique, canonical, and facilitates analysis of function properties like nonlinearity and algebraic immunity, as the degree equals the highest |S| with c_S = 1.[31]Notation and Language
Alternative Symbols
The primary symbol for exclusive or is the circled plus ⊕ (Unicode U+2295), introduced by mathematician Edward V. Huntington in his 1904 paper on independent postulates for the algebra of logic to denote symmetric difference. This notation was adopted by Claude Shannon in his 1938 master's thesis, A Symbolic Analysis of Relay and Switching Circuits, where it appeared in diagrams representing relay-based exclusive disjunction operations. In LaTeX, it is rendered using the command\oplus.
Other notations include the caret ^, widely used in programming languages for bitwise exclusive or; for example, in C, C++, Java, and Python, a ^ b computes the bitwise XOR of integers a and b. In Polish notation systems, logician Józef Maria Bocheński assigned the symbol J in his 1949 extension of Łukasiewicz's notation to cover all 16 binary connectives, where Jpq denotes the exclusive disjunction of p and q. Some early logical texts used the inequality symbol ≠ to represent exclusive or, emphasizing its function as logical inequality (true when operands differ).[32]
Contextual variations appear in specialized domains: the slashed disjunction ∨̸ (Unicode U+22C0, LaTeX \not\vee or \veebar) denotes exclusive disjunction in certain formal logic contexts to distinguish it from inclusive or. In Boolean algebra interpreted as a ring over GF(2), the addition operator + serves as exclusive or, aligning with modular arithmetic where addition modulo 2 yields the symmetric difference.[33]
The evolution of these symbols traces from early 20th-century algebraic logic, where Huntington's ⊕ formalized Boolean operations, through Shannon's application to electrical engineering in the 1930s, to mid-century digital circuit design, where IEEE standards defined graphical symbols for logic functions including XOR in diagrams, alongside algebraic notations like ⊕ and ⊻ (Unicode U+22BB, LaTeX \veebar) in mathematical texts, and finally to 1970s programming standards like ASCII, which assigned ^ for efficient bitwise operations in languages such as B and C.
Usage in Natural Language
In natural language, the English word "or" frequently conveys an exclusive disjunction, implying that only one of the alternatives can hold true, even though its semantic core is inclusive. For instance, the common query "Would you like tea or coffee?" typically suggests choosing one beverage, not both, as responding with both would often require clarification like "or both?" This exclusive interpretation arises in everyday scenarios where alternatives are mutually limiting, such as selecting "pie or cake" from a limited menu portion.[34][35] This usage introduces ambiguity between inclusive and exclusive meanings, which can lead to misunderstandings, particularly in precise domains like law. In legal drafting, "or" is often treated as inclusive unless specified otherwise, but phrases like "either...or" explicitly signal exclusivity to avoid disputes over joint fulfillment. For example, a contract stating "the buyer shall pay by cash or check" might allow both if inclusive, but "either cash or check" enforces selection of one to prevent ambiguity in obligations. Courts have interpreted "either...or" as denoting exclusive disjunction in English legal contexts, contrasting with more flexible uses in other languages.[36][8][37] Cross-linguistically, interpretations vary: French "ou" tends toward exclusivity in simple disjunctions, as in "thé ou café," where both would violate the implied choice, though complex forms like "ou...ou" can reinforce this. In Spanish, "o" is more context-dependent, functioning as inclusive or exclusive based on pragmatics, similar to English but without a strict default, as seen in phrases like "té o café" that allow both unless specified. These differences highlight how disjunctive particles encode exclusivity through convention rather than universal semantics.[38][39][8] Philosophically, the exclusive flavor of "or" in natural language stems from Gricean implicature, where speakers adhere to the maxim of quantity—providing no more information than needed—leading hearers to infer exclusivity from an inclusive statement. For example, saying "John bought apples or oranges" implicates "but not both" because mentioning both would be more informative if true, unless context cancels the implicature. This pragmatic mechanism explains why inclusive "or" often sounds exclusive without altering literal meaning.[40][41] Common phrases and literary examples further illustrate this: the idiom "you can't have your cake and eat it too" embodies exclusive disjunction by asserting the impossibility of simultaneous possession and consumption, underscoring mutually exclusive options. In literature, such as Lewis Carroll's Through the Looking-Glass, the White Queen's offer of "jam tomorrow and jam yesterday—but never jam today" plays on exclusive alternatives to highlight logical paradoxes in choice. These expressions reinforce how everyday language prioritizes exclusivity for clarity in decision-making.[34]Applications
Computer Science
In computer science, the exclusive or (XOR) operation is fundamental as a bitwise operator that performs a logical exclusive OR on corresponding bits of two binary numbers, producing a 1 in each bit position where the inputs differ and 0 where they are the same.[42] This bitwise XOR is applied independently to each bit pair, making it efficient for integer manipulation in programming languages. For instance, in binary, 5 (101) XOR 3 (011) yields 6 (110), as the first and third bits differ while the second matches.[43] Languages like C, C++, and Python use the caret symbol (^) to denote this operator, allowing direct application to integers for tasks such as bit flipping or masking.[44] One notable application of bitwise XOR is the XOR swap algorithm, which exchanges the values of two variables without requiring temporary storage, leveraging the property that XORing a value with itself yields zero and XORing with zero preserves the value. The steps are:a = a ^ b; b = a ^ b; a = a ^ b;, where the first step stores the XOR of both in a, the second recovers the original a in b, and the third extracts the original b in a.[45] This technique, while historically useful in memory-constrained environments, is now often optimized or avoided by modern compilers in favor of explicit temporary variables for clarity.[46]
The XOR symbol ⊕ is encoded in Unicode as U+2295 (Circled Plus) within the Mathematical Operators block, enabling its use in documentation and code comments across systems supporting Unicode. In programming, the operator ^ is standard in many languages, including JavaScript and Java, where it applies to integers or BigInts bit by bit.[42]
XOR plays a key role in data structures for hashing and error detection. In hashing, it is commonly used to combine multiple hash values, such as folding bits or merging sub-hashes, due to its commutative and associative properties that help distribute values evenly without order dependency.[47] For checksums, XOR computes parity bits in error-detecting codes; an even parity bit is the XOR of all data bits set to make the total XOR zero, detecting single-bit errors in transmission by verifying if the received parity matches.[48]
At the hardware level, XOR is implemented using XOR gates in digital circuits, which output 1 only for an odd number of 1 inputs and are essential in arithmetic logic units (ALUs) for addition, subtraction, and comparison. These gates typically require a low gate count, such as four NAND gates for a two-input XOR, making them cost-effective in VLSI design.[49]