Boolean Algebra

Boolean algebra works with two values, 0 and 1, and three operations:

It is propositional logic in algebraic dress (T = 1, F = 0) and set algebra in disguise (∪ = +, ∩ = ·). George Boole introduced it in 1854; Claude Shannon showed in 1937 that it describes switching circuits — the birth of digital electronics.

#Laws

Duality: swap + with ·, and 0 with 1, in any identity and you get another valid identity. That is why the laws come in pairs.

#Boolean functions and normal forms

A Boolean function of n variables maps each of the 2ⁿ input combinations to 0 or 1. There are 2^(2ⁿ) such functions.

• Sum of products (SOP / DNF): OR together a minterm (an AND of all variables, complemented where 0) for every row where f = 1.
• Product of sums (POS / CNF): AND together a maxterm for every row where f = 0.

Example: the majority function of three inputs (1 when at least two inputs are 1):

SOP: f = x′yz + xy′z + xyz′ + xyz, which simplifies to f = xy + yz + xz.

#Logic gates

NAND and NOR are each functionally complete: any Boolean function can be built from NAND gates alone. For example, x′ = (x·x)′ and x·y = ((x·y)′)′.

#Simplifying with Karnaugh maps

A Karnaugh map (K-map) arranges a function's truth table in a grid whose rows and columns are in Gray code order (00, 01, 11, 10), so neighbouring cells differ in exactly one variable. To simplify:

1. Write a 1 in each cell where f = 1.
2. Circle rectangular groups of 1, 2, 4 or 8 adjacent 1s (groups may wrap around the edges), as large as possible.
3. Each group becomes one product term: keep only the variables that do not change within the group.
4. OR the terms together.

For the majority function (rows x, columns yz):

Three overlapping pairs give yz (column 11), xz (cells 101, 111) and xy (cells 111, 110): f = xy + yz + xz.

Verify any simplification by comparing truth tables:

from itertools import product

def majority_sop(x, y, z):
    return (not x and y and z) or (x and not y and z) or (x and y and not z) or (x and y and z)

def majority_simple(x, y, z):
    return (x and y) or (y and z) or (x and z)

same = all(bool(majority_sop(*v)) == bool(majority_simple(*v)) for v in product([0, 1], repeat=3))
print("simplified circuit matches:", same)

def nand(a, b): return int(not (a and b))
def xor_from_nand(a, b):
    m = nand(a, b)
    return nand(nand(a, m), nand(b, m))      # XOR built from four NAND gates
print("XOR from NANDs:", [xor_from_nand(a, b) for a, b in product([0, 1], repeat=2)])

simplified circuit matches: True
XOR from NANDs: [0, 1, 1, 0]

#Half adder

Adding two bits produces a sum bit S = x ⊕ y and a carry bit C = x · y — one XOR gate and one AND gate. Chaining full adders gives the circuits that add numbers inside every CPU (see Logic Gates in Foundations).