Exclusive Disjuction, XOR Gate

Definition¹

The following Boolean function is referred to as a $\text{XOR}$ gate or exclusive disjunction and is denoted as follows:

$$ \oplus : \left\{ 0, 1 \right\}^{2} \to \left\{ 0, 1 \right\} $$

$$ 0\oplus 0 = 0,\quad 0\oplus 1 = 1,\quad 1\oplus 0 = 1,\quad 1\oplus 1 = 0 $$

Explanation

The $\text{XOR}$ gate returns true when only one of the two truth values is true, i.e., when the number of true values is odd. In other words, it returns $0$ if the two values are the same and $1$ if they are different, making it useful for implementing a function to compare if two values are the same.

The period between 1974 and 1980, marked by the critique that “Perceptrons cannot solve the $\text{XOR}$ problem,” leading to a stagnation in AI development, is referred to as the AI winter.

부울 함수	기호	진리표
$\text{XOR}$		$a$ $b$ $a \oplus b$ $0$ $0$ $0$ $0$ $1$ $1$ $1$ $0$ $1$ $1$ $1$ $0$

Properties

• This can be expressed with $\text{NOT}$ gate, $\text{AND}$ gate, and $\text{OR}$ gate.

  $$ \begin{align*} a \oplus b &= (a \land \lnot b) \lor (\lnot a \land b) \\ &= (a \lor b) \land (\lnot a \lor \lnot b) \\ &= (a \lor b) \land \lnot (a \land b) \end{align*} $$

• $a \oplus 1 = \lnot a$ is valid.

• $a \oplus 0 = a$ is valid.