부정논리곱, NAND 게이트

양자정보이론

[ 펼치기 · 접기 ]

양자계산	논리게이트	비트 · 부울함수(AND · OR · NOT · XOR · NAND · NOR · CNOT · CCNOT · CSWAP) · 범용 게이트 · 복제 함수 · 사영 · 주입
	양자게이트	큐비트 · 양자 얽힘 · 양자 회로 · 양자 게이트(파울리 게이트 · 위상 게이트 · 아다마르 게이트 · 양자 CNOT · 교환 게이트 · 양자 CSWAP · 양자 CSWAP) · 솔베이-키타예프 정리 · 복제 불가 정리
정보이론	고전정보이론	정보량 · 엔트로피(결합 엔트로피 · 조건부 엔트로피 · 상대적 엔트로피 · 상호 정보 ) · 부호화 · 복호화
	양자정보이론	TBD · TBD · TBD
관련 분야
선형대수 · 양자역학

정의¹

다음과 같은 부울함수를 $\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*}$

■