In logic, exclusive disjunction is a logical operator.
The exclusive disjunction of propositions A and B is usually called A xor B, where "xor" stands for "exclusive or" and is pronounced "ex-or".
The operation yields the result TRUE when one, and only one, of its operands is TRUE.
For two inputs A and B, the truth table of the function is as follows.
A B | A xor B
F F | F
F T | T
T F | T
T T | F
It can be deduced from this table that
- (A xor B) = (A and not B) or (not A and B) = (A or B) and (not A or not B) = (A or B) and not (A and B)
The mathematical symbol for exclusive disjunction varies in the literature.
In addition to the abbreviation "xor", one may see
- a plus sign ("+") or a plus sign that is modified in some way, such as being put inside a circle ("⊕"); this is used because exclusive disjunction corresponds to addition modulo 2 if F = 0 and T = 1.
- a vee that is modified in some way, such as being underlined ("∨"); this is used because exclusive disjunction is a modification of ordinary (inclusive) disjunction, which is typically denoted by a vee.
- a caret ("^"), as in the C programming language
Similarly, different textual notations are used, including "EOR" (with the same expansion as "xor") and "orr" (modelled on iff
, of which it is the negative).
Binary values xor'ed by themselves are always zero.
In some computer architectures, it is faster to store a zero in a
register by xor'ing the value with itself instead of loading and storing
the value zero. Thus, on some computer architectures, xor'ing values
with themselves is a common optimization.
The xor operation is sometimes used as a simple mixing function in cryptography, for example, with one-time pad or Feistel network systems.
: Symmetric difference
, Xor swap algorithm
, Xor linked list