NAND Gate
양자정보이론 | ||||||||||||||||
[ 펼치기 · 접기 ]
|
Definition1
The following Boolean function is called a $\text{NAND}$ Gate or Negated Logical Product and is denoted as follows.
$$ \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 $$
Description
It is a composition of the $\text{NOT}$ Gate and $\text{AND}$ Gate, and is named $\text{NAND}$ by adopting $\text{N(OT)}$ and $\text{AND}$.
$$ \begin{equation} \uparrow = \lnot \circ \land \end{equation} $$
$$ a \uparrow b = \lnot (a \land b) $$
It operates opposite to the $\text{AND}$ Gate, outputting false only when all inputs are true. Additionally, $\left\{ \uparrow \right\}$ is functionally complete, which is considered obvious due to $(1)$.
부울 함수 | 기호 | 진리표 | |||||||||||||||
$\text{NAND}$ |
|
Theorem
If the replication function is allowed, $\left\{ \uparrow \right\}$ is functionally complete. In other words, $\uparrow$ is a universal gate.
Proof
The set of $\text{NOT}$ and $\text{AND}$ Gates, $\left\{ \lnot, \land \right\}$, is functionally complete.
According to the above theorem, it is sufficient to show that the $\text{NOT}$ Gate and the $\text{AND}$ Gate can be created solely using the replication function $\text{cl}$ and $\uparrow$.
$\text{NOT}$ Gate
$$ \lnot = \uparrow \circ \operatorname{cl} \\ \lnot a = a \uparrow a $$
holds.
$$ \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}$ Gate
$$ \land = \uparrow \circ \operatorname{cl} \circ \uparrow \\ a \land b = (a \uparrow b) \uparrow (a \uparrow b) $$
holds.
$$ \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*} $$
■
Kim Young-Hoon & Heo Jae-Seong, Quantum Information Theory (2020), pp. 86-87 ↩︎