Definition:Exclusive Or

From ProofWiki
Jump to: navigation, search

Definition

Exclusive Or is a binary connective which can be written symbolically as $p \oplus q$ whose behaviour is as follows:

$p \oplus q$

means:

Either $p$ is true or $q$ is true but not both.


or symbolically:

$p \oplus q := \left({p \lor q} \right) \land \neg \left({p \land q}\right)$

where $\land$ denotes the and operator and $\lor$ denotes the or operator.


There is no standard symbol for this, but the one shown above is seen commonly enough to be adopted as standard for this site.


Truth Function

The exclusive or connective defines the truth function $f^\oplus$ as follows:

\(\displaystyle f^\oplus \left({F, F}\right)\) \(=\) \(\displaystyle F\) $\quad$ $\quad$
\(\displaystyle f^\oplus \left({F, T}\right)\) \(=\) \(\displaystyle T\) $\quad$ $\quad$
\(\displaystyle f^\oplus \left({T, F}\right)\) \(=\) \(\displaystyle T\) $\quad$ $\quad$
\(\displaystyle f^\oplus \left({T, T}\right)\) \(=\) \(\displaystyle F\) $\quad$ $\quad$


Truth Table

The characteristic truth table of the exclusive or operator $p \oplus q$ is as follows:

$\begin{array}{|cc||c|} \hline p & q & p \oplus q \\ \hline F & F & F \\ F & T & T \\ T & F & T \\ T & T & F \\ \hline \end{array}$


Boolean Interpretation

The truth value of $\mathbf A \oplus \mathbf B$ under a boolean interpretation $v$ is given by:

$v \left({\mathbf A \oplus \mathbf B}\right) = \begin{cases} F & : v \left({\mathbf A}\right) = v \left({\mathbf B}\right) \\ T & : \text{otherwise} \end{cases}$


Notational Variants

Various symbols are encountered that denote the concept of exclusive or:

Symbol Origin Known as
$p \oplus q$ sometimes called o-plus
$p\ \mathsf{XOR} \ q$
$p + q$
$p \not \Leftrightarrow q$
$p \not \equiv q$
$p \ne q$
$p \ \dot \lor \ q$
$p \ \_ \lor \ q$


Also known as

This usage of or, that disallows the case where both disjuncts are true, is also called:

  • exclusive disjunction
  • logical inequality
  • non-equivalence
  • symmetric difference
  • the alternative function
  • aut (from the Latin), pronounced out.

Some sources refer to this as the strong or, where the weak or is used in the sense of the inclusive or.

In natural language, when it is necessary to be precise about the nature of the term being used, the phrase but not both is often employed.


Also see

  • Results about exclusive or can be found here.


Sources