Essential Logic Gates

Why This Matters

Logic gates are the atomic units of digital computation—every processor, memory chip, and circuit you'll encounter is built from combinations of these seven fundamental operations. In Discrete Mathematics, you're being tested on your ability to translate between Boolean expressions, truth tables, and gate diagrams, and to recognize how complex logical statements decompose into simpler operations. Understanding gates also connects 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. The exam 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$—mirrors multiplication since $1 \cdot 0 = 0$
• Truth table pattern: produces exactly one 1 (when inputs are 1,1)—the most restrictive basic gate

OR Gate

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

NOT Gate

• Inverts the input—the only single-input gate, flipping 1 to 0 and 0 to 1
• Symbolized as $\neg A$, $\bar{A}$, or $A'$—all notations appear on exams
• Essential for De Morgan's Laws—negation distributes over AND/OR by swapping the operation

---

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 1,1)—the inverse of AND's single 1

NOR Gate

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

---

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$—the "exclusive or" that rejects the "both true" case
• Key application: binary addition without carry—$1 \oplus 1 = 0$ mirrors $1 + 1 = 10_2$

XNOR Gate

• Outputs 1 when inputs MATCH—true for (0,0) and (1,1), the equality detector
• Equivalent to $\overline{A \oplus B}$ or $(A \cdot B) + (\bar{A} \cdot \bar{B})$—XOR followed by NOT
• 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 an FRQ asks you 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?