否定論理和、NORゲート

定義¹

以下のようなブール関数を $\text{NOR}$ゲート^{NOR gate}または否定論理和と呼び、次のように表記する。

$$ \downarrow : \left\{ 0, 1 \right\}^{2} \to \left\{ 0, 1 \right\} $$

$$ 0\downarrow 0 = 1,\quad 0\downarrow 1 = 0,\quad 1\downarrow 0 = 0,\quad 1\downarrow 1 = 0 $$

説明

$\text{NOT}$ゲートと$\text{OR}$ゲートの合成であり、$\text{N(OT)}$と$\text{OR}$を取り入れて$\text{NOR}$と名付けた。

$$ \begin{equation} \downarrow = \lnot \circ \lor \end{equation} $$

$$ a \downarrow b = \lnot (a \lor b) $$

$\text{OR}$ゲートとは逆に動作し、すべての入力が偽のときのみ真を出力する。また、$\left\{ \downarrow \right\}$は機能的に完全であり、$(1)$により当然と言える。

부울 함수	기호	진리표
$\text{NOR}$		$a$ $b$ $a \downarrow b$ $0$ $0$ $1$ $0$ $1$ $0$ $1$ $0$ $0$ $1$ $1$ $0$

結論

(複製関数を許容するなら) $\left\{ \downarrow \right\}$は機能的に完全である。言い換えると、$\downarrow$は汎用ゲートである。

証明

定理

$\text{NOT}$と$\text{OR}$ゲートの集合$\left\{ \lnot, \lor \right\}$は機能的に完全である。

上の定理に従い、複製関数$\text{cl}$と$\downarrow$だけで$\text{NOT}$ゲートと$\text{OR}$ゲートを作ることができることを示せばよい。

• $\text{NOT}$ゲート

  $$ \lnot = \downarrow \circ \operatorname{cl} \\ \lnot a = a \downarrow a $$

  が成立する。

  $$ \begin{align*} \downarrow \circ \operatorname{cl}(0) = 0 \downarrow 0 = 1 = \lnot 0 \\ \downarrow \circ \operatorname{cl}(1) = 1 \downarrow 1 = 0 = \lnot 1 \\ \end{align*} $$

• $\text{OR}$ゲート

  $$ \lor = \downarrow \circ \operatorname{cl} \circ \downarrow \\ a \lor b = (a \downarrow b) \downarrow (a \downarrow b) $$

  が成立する。

  $$ \begin{align*} (0 \downarrow 0) \downarrow (0 \downarrow 0) = (1 \downarrow 1) = 0 = 0 \lor 0 \\ (0 \downarrow 1) \downarrow (0 \downarrow 1) = (0 \downarrow 0) = 1 = 0 \lor 1 \\ (1 \downarrow 0) \downarrow (1 \downarrow 0) = (0 \downarrow 0) = 1 = 1 \lor 0 \\ (1 \downarrow 1) \downarrow (1 \downarrow 1) = (1 \downarrow 1) = 1 = 1 \lor 1 \\ \end{align*} $$

■