負論理積、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*} $$
■
キム・ヨンフン, ホ・ジェソン, 量子情報理論 (2020), p86-87 ↩︎