부정논리곱, NAND 게이트
양자정보이론 | ||||||||||||||||
[ 펼치기 · 접기 ]
|
정의1
다음과 같은 부울함수를 $\text{NAND}$ 게이트NAND gate 혹은 부정논리곱이라 하고 다음과 같이 표기한다.
$$ \uparrow : \left\{ 0, 1 \right\}^{2} \to \left\{ 0, 1 \right\} $$
$$ 0\uparrow 0 = 1,\quad 0\uparrow 1 = 1,\quad 1\uparrow 0 = 1,\quad 1\uparrow 1 = 0 $$
설명
$\text{NOT}$ 게이트와 $\text{AND}$ 게이트의 합성이고, $\text{N(OT)}$과 $\text{AND}$를 따와서 $\text{NAND}$라고 명명하였다.
$$ \begin{equation} \uparrow = \lnot \circ \land \end{equation} $$
$$ a \uparrow b = \lnot (a \land b) $$
$\text{AND}$ 게이트와 반대로 작동하며, 모든 입력이 참일 때만 거짓을 출력한다. 또한 $\left\{ \uparrow \right\}$는 함수적으로 완전한데, $(1)$에 의해서 당연하다고 볼 수 있다.
부울 함수 | 기호 | 진리표 | |||||||||||||||
$\text{NAND}$ |
|
정리
(복제함수를 허용하면) $\left\{ \uparrow \right\}$는 함수적으로 완전하다. 다시말해 $\uparrow$는 범용 게이트이다.
증명
$\text{NOT}$와 $\text{AND}$ 게이트의 집합 $\left\{ \lnot, \land \right\}$은 함수적으로 완전하다.
위의 정리에 따라, 복제함수 $\text{cl}$과 $\uparrow$만으로 $\text{NOT}$ 게이트와 $\text{AND}$ 게이트를 만들 수 있음을 보이면 된다.
$\text{NOT}$ 게이트
$$ \lnot = \uparrow \circ \operatorname{cl} \\ \lnot a = a \uparrow a $$
가 성립한다.
$$ \begin{align*} \uparrow \circ \operatorname{cl}(0) = 0 \uparrow 0 = 1 = \lnot 0 \\ \uparrow \circ \operatorname{cl}(1) = 1 \uparrow 1 = 0 = \lnot 1 \\ \end{align*} $$
$\text{AND}$ 게이트
$$ \land = \uparrow \circ \operatorname{cl} \circ \uparrow \\ a \land b = (a \uparrow b) \uparrow (a \uparrow b) $$
가 성립한다.
$$ \begin{align*} (0 \uparrow 0) \uparrow (0 \uparrow 0) = (1 \uparrow 1) = 0 = 0 \land 0 \\ (0 \uparrow 1) \uparrow (0 \uparrow 1) = (0 \uparrow 0) = 0 = 0 \land 1 \\ (1 \uparrow 0) \uparrow (1 \uparrow 0) = (0 \uparrow 0) = 0 = 1 \land 0 \\ (1 \uparrow 1) \uparrow (1 \uparrow 1) = (1 \uparrow 1) = 1 = 1 \land 1 \\ \end{align*} $$
■
같이보기
- $\text{AND}$ 게이트논리곱
- $\text{OR}$ 게이트논리합
- $\text{NOT}$ 게이트논리 부정
- $\text{XOR}$ 게이트배타적 논리합
- $\text{NOR}$ 게이트부정논리합
- $\operatorname{CNOT}$ 게이트
- 토폴리 게이트$\text{CCNOT}$ 게이트
- 프레드킨 게이트$\text{CSWAP}$ 게이트
김영훈·허재성, 양자 정보 이론 (2020), p86-87 ↩︎