🟰Algebraic Logic

Basic Logic Gates

Study smarter with Fiveable

Get study guides, practice questions, and cheatsheets for all your subjects. Join 500,000+ students with a 96% pass rate.

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

Compare: AND vs. OR—both are binary operations combining two inputs, but AND requires all conditions true (outputs 0 in three of four cases) while OR requires any condition true (outputs 1 in three of four cases). If an exam asks about "restrictive" vs. "permissive" logic, this is your go-to contrast.

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

Compare: NAND vs. NOR—both are universal gates and both are negations of primary gates, but NAND negates AND (false only when both true) while NOR negates OR (true only when both false). FRQs about circuit minimization often ask you to implement functions using only one universal gate type.

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

Compare: XOR vs. XNOR—these are exact complements. XOR detects difference (useful for addition and error detection), while XNOR detects sameness (useful for comparison operations). Remember: XOR is sometimes called the "inequality gate" and XNOR the "equality gate."

Quick Reference Table

Concept	Best Examples
Primary/Foundational Gates	AND, OR, NOT
Universal Gates	NAND, NOR
Complement Pairs	AND/NAND, OR/NOR, XOR/XNOR
Single-Input Operation	NOT
Exclusive/Difference Detection	XOR
Equality Detection	XNOR
Used in Binary Arithmetic	XOR, AND
Most Common in IC Manufacturing	NAND

Self-Check Questions

Which two gates are considered universal, and what does "universal" mean in this context?
Compare AND and NAND: how do their truth tables relate, and what algebraic operation transforms one into the other?
If you need to detect whether two binary inputs are equal, which gate would you use? Which gate detects when they differ?
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?
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?