배타적 논리합, XOR 게이트
양자정보이론 | ||||||||||||||||
[ 펼치기 · 접기 ]
|
정의1
다음과 같은 부울함수를 $\text{XOR}$ 게이트XOR gate 혹은 배타적 논리합exclusive disjuction/or이라 하고 다음과 같이 표기한다.
$$ \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 $$
설명
$\text{XOR}$ 게이트는 두 진리값 중 하나만 참일 때, 즉 참이 홀수일 때 참을 반환한다. 다시말하면 두 값이 같으면 $0$, 다르면 $1$을 반환하므로 두 값이 같은지를 비교하는 기능을 구현할 때 유용하다.
"퍼셉트론은 $\text{XOR}$ 문제를 풀 수 없다"는 지적 때문에 AI의 발전이 침체된 시기인 1974년부터 1980년까지를 AI 겨울AI winter이라고 말한다.
부울 함수 | 기호 | 진리표 | |||||||||||||||
$\text{XOR}$ |
|
성질
$\text{NOT}$ 게이트, $\text{AND}$ 게이트, $\text{OR}$ 게이트로 표현 가능하다.
$$ \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$가 성립한다.
$a \oplus 0 = a$가 성립한다.
같이보기
- $\text{AND}$ 게이트논리곱
- $\text{OR}$ 게이트논리합
- $\text{NOT}$ 게이트논리 부정
- $\text{NAND}$ 게이트부정논리곱
- $\text{NOR}$ 게이트부정논리합
- $\operatorname{CNOT}$ 게이트
- 토폴리 게이트$\text{CCNOT}$ 게이트
- 프레드킨 게이트$\text{CSWAP}$ 게이트
김영훈·허재성, 양자 정보 이론 (2020), p85 ↩︎