logo

負論理積、NANDゲート

負論理積、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}$
$a$$b$$a \uparrow b$
$0$$0$$1$
$0$$1$$1$
$1$$0$$1$
$1$$1$$0$

定理

(複製関数を許容すると) $\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*} $$


  1. キム・ヨンフン, ホ・ジェソン, 量子情報理論 (2020), p86-87 ↩︎