Basic Logic Gates

Why This Matters

Logic gates are the fundamental building blocks of every digital system you'll encounter in Algebraic Logic. When you're tested on this material, you're not just being asked to recall truth tables—you're being evaluated on your understanding of Boolean algebra, functional completeness, and how simple operations combine to create complex logical behavior. These gates translate abstract algebraic expressions into physical circuit behavior, making them the bridge between theory and application.

The key insight here is that all digital computation—from simple calculators to supercomputers—reduces to combinations of these seven gates. Don't just memorize input-output pairs; know which gates are universal, which are complements of each other, and how each gate's algebraic representation connects to its truth table. This conceptual understanding is what separates strong exam performance from mere memorization.

---

Primary Gates: The Foundational Three

These three gates form the conceptual foundation of Boolean algebra. Every other gate can be expressed as a combination of AND, OR, and NOT operations.

AND Gate

• Outputs 1 only when ALL inputs are 1—this is logical conjunction, the most restrictive basic operation
• Algebraic notation: $A \cdot B$ or $AB$—multiplication symbolism reflects that any zero input "zeroes out" the result
• Circuit application: ensures multiple conditions are simultaneously satisfied before triggering an output

OR Gate

• Outputs 1 when AT LEAST ONE input is 1—this is logical disjunction, the most permissive basic operation
• Algebraic notation: $A + B$—addition symbolism reflects that any true input contributes to a true output
• Circuit application: triggers output when any qualifying condition is met, forming the basis for inclusive logic

NOT Gate

• Inverts the input—1 becomes 0, 0 becomes 1, making this the only single-input gate
• Algebraic notation: $\overline{A}$ or $\neg A$—the complement operation in Boolean algebra
• Building block role: essential for constructing negated expressions and deriving all other gates from AND/OR

---

Universal Gates: Build Anything

A universal gate can implement any Boolean function using only copies of itself. This property makes NAND and NOR extraordinarily important in circuit design and exam questions about functional completeness.

NAND Gate

• Outputs 0 only when BOTH inputs are 1—it's an AND gate followed by a NOT gate
• Algebraic notation: $\overline{A \cdot B}$ or $(AB)'$—the complement of conjunction
• Universal property: any logic circuit can be built using only NAND gates, making it the most common gate in integrated circuits

NOR Gate

• Outputs 1 only when BOTH inputs are 0—it's an OR gate followed by a NOT gate
• Algebraic notation: $\overline{A + B}$ or $(A + B)'$—the complement of disjunction
• Universal property: like NAND, any Boolean function is achievable with NOR gates alone, often preferred in certain manufacturing processes

---

Exclusive Gates: Detecting Difference and Equality

These gates focus on whether inputs match or differ. The XOR operation is fundamental to binary arithmetic, while XNOR serves as an equality comparator.

XOR Gate

• Outputs 1 when inputs DIFFER—exactly one input must be true, not both
• Algebraic notation: $A \oplus B$—equivalent to $(A \cdot \overline{B}) + (\overline{A} \cdot B)$
• Key applications: binary addition (half-adders), parity checking, and error detection circuits

XNOR Gate

• Outputs 1 when inputs MATCH—both must be the same value (both 0 or both 1)
• Algebraic notation: $\overline{A \oplus B}$—the complement of XOR, equivalent to $(A \cdot B) + (\overline{A} \cdot \overline{B})$
• Key applications: digital comparators, equality testing, and bit-matching circuits

---

Quick Reference Table

---

Self-Check Questions

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

2. Compare AND and NAND: how do their truth tables relate, and what algebraic operation transforms one into the other?

3. If you need to detect whether two binary inputs are equal, which gate would you use? Which gate detects when they differ?

4. Explain why $A \oplus B$ can be rewritten as $(A \cdot \overline{B}) + (\overline{A} \cdot B)$. What does this tell you about XOR's relationship to the primary gates?

5. An FRQ asks you to implement the expression $\overline{A} + B$ using only NAND gates. Which property of NAND makes this possible, and what's your first step in the conversion?