NOR Gate

Definition¹

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

Theorem

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

Proof

Theorem

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

■