Encyclopedia > Exclusive disjunction

  Article Content

Exclusive disjunction

In logic, exclusive disjunction is a logical operator. The exclusive disjunction of propositions A and B is called A xor B, where "xor" stands for "exclusive 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 being put inside of 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.

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.


See also: or, and



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Charles V, Holy Roman Emperor

... France (the "Pragmatic Sanction[?]"). In 1556 Charles abdicated his various positions, giving his personal empire to his son, Philip II of Spain, and the Holy Roman ...

 
 
 
This page was created in 36.7 ms