負論理積、NANDゲート

定義¹

以下のブール関数を**$\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*}$$

■