NAND Gate

Definition¹

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}$		$a$ $b$ $a \uparrow b$ $0$ $0$ $1$ $0$ $1$ $1$ $1$ $0$ $1$ $1$ $1$ $0$

Theorem

If the replication function is allowed, $\left\{ \uparrow \right\}$ is functionally complete. In other words, $\uparrow$ is a universal gate.

Proof

Theorem

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*} $$

■