| Exclusive Or |
Article Index for Exclusive |
Website Links For Exclusive |
Information AboutExclusive Or |
| CATEGORIES ABOUT EXCLUSIVE OR | |
| logic | |
| binary operations | |
|
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. ]] 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" -- the subject can only choose one of the operands. In logic, the word 'or' usually means the other, Inclusive, Disjunction . (Some languages, such as Latin , have been alleged to have different words for these different types of "or".) 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 Proposition s ''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. 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'') SYMBOL The mathematical symbol for exclusive disjunction varies in the literature. In addition to the abbreviation "xor", one may see
Similarly, different textual notations are used, including "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) It is sometimes useful to write XOR as: A ⊻ B = !( (A ∧ B) ∨ (!A ∧ !B) ) This result is simply De Morgan's Theorem applied (twice) to the fourth line of the above proof. ASSOCIATIVITY AND COMMUTATIVITY For successive xor operations, xor can be applied to the first two inputs and then the result can be xor'ed with each subsequent input, or in any other order: :(''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: :(''A'' xor (''B'' xor ''C'') ) = ( (''A'' xor ''B'') xor ''C'') The operator xor is also Commutative and therefore the order of the operands is not important: A LIST OF SOME PROPERTIES This section uses the symbols: A ⊕ B = A ⊻ B = A xor B
A + B = A ∨ B = A or B A ⊕ !A = 1 A ⊕ A = 0 A ⊕ 1 = !A A ⊕ 0 = A A ⊕ B = B ⊕ A A ⊕ B ⊕ A = B A ⊕ (B ⊕ C) = (A ⊕ B) ⊕ C A ⊕ B = !A ⊕ !B !(A ⊕ B) = (!A) ⊕ B = A ⊕ (!B)
(!A) ⊕ (A + !B) = A + B
A + (A ⊕ B) = A + B BITWISE OPERATION Exclusive disjunction is often used for bitwise operations. Examples:
IN COMPUTER SCIENCE In computer science, exclusive disjunction is commonly referred to as "''exclusive-or''" or "''xor''". It has several uses:
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.XOR is also used to detect an overflow in the result of a signed binary arithmetic operation. If the leftmost retained bit of the result is not the same as the infinite number of digits to the left, then that means overflow occurred. XORing those two bits will give a "one" if there is an overflow. MORE THAN TWO INPUTS The case of a three, or more, input XOR operation tends to be an ill-considered case. An XOR operation with three ''simultaneous'' inputs is not so easily expressed in most popular programming languages. When expressed as successive Binary Operation s the result is a simple Parity , giving a TRUE result for any odd number of TRUE inputs. When taken as a multi-input black box whose operation follows the formal definition and yields the result TRUE when one, and only one, of its inputs is TRUE, the behaviour is inconsistent with the successive binary mode. For example; in the case where three inputs are all TRUE (as shown on the right, in the IEC symbology to emphasise the definition) the result would have to be FALSE because it does not meet the condition that "only one of its inputs is TRUE". SEE ALSO ;Applications ;In logic
;In mathematics ;Other gates |
|
|