L13: Universal Gates
Where we learn about negative numbers.
Objective
Develop a basic understanding of addition and subtraction of signed Boolean values.
Additional Materials & Formats
Check Box for the most up-to-date versions of this lecture’s materials.
Before the Lecture
Required Textbook Reading:
- 2.7 (NAND and NOR Logic Networks)
Optional Supplemental Instruction:
- Universal Logic Gates – Electronics Tutorials
- Universal Logic Gates – Wikipedia
- Sheffer Stroke (proof that NAND is universal) – Wikipedia
Universal Logic Gates
Universal logic gates are logic gates that can be used to implement any Boolean function or digital circuit without needing any other gate types. There are two universal gates: NAND and NOR. This section covers their properties, why they are universal, and how they can be used to construct other logic gates.
What Makes a Gate Universal?
A logic gate is considered universal if any other logic gate (AND, OR, NOT, XOR, etc.) can be constructed using only that gate type. This means a universal gate is functionally complete—it can replicate the behavior of all other basic gates. This property is invaluable in digital circuit design because manufacturers can simplify production by fabricating primarily one gate type and still enable the creation of complex systems.
NAND Gate
Definition and Truth Table
The NAND gate (NOT-AND) produces an output of 0 only when all inputs are 1; otherwise, the output is 1. It is the complement of the AND gate.
| A | B | Output |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Boolean expression: Y = (A · B)’ or Y = A NAND B
Why NAND is Universal
The NAND gate is universal because NOT, AND, and OR gates can all be constructed using only NAND gates. Once these three fundamental gates exist, any Boolean function can be expressed and implemented.
Constructing Other Gates with NAND
NOT Gate: Connect both inputs of a NAND gate together. When A = A, the output is (A · A)’ = A’, which is NOT A.
AND Gate: Use two NAND gates in series. The first NAND gate produces (A · B)’, and feeding this into a second NAND gate (with both inputs connected to the output of the first) produces ((A · B)’)’ = A · B.
OR Gate: Convert inputs using De Morgan’s Law. OR can be expressed as A + B = (A’ · B’)’. To implement this: pass A and B through separate NAND gates (configured as NOT gates) to get A’ and B’, then feed these into a third NAND gate to produce the OR output.
NOR Gate
Definition and Truth Table
The NOR gate (NOT-OR) produces an output of 1 only when all inputs are 0; otherwise, the output is 0. It is the complement of the OR gate.
| A | B | Output |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
Boolean expression: Y = (A + B)’ or Y = A NOR B
Why NOR is Universal
Like NAND, NOR is universal because NOT, AND, and OR gates can be constructed using only NOR gates. This makes NOR equally valuable in digital circuit design.
Constructing Other Gates with NOR
NOT Gate: Connect both inputs of a NOR gate together. When A = A, the output is (A + A)’ = A’, which is NOT A.
OR Gate: Use two NOR gates in series. The first NOR gate produces (A + B)’, and feeding this into a second NOR gate (with both inputs connected) produces ((A + B)’)’ = A + B.
AND Gate: Apply De Morgan’s Law: A · B = (A’ + B’)’. Pass A and B through separate NOR gates (configured as NOT gates) to get A’ and B’, then feed these into a third NOR gate to produce the AND output.
Comparison of NAND and NOR
| Property | NAND | NOR |
|---|---|---|
| Universality | Universal—can implement any Boolean function | Universal—can implement any Boolean function |
| Complement of | AND gate | OR gate |
| Output is 1 when | At least one input is 0 | All inputs are 0 |
| Output is 0 when | All inputs are 1 | At least one input is 1 |
| Common use | More commonly used in practice; easier to implement with current semiconductor technology | Used when natural to the problem or design requirements |
Practical Significance
NAND gates are more commonly used in real digital circuits than NOR gates, primarily because they are easier and more cost-effective to implement in CMOS (Complementary Metal-Oxide-Semiconductor) technology, which dominates modern semiconductor manufacturing. However, both gates are equally powerful in theory, and the choice between them depends on design specifics, technological constraints, and the natural structure of the problem being solved.