Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 67 · Digital Logic

Logic Gates and Boolean Algebra

Learn AND, OR, NOT, XOR, NAND and NOR gates, truth tables, Boolean laws, De Morgan's theorems and universal gates, with a Python truth-table generator.

Everything a computer does, from adding numbers to drawing this page, is built from tiny circuits that answer yes/no questions. Each circuit is a logic gate: it takes one or more inputs that are either 0 or 1 and produces one output that is also 0 or 1. Billions of gates wired together make a processor.

The mathematics of gates is Boolean algebra, invented by George Boole in the 1800s, long before computers. Once you know a few gates and laws, you can describe a circuit as a formula, simplify it, and prove two circuits do the same thing. In this lesson you will learn the six basic gates, their truth tables, the key Boolean laws, and why NAND alone is enough to build any circuit. You will use Python to generate truth tables and to check laws by brute force.

Bits as voltages

Inside a chip, a signal is a voltage. A voltage near zero means logic 0 (false), and a voltage near the supply voltage means logic 1 (true). Treating signals as only two levels makes circuits robust against noise: small variations do not change the meaning. Transistors act as electrically controlled switches, and a few of them make one gate.

A truth table lists every combination of inputs and the resulting output. With n inputs there are 2^n rows, so tables get large quickly; that is why we also use formulas.

The basic gates

NOT (inverter) flips its single input: NOT 0 = 1, NOT 1 = 0. Notation: A', ¬A, or an overbar.

AND outputs 1 only when all inputs are 1. Notation: A · B or AB.

OR outputs 1 when at least one input is 1. Notation: A + B.

XOR (exclusive OR) outputs 1 when the inputs differ. Notation: A ⊕ B. It is the "odd number of 1s" gate, and the sum bit of a binary adder.

NAND is AND followed by NOT. NOR is OR followed by NOT. Both are cheap to build from transistors, which is why real chips are full of them.

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

(There is also XNOR, the equality gate: 1 when the inputs are the same.)

You can model every gate as a tiny Python function. Python's &, |, ^ already work on bits, and 1 - x flips one.

Python A truth-table generator

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Reading a gate diagram

Circuit diagrams use standard shapes: AND looks like a D, OR like a curved shield, and a small circle on the output (a "bubble") means inversion. In the diagram below a NAND is drawn as an AND gate feeding a NOT.

flowchart LR
  A["A"] --> AND["AND"]
  B["B"] --> AND
  AND --> NOT["NOT"]
  NOT --> Y["Y = NAND(A, B)"]

A NAND gate is an AND gate followed by an inverter.

Boolean algebra and its laws

Boolean algebra has only two values and three main operations (AND, OR, NOT), yet a pleasant set of laws. Writing AND as multiplication and OR as addition makes many look familiar, but a few are different from ordinary algebra.

Law AND form OR form
Identity A · 1 = A A + 0 = A
Null (domination) A · 0 = 0 A + 1 = 1
Idempotent A · A = A A + A = A
Complement A · A' = 0 A + A' = 1
Double negation (A')' = A
Commutative AB = BA A + B = B + A
Associative (AB)C = A(BC) (A + B) + C = A + (B + C)
Distributive A(B + C) = AB + AC A + BC = (A + B)(A + C)
Absorption A(A + B) = A A + AB = A

Notice the second distributive law: OR distributes over AND, which has no counterpart in ordinary arithmetic. Every law has a dual form obtained by swapping AND with OR and 0 with 1.

De Morgan's theorems

Two laws are used constantly to transform circuits:

TEXT
(A · B)' = A' + B'      (NAND = OR of the inverted inputs)
(A + B)' = A' · B'      (NOR  = AND of the inverted inputs)

In words: invert an AND and you get an OR of the inverted inputs; invert an OR and you get an AND of the inverted inputs. Visually: "break the bar, change the sign". De Morgan lets you replace a gate with its dual plus inverters, and is the reason an AND with bubbles on its inputs is the same thing as a NOR.

Rather than trust a table, we can prove a law by checking every input combination. With few variables, brute force is a complete proof.

Python Verify Boolean laws by brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Boolean expressions and circuits

Any truth table can be turned into a formula. The simplest recipe is sum of products: for every row where the output is 1, write an AND term that is true only for that row, then OR all those terms together.

Example: a circuit that outputs 1 when exactly two of the three inputs A B C are 1 has three 1-rows (110, 101, 011):

TEXT
Y = A·B·C' + A·B'·C + A'·B·C

The formula is correct but not minimal. Simplifying with the laws (or with a Karnaugh map, a visual grouping technique) reduces gate count, cost and delay. For example, AB + AB' simplifies to A: factor out A to get A(B + B'), and the complement law gives A · 1 = A.

Python Sum of products from a truth table

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last line shows a simplification: the four-term majority formula collapses to three terms AB + AC + BC. Fewer terms mean fewer gates.

Universal gates

A set of gates is functionally complete if you can build every Boolean function from it. {AND, OR, NOT} is complete. Remarkably, NAND alone is complete, and so is NOR alone. That is why NAND and NOR are called universal gates. A chip designer can use a single gate type everywhere, which simplifies manufacturing.

Here is how to build the basics from NAND:

  • NOT A = NAND(A, A)
  • A AND B = NOT(NAND(A, B)) = NAND(NAND(A, B), NAND(A, B))
  • A OR B = NAND(NOT A, NOT B) (De Morgan)
  • A XOR B takes four NAND gates.
flowchart LR
  A["A"] --> N1["NAND 1"]
  B["B"] --> N1
  A --> N2["NAND 2"]
  N1 --> N2
  B --> N3["NAND 3"]
  N1 --> N3
  N2 --> N4["NAND 4"]
  N3 --> N4
  N4 --> X["A XOR B"]

XOR built from four NAND gates.

Python Everything from NAND

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Gate delay and fan-in

Real gates are not instant. Each has a propagation delay, typically a few picoseconds in modern chips, and the longest chain of gates between two registers decides how fast the clock can run. Gates also have fan-in (how many inputs) and fan-out (how many other gates one output can drive). Big expressions are split into trees of small gates, trading depth for width. These limits shape the adders and ALUs you will build soon.

You already use Boolean logic in programs: and, or, not, and the bitwise &, |, ^, ~. A bitwise operator is just a row of gates, one per bit. See Python's bitwise operators.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. For which inputs does a two-input XOR gate output 1?

    XOR is 1 when exactly one input is 1, that is, when the inputs differ. OR also gives 1 for 1,1; XOR does not.
  2. 2. According to De Morgan's law, (A + B)' equals which expression?

    Inverting an OR gives an AND of the inverted inputs: NOR(A, B) = A'B'.
  3. 3. Why are NAND and NOR called universal gates?

    From NAND alone you can make NOT, AND, OR and everything else, so a design needs only one gate type.
  4. 4. How many rows does the truth table of a circuit with 4 inputs have?

    n inputs give 2^n input combinations, so 4 inputs give 16 rows.
  5. 5. Which law lets you simplify A + AB to A?

    Absorption says A + AB = A: if A is 1 the whole expression is 1, and if A is 0 both terms are 0.

Summary

  • Gates map 0/1 inputs to a 0/1 output; truth tables list every case, with 2^n rows for n inputs.
  • The basic gates are NOT, AND, OR, XOR, NAND and NOR (plus XNOR).
  • Boolean laws (identity, complement, distributive, absorption and so on) let you simplify formulas; De Morgan converts between AND and OR forms.
  • Sum of products turns any truth table into a formula, which can then be simplified.
  • NAND and NOR are universal: any circuit can be built from one of them.
  • With few inputs, brute-force truth tables prove or disprove a law.

Next, combine gates into useful building blocks in Combinational Circuits.