Boolean Algebra

Boolean algebra is the algebra of two values, 0 and 1, with the operations AND (·), OR (+) and NOT (written A′ or Ā). It describes exactly what logic circuits compute.

Laws

Two more identities are used constantly: A + A′B = A + B and A(A′ + B) = AB.

The second distributive law (A + BC = (A + B)(A + C)) has no counterpart in ordinary arithmetic; it is the dual of the first.

Duality

The dual of an expression swaps AND with OR and 0 with 1 (variables are not complemented). Duality principle: if an identity holds, its dual holds too. That is why every law above comes in pairs.

A function is self-dual if it equals its own dual: f(A, B, C) = f′(A′, B′, C′). Example: the majority function AB + BC + CA.

Canonical forms

Any Boolean function can be written from its truth table.

• A minterm is an AND of all n variables, each plain or complemented, that is 1 for exactly one row. For n = 3, row 5 (101) has minterm m₅ = AB′C.
• A maxterm is an OR of all variables that is 0 for exactly one row. Row 5 has maxterm M₅ = A′ + B + C′.
• Sum of products (SOP), canonical: OR the minterms of the rows where f = 1: f = Σm(…).
• Product of sums (POS), canonical: AND the maxterms of the rows where f = 0: f = ΠM(…).

The two lists are complementary: if f = Σm(2, 3, 5, 6, 7) then f = ΠM(0, 1, 4). And m_i′ = M_i.

from itertools import product

def minterms(f, n):
    return [i for i, row in enumerate(product([0, 1], repeat=n)) if f(*row)]

f = lambda a, b, c: (not a and b) or (b and not c) or (a and c)     # A'B + BC' + AC
ones = minterms(f, 3)
zeros = [i for i in range(8) if i not in ones]
print("f = Σm", tuple(ones))
print("f = ΠM", tuple(zeros))

def term(i, n=3, names="ABC"):
    bits = format(i, f"0{n}b")
    return "".join(v if b == "1" else v + "'" for v, b in zip(names, bits))
print("f =", " + ".join(term(i) for i in ones))

f = Σm (2, 3, 5, 6, 7)
f = ΠM (0, 1, 4)
f = A'BC' + A'BC + AB'C + ABC' + ABC

Counting Boolean functions

A function of n variables is fixed by its truth table of 2ⁿ rows, each 0 or 1:

A brute-force check over all 256 functions of 3 variables:

from itertools import product
from math import comb

n = 3
rows = list(product([0, 1], repeat=n))
self_dual = neutral = symmetric = 0
for code in range(2 ** 2 ** n):
    f = {row: (code >> i) & 1 for i, row in enumerate(rows)}
    if all(f[r] != f[tuple(1 - x for x in r)] for r in rows):
        self_dual += 1
    if sum(f.values()) == 2 ** (n - 1):
        neutral += 1
    if all(f[r] == f[s] for r in rows for s in rows if sum(r) == sum(s)):
        symmetric += 1
print("all:", 2 ** 2 ** n, "self-dual:", self_dual, "neutral:", neutral, "symmetric:", symmetric)
print("formulas:", 2 ** 2 ** (n - 1), comb(2 ** n, 2 ** (n - 1)), 2 ** (n + 1))

all: 256 self-dual: 16 neutral: 70 symmetric: 16
formulas: 16 70 16

Simplifying with the laws

Example: simplify F = A′B + AB + AB′.

• A′B + AB = (A′ + A)B = B, so F = B + AB′.
• B + AB′ = B + A (using X + X′Y = X + Y).
• F = A + B.

Example: AB + A′C + BC = AB + A′C, because BC is the consensus term of AB and A′C (it is covered whenever B = C = 1, by AB if A = 1 and by A′C if A = 0).

Practice questions

ones = {2, 3, 5, 7}
print("ΠM(" + ", ".join(str(i) for i in range(8) if i not in ones) + ")")