Exclusive Or

Pronunciation: /ɪkˈsklusɪv ɔr/ ?

Exclusive or is a logical operation that returns true only if one operand is true and the other is false. For propositions a and b, exclusive or is true if either a or b are true, but not both. Table 1 is the truth table for exclusive or. Exclusive or can also be called an exclusive disjunction. When writing, the term 'exclusive or' is sometimes abbreviated as 'xor'; which is pronounced 'ex-or'.

Three ways in which exclusive or can be written are: a XOR b, a?b, or a?b. In many programming languages, exclusive or is denoted with the caret symbol (^). In electronics, an exclusive or gate is drawn as:
Exclusive or gate from electronics..

Venn diagram with only the parts of a and b that are not in common colored in.
Figure 1: Venn diagram of A xor B.

Properties of Exclusive Or

Property
Using Words
Property
Using Symbols
Description
a xor false = aa⊕false = a
a xor true = not aa⊕true = ¬a
a xor a = falsea⊕a = falseThe definition of exclusive or implies that if both operands are true, or both operands are false, then exclusive or returns false. a≠a, a xor a must always be false.
a xor not a = truea⊕¬a = trueThe definition of exclusive or states that if the two operands are not equal, exclusive or returns true. Since a?not a, a xor not a is always true.
a xor b = b xor aa⊕b = b⊕aExclusive or is commutative.
a xor (b xor c) = (a xor b) xor ca⊕(b⊕c) = (a⊕b)⊕cExclusive or is associative.
a xor b = not a xor not ba⊕b = ¬a⊕¬bIf the truth value of both operands are swapped, exclusive or still returns the same value.
not (a xor b) = not a xor b = a xor not b¬(a⊕b) = ¬a⊕b = a⊕¬bThe logical negation of exclusive or result is the same thing as negating one of the operands of the exclusive or.
a xor b = (a and not b) or (not a and b)a⊕b = (a∧¬b)∨(¬a∧b)This is a restatement of the definition of exclusive or: an exclusive or operation is true only if one of the arguments is true and the other is false.
a xor b = (a or b) and (not a or not b)a⊕b = (a∨b)∧(¬a∨¬b)This is again a restatement of the definition of exclusive or. The first term (a or b) is true if either a or b is true. The second term (not a or not b) is true if either a and b is false. With the conjunction, the entire expression is true if either a or b is true.
a xor b = (a or b) and not (a and b)a⊕b = (a∨b)∧¬(a∧b)This is another restatement of the definition of exclusive or.
Table 2: Properties of Exclusive Or.

Bitwise Exclusive Or

In logic, the operands of exclusive or must be a truth value, must be either true of false. In computers, the operands of exclusive or are binary numbers. The exclusive or is applied to corresponding bits of the operands:
0 xor 0 = 0; 0 xor 1 = 1; 1 xor 0 = 1; 1 xor 1 = 0; 1001 xor 1100 = 0110

References

  1. xor. merriam-webster.com. Encyclopedia Britannica. (Accessed: 2009-03-12). http://www.merriam-webster.com/dictionary/XOR?db=luna.
  2. Boole, George; von Kuffner, Moriz. The mathematical analysis of logic : being an essay towards a calculus of deductive reasoning, pp 52-59. Macmillan, Barclay, & Macmillan, 1847. (Accessed: 2010-02-01). http://www.archive.org/stream/mathematicalanal00booluoft#page/52/mode/1up/search/exclusive.

Printed Resources

Cite this article as:


Exclusive Or. 2010-02-02. All Math Words Encyclopedia. Life is a Story Problem LLC. http://www.allmathwords.org/en/e/exclusiveor.html.

Translations

Image Credits

Revision History


2010-02-01: Added "References" (McAdams, David.)
2009-04-18: Corrected discussion of a xor a. (McAdams, David.)
2009-01-08: Initial version (McAdams, David.)

All Math Words Encyclopedia is a service of Life is a Story Problem LLC.
Copyright © 2005-2011 Life is a Story Problem LLC. All rights reserved.
Creative Commons License This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 License