Skip to content
Tutorials Center
My learning

Topics

Lesson 51 of 68 ยท Algebraic Structures and Boolean Algebra

Boolean Algebra and Logic Circuits

Learn Boolean algebra, logic gates, Karnaugh maps, half and full adders, and build a small ALU from gates in Python, with live examples.

Every processor, from a phone chip to a data-center CPU, is built from tiny switches that are either on or off. Boolean algebra is the mathematics of those two values. It is the same logic you met in propositional logic and logical equivalences, with the names changed: AND, OR and NOT become gates, and true and false become 1 and 0.

In this lesson we treat Boolean algebra as an engineering tool. We write gates as Python functions, check the standard identities by brute force, simplify a function with a Karnaugh map, and then assemble real arithmetic: a half adder, a full adder, a ripple-carry adder, and finally one slice of an ALU (arithmetic logic unit), the part of a CPU that adds, subtracts and compares. Everything we build is checked against ordinary Python integers, so you can see that gates really do arithmetic.

From logic to hardware

Gates AND, OR, NOT, NAND, NOR, XOR as tiny circuits.
Algebra Identities let us shrink a circuit safely.
Adders Gates chained together do binary addition.
1 / 2

Boolean algebra and gates

A Boolean algebra works on the values 0 and 1 with three basic operations: AND (written ยท or juxtaposition, AยทB), OR (+, so A + B) and NOT (a bar or a prime, A'). Careful: here + means OR, not addition, so 1 + 1 = 1.

Each operation has a physical gate. Other useful gates are built from the basic ones:

  • NAND is NOT-AND and NOR is NOT-OR.
  • XOR (exclusive or) is 1 when its inputs differ: A โŠ• B = AยทB' + A'ยทB.
  • XNOR is 1 when the inputs are equal.

NAND and NOR are each functionally complete: you can build every other gate from NAND alone. That is why chip makers like them, since one kind of gate is enough. The standard laws are the ones you already know from logic: commutative, associative, distributive, identity (A + 0 = A, Aยท1 = A), complement (A + A' = 1, AยทA' = 0), idempotent (A + A = A), absorption (A + AยทB = A) and De Morgan ((AยทB)' = A' + B'). Every law has a dual, obtained by swapping AND with OR and 0 with 1.

Because a Boolean function of n variables has only 2^n input rows, we can prove any identity by testing all rows, exactly like a truth table.

Python Gates, NAND universality and identities

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.

Sum of products and simplification

Any Boolean function can be written as a sum of products (SOP): OR together one AND-term for every input row where the function is 1. Each such term is a minterm. This is the disjunctive normal form from the logic chapter, and it always works, but the result is usually bigger than needed. Smaller expressions mean fewer gates, less power and faster circuits.

You can simplify with the laws. For example, AยทB + AยทB' = Aยท(B + B') = A. Doing that by hand on a big expression is error-prone, which is where Karnaugh maps help.

Useful theorems and how many functions exist

Beyond the basic laws, a few theorems save real work in simplification.

Duality. Swap every AND with OR and every 0 with 1 in a true identity, and you get another true identity. So you only ever prove half the laws: A + AยทB = A has the dual Aยท(A + B) = A.

Redundancy and consensus. Some terms add nothing. The consensus theorem says

TEXT
AยทB + A'ยทC + BยทC = AยทB + A'ยทC

The term BยทC (the "consensus" of the other two) is redundant, because whenever BยทC is 1, either A or A' is 1, so one of the other two terms is already 1. Its dual is (A + B)(A' + C)(B + C) = (A + B)(A' + C). Spotting a consensus term is a favorite way to remove a gate.

Transposition. (A + B)(A' + C) = AยทC + A'ยทB. It converts a product of sums into a sum of products in one step.

Absorption variants. A + A'ยทB = A + B and Aยท(A' + B) = AยทB remove a literal rather than a whole term.

Any of these can be proved by testing all 2^n rows. The code below also counts functions. A Boolean function of n variables assigns a 0 or 1 to each of the 2^n rows, and each row can be chosen independently, so there are exactly 2^(2^n) different functions. With 2 variables that is 16 (AND, OR, XOR, NAND, and 12 more, including the constants), with 3 variables 256, and with 4 variables 65,536.

Python Proving theorems by truth table and counting functions

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 counting fact explains why hardware designers care about a small, functionally complete gate set: even 4 inputs allow 65,536 different behaviors, yet NAND gates alone can realize every one.

Karnaugh maps

A Karnaugh map (K-map) lays out the truth table as a grid in which neighboring cells differ in exactly one variable. To make that work, rows and columns are labeled in Gray code order 00, 01, 11, 10, not in counting order. The grid also wraps around: the top row neighbors the bottom row, and the left column neighbors the right.

To simplify, circle rectangular groups of 1s whose size is a power of two (1, 2, 4, 8, ...). A group of size 2^k lets you drop k variables, because inside the group those variables take both values. Use the largest groups you can, cover every 1, and write one product term per group.

Here is a four-variable function with 1s at minterms 0, 1, 2, 5, 8, 9 and 10. In the map, the four corners and the edges wrap together, so the cells 0, 2, 8, 10 form a group where only B' D' stay constant. The cells 0, 1, 8, 9 give B' C', and the cells 1 and 5 give A' C' D. So the minimal form is B'D' + B'C' + A'C'D. The code prints the map and proves the shorter formula equals the original on all 16 rows.

Python A Karnaugh map and its simplified formula

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.

K-maps are practical up to about four or five variables. For larger functions, tools use algorithms such as Quine-McCluskey or heuristic minimizers, but the idea is the same: merge neighboring 1s to eliminate variables. The map also lets you use don't-care cells, inputs that can never occur, as either 0 or 1, whichever gives a bigger group.

Half adders and full adders

Now arithmetic. To add two single bits, there are four cases: 0+0=0, 0+1=1, 1+0=1 and 1+1=10 in binary. So the result needs a sum bit and a carry bit:

  • sum = A โŠ• B
  • carry = A ยท B

That circuit is a half adder. It is "half" because it has no input for a carry arriving from a lower column. A full adder adds three bits, A, B and a carry-in Cin:

  • sum = A โŠ• B โŠ• Cin
  • carry-out = AยทB + Cinยท(A โŠ• B)

Chain n full adders, feeding each carry-out into the next carry-in, and you have an n-bit ripple-carry adder. It is called "ripple" because the carry has to travel through every stage in turn, which limits speed; real CPUs use faster carry-lookahead designs that compute carries in parallel.

flowchart LR
    A0["a0, b0"] --> FA0["Full adder 0"]
    C0["carry in = 0"] --> FA0
    FA0 -->|"carry"| FA1["Full adder 1"]
    A1["a1, b1"] --> FA1
    FA1 -->|"carry"| FA2["Full adder 2"]
    A2["a2, b2"] --> FA2
    FA2 -->|"carry out"| OUT["Carry out"]

The carry ripples from the lowest bit to the highest, one adder at a time.

Python Half adder, full adder and a ripple-carry adder

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.

One slice of an ALU

An ALU takes two numbers and a few control wires that select an operation. A common design is a bit slice: one small circuit that handles a single bit position. Put n slices side by side, pass the carry from one to the next, and you have an n-bit ALU.

A tiny ALU slice can do four things, picked by two select bits:

select operation
00 A AND B
01 A OR B
10 A + B (add)
11 A - B (subtract)

Subtraction reuses the adder. In two's complement, A - B equals A + (NOT B) + 1. So the slice flips B with an XOR gate controlled by a "subtract" wire, and the lowest carry-in is also set to that wire. No separate subtractor is needed, which is exactly why two's complement is used.

Python A 4-bit ALU built from gates

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 zero flag at the end is how a CPU decides whether two values are equal: subtract them and see if the result is zero. Comparisons, loops and if statements all come down to a few signals like that.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In Boolean algebra, what is 1 + 1?

    In Boolean algebra + means OR, and 1 OR 1 is 1.
  2. 2. Which gate is functionally complete by itself?

    NOT, AND and OR can all be built from NAND alone (NOR has the same property). AND, OR and XOR alone cannot build NOT.
  3. 3. A half adder computes which sum and carry for inputs A and B?

    Adding two bits gives 0, 1, 1, or 10. The low bit is XOR and the carry is 1 only when both inputs are 1.
  4. 4. Why are Karnaugh map rows and columns labeled 00, 01, 11, 10?

    Gray code ordering makes adjacent cells differ in one bit, so groups of 1s correspond to dropping variables.
  5. 5. How does the ALU slice subtract using the adder?

    A - B equals A + NOT B + 1 in two's complement, so inverting B and setting the first carry-in to 1 reuses the adder.

Summary

  • Boolean algebra uses 0 and 1 with AND, OR and NOT; gates are the circuits for those operations, and NAND (or NOR) alone can build any circuit.
  • Identities such as De Morgan, absorption and distribution can be proved by checking all 2^n input rows.
  • Any function has a sum-of-products form; simplifying it means fewer gates.
  • A Karnaugh map lists the truth table in Gray-code order so that groups of neighboring 1s show which variables can be dropped.
  • A half adder gives sum = A โŠ• B, carry = AยทB; a full adder adds a carry-in; chaining full adders gives a ripple-carry adder.
  • An ALU slice combines AND, OR, add and subtract, with subtraction done by inverting B and setting the carry-in.

Next: Groups, Rings and Fields (Gentle Intro), where we study operations in the abstract.