Boolean Algebra, Logic Gates & Semiconductor Logic Families

1. Formal Mathematical Axioms of Boolean Algebra

In 1904, Edward V. Huntington formalized George Boole's algebraic logic as a deductive mathematical system defined on a set of elements $B$ with two binary operators: logical OR ($+$) and logical AND ($\cdot$), satisfying six fundamental postulates:

1. Closure: For every $x, y \in B$:
   $$x + y \in B \quad \text{and} \quad x \cdot y \in B$$
2. Identity Elements: There exist unique elements $0, 1 \in B$ such that for every $x \in B$:
   $$x + 0 = x \quad \text{and} \quad x \cdot 1 = x$$
3. Commutative Laws: For every $x, y \in B$:
   $$x + y = y + x \quad \text{and} \quad x \cdot y = y \cdot x$$
4. Distributive Laws: Each operator distributes over the other:
   $$x \cdot (y + z) = (x \cdot y) + (x \cdot z)$$
   $$x + (y \cdot z) = (x + y) \cdot (x + z) \quad (\text{Crucial rule with no ordinary algebra analog!})$$
5. Complement: For every $x \in B$, there exists a unique complement $\bar{x} \in B$ such that:
   $$x + \bar{x} = 1 \quad \text{and} \quad x \cdot \bar{x} = 0$$
6. Distinct Elements: There exist at least two elements $x, y \in B$ such that $x \ne y$.

2. Fundamental Theorems of Boolean Algebra

From Huntington's postulates, the standard operational theorems are deduced:

• Idempotence: $x + x = x$ and $x \cdot x = x$.
• Null Elements (Dominance): $x + 1 = 1$ and $x \cdot 0 = 0$.
• Involution (Double Negation): $\overline{\bar{x}} = x$.
• Absorption Laws:
  $$x + (x \cdot y) = x \quad \text{and} \quad x \cdot (x + y) = x$$
  $$x + (\bar{x} \cdot y) = x + y \quad \text{and} \quad x \cdot (\bar{x} + y) = x \cdot y$$
• Associative Laws:
  $$x + (y + z) = (x + y) + z \quad \text{and} \quad x \cdot (y \cdot z) = (x \cdot y) \cdot z$$

3. The Principle of Duality

The Principle of Duality states: Any true Boolean algebraic identity remains strictly valid if the operators $+$ and $\cdot$ are interchanged, and the identity elements $0$ and $1$ are simultaneously interchanged.

For example, the dual of the distributive law $x \cdot (y + z) = (x \cdot y) + (x \cdot z)$ is directly obtained by swapping $\cdot \leftrightarrow +$:

Duality halves the labor of Boolean mathematical proofs: proving one theorem automatically validates its dual.

1. Augustus De Morgan's Laws

Augustus De Morgan (1847) established the two most celebrated theorems in digital circuit design, defining the rigorous relationship between conjunction, disjunction, and complementation:

In digital circuit topology, De Morgan's laws state that a NOR gate (OR followed by inversion) is functionally identical to an AND gate with inverted inputs (negative-AND), and a NAND gate is identical to a negative-OR gate:

2. Generalized Generalized Multi-Variable Formulation

By mathematical induction, De Morgan's laws extend to an arbitrary number of $n$ variables:

To complement any arbitrary Boolean function $F(A, B, C, \dots, +, \cdot)$, one simultaneously applies De Morgan's rule across all levels: interchange all $+$ and $\cdot$ operators, and complement every individual literal ($A \to \bar{A}$ and $\bar{A} \to A$).

3. The Consensus Theorem

The Consensus Theorem provides a powerful shortcut for eliminating redundant terms in multi-variable equations without tedious K-map expansion:

where $B C$ is the consensus term formed from the conjunction of the two literals associated with the complemented pair $A$ and $\bar{A}$. In its dual form:

1. Basic Logic Gates and Operational Truth Tables

Digital logic gates are physical electronic circuits that perform elementary Boolean switching operations on binary voltage signals ($V_{LOW} \leftrightarrow 0$, $V_{HIGH} \leftrightarrow 1$):

1. NOT Gate (Inverter): Implements single-input complementation: $Y = \bar{A}$. If $A=0$, $Y=1$; if $A=1$, $Y=0$.
2. AND Gate: Output is HIGH if and only if all inputs are HIGH: $Y = A \cdot B$.
3. OR Gate: Output is HIGH if at least one input is HIGH: $Y = A + B$.
4. NAND Gate: Negated AND operation: $Y = \overline{A \cdot B}$. Output is LOW if and only if all inputs are HIGH.
5. NOR Gate: Negated OR operation: $Y = \overline{A + B}$. Output is HIGH if and only if all inputs are LOW.

2. Exclusive-OR (XOR) & Exclusive-NOR (XNOR) Gates

The XOR gate ($\oplus$), or modulo-2 adder, yields a HIGH output when the inputs are different:

Properties of XOR:

• $A \oplus 0 = A$, \quad $A \oplus 1 = \bar{A}$ (programmable inverter).
• $A \oplus A = 0$, \quad $A \oplus \bar{A} = 1$.
• Commutative: $A \oplus B = B \oplus A$; Associative: $(A \oplus B) \oplus C = A \oplus (B \oplus C)$.
• For $n$ inputs, an XOR gate acts as an odd parity detector: output is 1 if and only if an odd number of inputs are 1.

The XNOR gate ($\odot$), or equivalence detector, produces a HIGH output when the inputs are identical:

1. Functional Completeness in Digital Logic

A set of Boolean operators is defined as functionally complete if every arbitrary Boolean function can be expressed solely using operators from that set. The standard set $\{\text{AND}, \text{OR}, \text{NOT}\}$ is functionally complete. However, fabricating multiple distinct gate types on an integrated circuit increases silicon area and manufacturing complexity.

A Universal Gate is a single gate type capable of synthesizing all elementary logic functions (NOT, AND, OR, XOR) without requiring any other components. There exist precisely two universal logic gates in digital electronics: NAND and NOR.

2. NAND-Only Gate Realizations

1. NOT using NAND: Tie both inputs together:
   $$\overline{A \cdot A} = \bar{A}$$
2. AND using NAND: Feed the output of a NAND gate into a NAND-inverter:
   $$\overline{\overline{A \cdot B}} = A \cdot B \quad (\text{2 NAND gates})$$
3. OR using NAND: Invert each input with a NAND gate, then feed into a third NAND gate (De Morgan's law):
   $$\overline{\bar{A} \cdot \bar{B}} = \overline{\bar{A}} + \overline{\bar{B}} = A + B \quad (\text{3 NAND gates})$$
4. NOR using NAND: Invert the output of the NAND-synthesized OR gate:
   $$\overline{A + B} \quad (\text{4 NAND gates})$$
5. XOR using NAND: Synthesize $A \bar{B} + \bar{A} B$ with minimum four 2-input NAND gates:
   $$X = \overline{A B}, \quad Y = \overline{A \cdot X} \cdot \overline{B \cdot X} = A \oplus B \quad (\text{4 NAND gates})$$

3. NOR-Only Gate Realizations

1. NOT using NOR: Tie both inputs together: $\overline{A + A} = \bar{A}$ (1 NOR gate).
2. OR using NOR: Invert the NOR output: $\overline{\overline{A + B}} = A + B$ (2 NOR gates).
3. AND using NOR: Invert each input, then combine in a NOR gate: $\overline{\bar{A} + \bar{B}} = A \cdot B$ (3 NOR gates).
4. NAND using NOR: Invert the output of the NOR-synthesized AND gate (4 NOR gates).
5. XOR using NOR: Synthesized with five 2-input NOR gates.

1. Transistor-Transistor Logic (TTL) & The Totem-Pole Output

Standard BJT Transistor-Transistor Logic (7400 series) operates from a single $+5\text{ V}$ power supply ($V_{CC}$). The canonical TTL NAND gate consists of three stages:

1. Input Stage: Multi-emitter NPN transistor $Q_1$. If any input is LOW ($0.2\text{ V}$), $Q_1$ conducts base current to the LOW input, pulling $Q_1$'s collector voltage low and cutting off phase-splitter $Q_2$.
2. Phase-Splitter Stage: Transistor $Q_2$ generates complementary out-of-phase drive voltages at its collector and emitter.
3. Totem-Pole Output Stage: Consists of pull-up transistor $Q_4$, diode $D$, and pull-down transistor $Q_3$:
   • Output LOW State ($Y = 0$): $Q_2$ and $Q_3$ are saturated. $Q_3$ pulls the output to $V_{OL} \approx V_{CE,\text{sat}} \approx 0.2\text{ V}$. Meanwhile, $Q_4$ is completely off because diode $D$ drops $0.7\text{ V}$, ensuring base-emitter voltage $V_{BE4}$ is insufficient to turn $Q_4$ on.
   • Output HIGH State ($Y = 1$): $Q_2$ and $Q_3$ are cut off. $Q_4$ acts as an active pull-up emitter follower, charging the capacitive load rapidly to $V_{OH} = V_{CC} - V_{BE4} - V_D \approx 5.0 - 0.7 - 0.7 \approx 3.6\text{ V}$.

The totem-pole active pull-up provides low output impedance in both states, dramatically accelerating capacitive line charging compared to passive resistor pull-ups.

2. Complementary MOS (CMOS) Inverter

CMOS technology pairs an enhancement-mode pMOS pull-up transistor with an nMOS pull-down transistor in a symmetric, push-pull configuration:

• Input LOW ($V_{\text{in}} = 0\text{ V}$): $V_{GS,n} = 0 < V_{tn} \implies$ nMOS is OFF. $V_{GS,p} = -V_{DD} < V_{tp} \implies$ pMOS is saturated/linear, pulling $V_{\text{out}}$ to exactly $V_{DD}$ with zero static current.
• Input HIGH ($V_{\text{in}} = V_{DD}$): $V_{GS,n} = V_{DD} > V_{tn} \implies$ nMOS is ON. $V_{GS,p} = 0 \implies$ pMOS is OFF. nMOS pulls $V_{\text{out}}$ to exactly $0\text{ V}$ with zero static current.
• Power Dissipation: Because one transistor is always cut off in the steady state, static power dissipation is virtually zero ($P_{\text{static}} \sim\text{nW}$). Power is consumed only during switching transitions as dynamic power:
  $$P_{\text{dynamic}} = C_L V_{DD}^2 f$$
  where $C_L$ is load capacitance and $f$ is clock switching frequency.

3. Key Logic Family Performance Metrics