NOR Gate
양자정보이론 | ||||||||||||||||
[ 펼치기 · 접기 ]
|
Definition1
The following Boolean function is called the $\text{NOR}$ gate or negated logical sum and is denoted as follows.
$$ \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 $$
Description
It is a composition of the $\text{NOT}$ gate and the $\text{OR}$ gate, and it is named $\text{NOR}$ by borrowing $\text{N(OT)}$ and $\text{OR}$.
$$ \begin{equation} \downarrow = \lnot \circ \lor \end{equation} $$
$$ a \downarrow b = \lnot (a \lor b) $$
It operates opposite to the $\text{OR}$ gate and produces a true output only when all inputs are false. Furthermore, $\left\{ \downarrow \right\}$ is functionally complete, which can be seen as obvious due to $(1)$.
부울 함수 | 기호 | 진리표 | |||||||||||||||
$\text{NOR}$ |
|
Theorem
If the replication function is allowed, then $\left\{ \downarrow \right\}$ is functionally complete. In other words, $\downarrow$ is a universal gate.
Proof
The set of $\text{NOT}$ and $\text{OR}$ gates, $\left\{ \lnot, \lor \right\}$, is functionally complete.
According to the above theorem, it suffices to show that the $\text{NOT}$ gate and the $\text{OR}$ gate can be made only with the replication function $\text{cl}$ and $\downarrow$.
$\text{NOT}$ gate
$$ \lnot = \downarrow \circ \operatorname{cl} \\ \lnot a = a \downarrow a $$
holds.
$$ \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}$ gate
$$ \lor = \downarrow \circ \operatorname{cl} \circ \downarrow \\ a \lor b = (a \downarrow b) \downarrow (a \downarrow b) $$
holds.
$$ \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*} $$
■
Kim Young-hoon and Heo Jae-seong, Quantum Information Theory (2020), p86-87 ↩︎