Exclusive or
From Freepedia
- XOR redirects here. For the computer game, see XOR (computer game).
Contents |
Definition
In English and other languages, the treatment of the word or requires a little care. The exclusive disjunction of propositions A and B means A or B, but not both, as in "you can follow the rules or be disqualified". In logic, the word 'or' usually means the other, inclusive, disjunction.
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 |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
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
- the symbol Image:Xor.png.
- a plus sign ("+") or a plus sign that is modified in some way, such as being put inside a circle ("<math>\oplus</math>"); this is used because exclusive disjunction corresponds to addition modulo 2 (where 0+0 = 1+1 = 0 , and 0+1 = 1+0 = 1). The HTML entity for the circled plus character is "⊕".
- 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 or Java 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).
Definition using symbols
Using the symbols above one can write the XOR as:
A ∨ B = (A ∧ !B) ∨ (!A ∧ B) (this is the definition)
After some calculation, one can also derive that XOR can be written as:
A ∨ B = !(A ∧ B) ∧ (A ∨ B)
This representation of XOR is very powerful, because it has only one ! operation and small number of ∧ and ∨ operations. When constructing a circuit or network that works as a XOR, you will find this expression handy. The proof of this expression is given below:
Proof:
A ∨ B = (A ∧ !B) ∨ (!A ∧ B)
= {(A ∧ !B) ∨ !A} ∧ {(A ∧ !B) ∨ B}
= {(A ∨ !A) ∧ (!B ∨ !A)} ∧ {(A ∨ B) ∧ (!B ∨ B)}
= {!A ∨ !B} ∧ {A ∨ B}
= !(A ∧ B) ∧ (A ∨ B)
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 B ⇔ B 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 (this is equivalent to addition without carry)
In computer science
In computer science, exclusive disjunction is commonly referred to as "exclusive-or" and "xor". It has several uses:
- It tells whether two bits are unequal.
- It is an optional bit-flipper (the deciding input chooses whether or not to invert the data input).
- It tells whether there are an odd number of one bits (A ⊕ B ⊕ C ⊕ D ⊕ E is true iff an odd number of the variables are true).
On some computer architectures, it is more efficient to store a zero in a register by xor-ing the register with itself (bits xor-ed with themselves are always zero) instead of loading and storing the value zero. Because 'xor' is a more complex logical function than 'or' and 'and', its neural network requires an additional processing layer.
Exclusive-or is sometimes used as a simple mixing function in cryptography, for example, with one-time pad or Feistel network systems.
XOR is used in RAID 3-6 for creating parity information. For example, RAID can "back up" bytes 10011100 and 01101100 from two hard drives by XORing (11110000) and writing to a third drive. Under this method, if any one of the three hard drives are lost, the lost byte can be re-created by XORing bytes from the remaining drives. If the drive containing 01101100 is lost, 10011100 and 11110000 can be XORed to recover the lost byte.
See also
- Boolean algebra
- symmetric difference
- logical or
- logical and
- xor swap algorithm
- xor linked list
- parity
- disjunctive syllogism
- affirming a disjunct
