Question

Is there a single type of logic gate that can be used to build all circuits that can be built using \({\bf{OR}}\)gates, \({\bf{AND}}\) gates, and inverters?

Short answer

Yes, a single type of logic gate that can be used to build all circuits.

Step-by-step solution

Definition

The complement of an element: \({\bf{\bar 0 = 1}}\) and \({\bf{\bar 1 = 0}}\).

The Boolean sum \({\bf{ + }}\) or \({\bf{OR}}\) is \({\bf{1}}\) if either term is \({\bf{1}}{\bf{.}}\)

The Boolean product \({\bf{ \bullet }}\)or \({\bf{AND}}\) is \({\bf{1}}\) if both terms are \({\bf{1}}{\bf{.}}\)

The \({\bf{NAND}}\) operator \(\mid \) is \({\bf{1}}\) if either term is \({\bf{0}}\).

The \({\bf{NOR}}\) operator \( \downarrow \) is \({\bf{1}}\) if both terms are \({\bf{0}}\).

The \({\bf{XOR}}\) operator \( \oplus \) is \({\bf{1}}\) if one of the terms is \({\bf{1}}\) (but not both).

An inverter (Not gate) takes the complement of the input.

An \({\bf{AND}}\)gate takes the Boolean product of the input.

An \({\bf{OR}}\) gate takes the Boolean sum of the input.

An \({\bf{NOR}}\) gate takes the \({\bf{NOR}}\) operator of the input.

Using the Boolean sum and product

Every Boolean function can be represented using the operators \( \bullet {\bf{, + }}\) and \(^{\bf{ - }}\) ,which

implies that the set \(\left\{ {{\bf{ \bullet , + }}{{\bf{,}}^{\bf{ - }}}} \right\}\) is functionally complete.

By the previous exercises:

\(\begin{array}{c}{\bf{\bar x = x}} \downarrow {\bf{x}}\\{\bf{xy = (x}} \downarrow {\bf{x)}} \downarrow {\bf{(y}} \downarrow {\bf{y)}}\\{\bf{x + y = (x}} \downarrow {\bf{y)}} \downarrow {\bf{(x}} \downarrow {\bf{y)}}\end{array}\)

Thus, now can write any expression including a complement, a Boolean product and a Boolean sum using the \({\bf{NOR}}\) operator \( \downarrow \) (by using the above equations to rewrite the expressions of the Boolean functions). Since \({\bf{\{ }} \bullet {\bf{, + , - \} }}\) functionally complete, \( \downarrow \) is also functionally complete. The \({\bf{NOR}}\) gate corresponds to the \({\bf{NOR}}\) operator. Since the \({\bf{NOR}}\) operator is a functionally complete set, the \({\bf{NOR}}\) gate can be used to build \({\bf{OR}}\) gates, \({\bf{AND}}\) gates and inverters.