Exclusive Disjuction, XOR Gate
양자정보이론 | ||||||||||||||||
[ 펼치기 · 접기 ]
|
Definition1
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}$ |
|
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.
Kim Young-hoon·Heo Jae-seong, Quantum Information Theory (2020), p85 ↩︎