Question

Prove that the NOR gate is universal by showing how to build the AND, OR, and NOT functions using a two-input NOR gate.

Short answer

According to DeMorgan’s law, the complement of the OR of two values is equal to the AND of their complements and the complement of the AND of two values is equal to the OR of their complements.

Using this law, the AND function for two values X and Y can be built as$AB=\overline{\overline{A}+\overline{B}}$

The OR function can be built as$A+B=\overline{\overline{A+B}}$.

The NOT function can be built as$\overline{A}=\overline{A+A}$.

Step-by-step solution

DeMorgan’s theorem is a set of rules for boolean expressions for AND, OR, NOT functions

According to DeMorgan’s theorem,

$$\begin{gathered} \overline{A.B}=\overline{A}+\overline{B} \\ \overline{A+B}=\overline{A}·\overline{B} \end{gathered}$$

Build AND function using two-input NOR gate

To build AND function using NOR gate, three NOR gates are required. The same value A is passed to the both inputs of the first NOR gate and Y to the inputs of both inputs to the second NOR gate. The output of these two NOR gates is passed to the third NOR gate. The output of the third NOR gate is equal to the AND function.

Build OR function using a two-input NOR gate

To build OR function using NOR gate, two NOR gates are required. The value A and B is passed to the first gate and the output of the first gate is passed to both inputs of the second NOR gate.

Build NOT function using two-input NOR gate

To build a NOT function using a NOR gate, one NOR gate is required. The input to the NOR gate is a tie of the two inputs together.