Logic Gates

Physical implementations of Boolean operations - AND, OR, NOT, NAND, NOR, XOR gates and their symbols.

12 topics • ~1176 words

The valve chamber was a prototype. The real system is etched in silicon— millions of gates, each one a tiny switch doing exactly what the valves do. AND, OR, NOT. The logic is the same. Only the scale has changed.

Everything we have learned about Boolean logic has a physical implementation. Logic gates are electronic circuits that perform these operations—the building blocks of every computer ever made.

Introduction to Logic Gates

Logic gates are electronic circuits that implement Boolean operations:

Gate Operation Symbol
AND A $\land$ B Flat-ended shape
OR A $\lor$ B Curved/pointed shape
NOT $\neg$A Triangle with bubble
NAND $\neg$(A $\land$ B) AND with bubble
NOR $\neg$(A $\lor$ B) OR with bubble

Gates are the building blocks of all digital circuits - from simple calculators to complex CPUs.

Basic Gates (AND, OR, NOT)

AND gate: series connection—both switches must close.

OR gate: parallel connection—any switch closing completes the circuit.

NOT gate: a relay that flips the signal. Same logic, different medium.

The three fundamental gates:

AND Gate ($\land$)

  • Output 1 only when ALL inputs are 1
  • A AND B = A · B = A $\land$ B

OR Gate ($\lor$)

  • Output 1 when ANY input is 1
  • A OR B = A + B = A $\lor$ B

NOT Gate ($\neg$) - also called "inverter"

  • Output is opposite of input
  • NOT A = A' = $\neg$A = Ā

Any Boolean function can be built from just these three gates!

NAND and NOR Gates

NAND Gate = NOT + AND

  • $\neg$(A $\land$ B) - output 0 only when BOTH inputs are 1
  • Output 1 in all other cases

NOR Gate = NOT + OR

  • $\neg$(A $\lor$ B) - output 1 only when BOTH inputs are 0
  • Output 0 in all other cases

Universal gates: NAND and NOR are each "universal" - you can build ANY Boolean function using only NAND gates (or only NOR gates)!

This is why NAND is the most commonly used gate in digital ICs.

XOR and XNOR Gates

XOR Gate (Exclusive OR)

  • A $\oplus$ B = output 1 when inputs DIFFER
  • "One or the other, but not both"
  • Used for: parity checking, addition, comparison

XNOR Gate (Exclusive NOR) = NOT XOR

  • A ⊙ B = output 1 when inputs are SAME
  • Also called "equivalence gate"
  • Used for: equality comparison, bit matching

XOR is fundamental in:

  • Binary addition (half adder, full adder)
  • Parity generation and checking
  • Error detection codes

Gate Truth Tables

Truth tables for 2-input gates:

A B AND OR NAND NOR XOR XNOR
0 0 0 0 1 1 0 1
0 1 0 1 1 0 1 0
1 0 0 1 1 0 1 0
1 1 1 1 0 0 0 1

Patterns to remember:

  • AND: Only one 1 (when both inputs are 1)
  • OR: Only one 0 (when both inputs are 0)
  • NAND/NOR: Complements of AND/OR
  • XOR: 1 when different; XNOR: 1 when same

Multi-Input Gates

Gates can have more than 2 inputs:

Gate Output is 1 when...
AND ALL inputs are 1
OR ANY input is 1
NAND NOT all inputs are 1
NOR NO inputs are 1

Multi-input gates are equivalent to cascading 2-input gates:

(A $\land$ B $\land$ C) = (A $\land$ B) $\land$ C

Gates and Boolean Expressions

Gate circuits $\leftrightarrow$ Boolean expressions:

Each gate corresponds to an operation:

  • AND gate $\to$ A $\land$ B (or A · B)
  • OR gate $\to$ A $\lor$ B (or A + B)
  • NOT gate $\to$ $\neg$A (or A')
  • NAND gate $\to$ $\neg$(A $\land$ B)
  • NOR gate $\to$ $\neg$(A $\lor$ B)
  • XOR gate $\to$ A $\oplus$ B

To read a circuit: Start from inputs, follow through gates, write the expression at each gate's output.

To build a circuit: Parse the expression and connect gates accordingly.

Logic Gate Practice

Gate review:

  • AND: Output 1 only when ALL inputs are 1
  • OR: Output 1 when ANY input is 1
  • NOT: Inverts input
  • NAND: NOT of AND
  • NOR: NOT of OR
  • XOR: Output 1 when inputs differ
  • XNOR: Output 1 when inputs are same

Gate Diagram Translation

Reading circuit diagrams:

  • Inputs enter from the left
  • Gates process signals and output to the right
  • Outputs of one gate can feed into inputs of another
  • The final output on the right is the expression result

Writing expressions from diagrams:

  • Start at inputs, trace through each gate
  • Write the operation at each gate's output
  • Nested gates create parenthesized subexpressions

Universal Gates

A gate is universal (or functionally complete) if you can build any other logic function using only that gate.

NAND and NOR are universal gates!

With just NAND gates, you can build:

  • NOT: A NAND A = $\neg$A
  • AND: (A NAND B) NAND (A NAND B)
  • OR: (A NAND A) NAND (B NAND B)

This is important in chip design - entire processors can be built from just one gate type!

Circuit Tracing

Same as tracing flow through the valve chamber—but now the signals are electrons, and the whole system fits on a chip the size of your fingernail.

Circuit tracing means following input signals through gates to find the output.

Process:

  1. Label all input values
  2. Find gates whose inputs are all known
  3. Compute each gate's output
  4. Repeat until you reach the final output

This is how computers execute Boolean expressions in hardware!

Gate Combinations

Complex Boolean functions are built by combining gates:

  • Series: Output of one gate feeds input of another
  • Parallel: Multiple gates process different inputs
  • Feedback: Output connects back to input (used in memory circuits)

Gate count matters for efficiency - fewer gates means faster, cheaper circuits.

Ready to test your understanding?

Bitwit uses spaced repetition to help you truly master concepts like this—not just read about them. Each card generates with different values, so you can't just memorize answers.

Practice Logic Gates →