否定論理和、NORゲート
양자정보이론 | ||||||||||||||||
[ 펼치기 · 접기 ]
|
定義1
以下のようなブール関数を $\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}$ |
|
結論
(複製関数を許容するなら) $\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*} $$
■
キム・ヨンフン・ホ・ジェソン, 量子情報理論 (2020), p86-87 ↩︎