Exclusive or or exclusive disjunction or exclusive alternation, also known as non-equivalence which is the negation of equivalence, is a logical operation that is true if and only if its arguments differ (one is true, the other is false).
It is symbolized by the prefix operator and by the infix operators XOR (, , or ), EOR, EXOR, , , , ⩛, , and .
It gains the name "exclusive or" because the meaning of "or" is ambiguous when both operands are true; the exclusive or operator excludes that case. This is sometimes thought of as "one or the other but not both" or "either one or the other". This could be written as "A or B, but not, A and B".
XOR is equivalent to logical inequality (NEQ) since it is true only when the inputs are different (one is true, and one is false). The negation of XOR is the logical biconditional, which yields true if and only if the two inputs are the same, which is equivalent to logical equality (EQ).
Since it is associative, it may be considered to be an n-ary operator which is true if and only if an odd number of arguments are true. That is, a XOR b XOR ... may be treated as XOR(a,b,...).
Definition
The truth table of shows that it outputs true whenever the inputs differ:
Equivalences, elimination, and introduction
Exclusive disjunction essentially means 'either one, but not both nor none'. In other words, the statement is true if and only if one is true and the other is false. For example, if two horses are racing, then one of the two will win the race, but not both of them. The exclusive disjunction , also denoted by or , can be expressed in terms of the logical conjunction ("logical and", ), the disjunction ("logical or", ), and the negation () as follows:
The exclusive disjunction can also be expressed in the following way:
This representation of XOR may be found useful when constructing a circuit or network, because it has only one operation and small number of and operations. A proof of this identity is given below:
It is sometimes useful to write in the following way:
or:
This equivalence can be established by applying De Morgan's laws twice to the fourth line of the above proof.
The exclusive or is also equivalent to the negation of a logical biconditional, by the rules of material implication (a material conditional is equivalent to the disjunction of the negation of its antecedent and its consequence) and material equivalence.
In summary, we have, in mathematical and in engineering notation:
Negation of the operator
The spirit of De Morgan's laws can be applied, we have:
Relation to modern algebra
Although the operators (conjunction) and (disjunction) are very useful in logic systems, they fail a more generalizable structure in the following way:
The systems and are monoids, but neither is a group. This unfortunately prevents the combination of these two systems into larger structures, such as a mathematical ring.
However, the system using exclusive or is an abelian group. The combination of operators and over elements produce the well-known two-element field . This field can represent any logic obtainable with the system and has the added benefit of the arsenal of algebraic analysis tools for fields.
More specifically, if one associates with 0 and with 1, one can interpret the logical "AND" operation as multiplication on and the "XOR" operation as addition on :
The description of a Boolean function as a polynomial in , using this basis, is called the function's algebraic normal form.
Exclusive or in natural language
Disjunction is often understood exclusively in natural languages. In English, the disjunctive word "or" is often understood exclusively, particularly when used with the particle "either". The English example below would normally be understood in conversation as implying that Mary is not both a singer and a poet.
1. Mary is a singer or a poet.
However, disjunction can also be understood inclusively, even in combination with "either". For instance, the first example below shows that "either" can be felicitously used in combination with an outright statement that both disjuncts are true. The second example shows that the exclusive inference vanishes away under downward entailing contexts. If disjunction were understood as exclusive in this example, it would leave open the possibility that some people ate both rice and beans.
2. Mary is either a singer or a poet or both. 3. Nobody ate either rice or beans.