FACTOID # 30: If Alaska were its own country, it would be the 26th largest in total area, slightly larger than Iran.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
RELATED ARTICLES
People who viewed "XOR" also viewed:
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Exclusive disjunction (usual symbol xor) is a logical operator that results in true if one of the operands (not both) is true.

Contents

Definition

In logic, the treatment of the word or requires a little care (for a native English speaker; some other languages have greater precision). Exclusive disjunction is the sense of the word or as in the proverb you can have your cake or eat it (but not both). The exclusive disjunction of propositions A and B means A or B, but not both. In logic, unqualified disjunction is normally understood to mean the inclusive sense.


More formally exclusive disjunction is a logical operator. The operation yields the result TRUE when one, and only one, of its operands is TRUE. The exclusive disjunction of propositions A and B is usually called A xor B, where "xor" stands for "exclusive or" and is pronounced "eks-or" or "zor".


For two inputs A and B, the truth table of the operator 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)

In general, the result of xor depends on the number of TRUE operands, if there are an odd number of TRUE operands, then the result will be TRUE, otherwise it will be FALSE.


Symbols

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).


Associativity and commutativity

For more than two inputs, xor can be applied to the first two inputs, and then the result can be xor'ed with each subsequent input:

(A xor B xor C xor D) ⇔ (((A xor B) xor C) xor D)

Because xor is associative, the order of the inputs does not matter: the same result will be obtained regardless of association.


The operator xor is also commutative and therefore the order of the operands is not important:

A xor BB xor A

Bitwise operation

Exclusive disjunction is often used for bitwise operations. Examples:

  • 1 xor 1 = 0
  • 1 xor 0 = 1
  • 1110 xor 1001 = 0111

Exclusive disjunction in computer science

Binary values xor'ed by themselves are always zero. In some computer architectures, it is faster, or takes less space, 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.


In digital logic design, a two-input xor logic gate is often thought of as a programmable inverter, in that if one input is held at a logic '1', the output will be the inverse of the other input. Otherwise, if one input is held at logic '0', the output will always be the same as the other input.


The xor operation is a more complex logical function than 'or' and 'and'. Neural networks require an extra processing layer to handle the added complexity.


See also


  Results from FactBites:
 
Exclusive or - Wikipedia, the free encyclopedia (786 words)
Exclusive or (usual symbol XOR occasionally EOR), which is sometimes called exclusive disjunction, is a logical operator that results in true if one of the operands, but not both of them, is true.
The exclusive disjunction of propositions A and B is usually called A xor B, where "xor" stands for "exclusive or" and is pronounced "eks-or" or "zor".
(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)
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m