Essential Logic Gates

Why This Matters

Logic gates are the building blocks of digital computation. Every processor, memory chip, and circuit is built from combinations of seven fundamental operations. In Discrete Mathematics, you need to translate fluently between Boolean expressions, truth tables, and gate diagrams, and to break complex logical statements into simpler operations. Gates also connect directly to proof techniques, set operations, and propositional logic.

Don't just memorize what each gate does. Know why certain gates are called universal, how compound gates relate to their primitive components, and when to apply each gate in Boolean simplification problems. Exams will ask you to evaluate expressions, construct equivalent circuits, and identify which gate produces a specific truth table pattern.

---

Basic Gates: The Primitives

These three gates form the foundation of Boolean algebra. Every other gate can be constructed from combinations of AND, OR, and NOT. Master these first, and the compound gates become intuitive.

AND Gate

• Outputs 1 only when ALL inputs are 1. Think of it as a strict "both must be true" condition.
• Symbolized as $A \cdot B$ or simply $AB$. This mirrors multiplication since $1 \cdot 0 = 0$.
• Truth table pattern: produces exactly one 1 (when both inputs are 1). It's the most restrictive basic gate.

OR Gate

• Outputs 1 when AT LEAST ONE input is 1. This is the inclusive "either or both" operation.
• Symbolized as $A + B$. It resembles addition but caps at 1 (no carrying).
• Truth table pattern: produces exactly one 0 (when both inputs are 0). It's the most permissive basic gate.

NOT Gate

• Inverts the input. It's the only single-input gate, flipping 1 to 0 and 0 to 1.
• Symbolized as $\neg A$, $\bar{A}$, or $A'$. All three notations appear on exams, so recognize each one.
• Essential for De Morgan's Laws. Negation distributes over AND/OR by swapping the operation: $\overline{A \cdot B} = \bar{A} + \bar{B}$ and $\overline{A + B} = \bar{A} \cdot \bar{B}$.

---

Universal Gates: Build Anything

NAND and NOR are called universal gates because either one alone can construct AND, OR, NOT, and therefore any Boolean function. This property makes them crucial for circuit minimization and hardware design.

NAND Gate

• Outputs 0 only when ALL inputs are 1. It's AND followed by NOT, so $\overline{A \cdot B}$.
• Universal gate: you can build any circuit using only NAND gates (common exam question).
• Truth table pattern: produces exactly one 0 (at input 1,1). This is the exact inverse of AND's truth table.

NOR Gate

• Outputs 1 only when ALL inputs are 0. It's OR followed by NOT, so $\overline{A + B}$.
• Also universal. It has equivalent computational power to NAND, just a different default state.
• Truth table pattern: produces exactly one 1 (at input 0,0). This is the exact inverse of OR's truth table.

---

Exclusive Gates: Parity and Equality

XOR and XNOR detect whether inputs match or differ. These gates are essential for arithmetic circuits, error detection, and comparison operations in digital systems.

XOR Gate

• Outputs 1 when inputs DIFFER. True for (0,1) and (1,0), false when inputs match.
• Symbolized as $A \oplus B$. This is the "exclusive or" that rejects the "both true" case that regular OR accepts.
• Key application: binary addition without carry. $1 \oplus 1 = 0$ mirrors the sum digit of $1 + 1 = 10_2$.

Notice that XOR and OR produce the same output for three of the four input combinations. They only differ at (1,1): OR gives 1, XOR gives 0.

XNOR Gate

• Outputs 1 when inputs MATCH. True for (0,0) and (1,1). It's the equality detector.
• Equivalent to $\overline{A \oplus B}$, which can also be written as $(A \cdot B) + (\bar{A} \cdot \bar{B})$. That expanded form reads naturally: "both are 1, or both are 0."
• Key application: bit comparison. Outputs 1 when two bits are identical.

---

Quick Reference Table

---

Self-Check Questions

1. Which two gates are universal, and what does "universal" mean in this context?

2. Given a truth table with outputs (1, 1, 1, 0) for inputs (0,0), (0,1), (1,0), (1,1), which gate does this represent?

3. Compare and contrast XOR and OR: when do they produce the same output, and when do they differ?

4. How would you construct a NOT gate using only NAND gates? What about using only NOR gates?

5. If you need to design a circuit that outputs 1 only when two input bits are equal, which single gate accomplishes this, and what Boolean expression represents it?