Skills101

AdvancedDiscrete Mathematics · Lesson 11 of 14 · Updated ·

Boolean Algebra and Propositional Logic — Laws, Truth Tables, SOP and POS Forms, K-Maps and Valid Arguments

The logic lesson used T and F and the symbols ∧, ∨, ¬. Engineers write the same ideas as Boolean algebra: 1 and 0, with + for OR, · for AND and ′ for NOT. This is the maths behind every if condition, every SQL WHERE clause and every logic circuit in a CPU. In this lesson we generate every truth table with Python, so no row is ever missed.

1. From logic to Boolean algebra

LogicBoolean algebraPythonMeaning
p ∧ qp·q (or pq)p and q / p & qAND
p ∨ qp + qp or q / p | qOR
¬pp′not p / 1 - pNOT
T, F1, 0True, Falsevalues

Careful: in Boolean algebra 1 + 1 = 1 (true OR true is true). It is not ordinary arithmetic.

2. The laws, checked by brute force

LawOR formAND form (the dual)
Identityx + 0 = xx · 1 = x
Null (domination)x + 1 = 1x · 0 = 0
Idempotentx + x = xx · x = x
Complementx + x′ = 1x · x′ = 0
Involution(x′)′ = x
Absorptionx + xy = xx(x + y) = x
Distributivex(y + z) = xy + xzx + yz = (x + y)(x + z)
De Morgan(x + y)′ = x′y′(xy)′ = x′ + y′

The second distributive law, x + yz = (x + y)(x + z), is false for ordinary numbers but true in Boolean algebra.

Duality principle: swap + with ·, and 0 with 1, in any true law and you get another true law. That is why the table has two columns.

With only 0 and 1, a law with three variables has just 2³ = 8 cases, so a computer can check every one:

from itertools import product

laws = {
    "x + yz = (x+y)(x+z)": lambda x, y, z: (x | (y & z)) == ((x | y) & (x | z)),
    "x(y + z) = xy + xz":  lambda x, y, z: (x & (y | z)) == ((x & y) | (x & z)),
    "x + xy = x":          lambda x, y, z: (x | (x & y)) == x,
    "(x + y)' = x'y'":     lambda x, y, z: (1 - (x | y)) == ((1 - x) & (1 - y)),
    "x + y = x + y + xy":  lambda x, y, z: (x | y) == (x | y | (x & y)),
    "x + y' = (x + y)'":   lambda x, y, z: (x | (1 - y)) == (1 - (x | y)),
}
for name, law in laws.items():
    bad = [c for c in product([0, 1], repeat=3) if not law(*c)]
    print(f"{name:22} {'holds' if not bad else 'FALSE, e.g. x,y,z = ' + str(bad[0])}")
x + yz = (x+y)(x+z)    holds
x(y + z) = xy + xz     holds
x + xy = x             holds
(x + y)' = x'y'        holds
x + y = x + y + xy     holds
x + y' = (x + y)'      FALSE, e.g. x,y,z = (1, 0, 0)

The last line is a made-up "law". Brute force finds a counterexample at once — a habit worth keeping when you simplify expressions by hand.

3. Truth tables in Python

A small function prints the table for any expression with any number of variables:

from itertools import product

def truth_table(f, names):
    print(" ".join(names), "| F")
    rows = []
    for values in product([0, 1], repeat=len(names)):
        out = int(f(*values))
        rows.append(out)
        print(" ".join(map(str, values)), "|", out)
    return rows

# majority of three: 1 when at least two inputs are 1
majority = lambda a, b, c: (a & b) | (b & c) | (a & c)
column = truth_table(majority, ["A", "B", "C"])
A B C | F
0 0 0 | 0
0 0 1 | 0
0 1 0 | 0
0 1 1 | 1
1 0 0 | 0
1 0 1 | 1
1 1 0 | 1
1 1 1 | 1

4. Canonical forms: SOP and POS

Every Boolean function can be written straight from its truth table in two standard ways.

  • A minterm is an AND of all variables (each plain or primed) that is 1 in exactly one row. Row 3 (A B C = 0 1 1) gives the minterm A′BC.
  • Sum of products (SOP): OR together the minterms of the rows where F = 1. Written Σm(…) with the row numbers.
  • A maxterm is an OR of all variables that is 0 in exactly one row. Row 0 (0 0 0) gives A + B + C.
  • Product of sums (POS): AND together the maxterms of the rows where F = 0. Written ΠM(…).
from itertools import product

def canonical(f, names):
    rows = list(product([0, 1], repeat=len(names)))
    ones = [i for i, r in enumerate(rows) if f(*r)]
    zeros = [i for i, r in enumerate(rows) if not f(*r)]
    minterm = lambda r: "".join(n if v else n + "'" for n, v in zip(names, r))
    maxterm = lambda r: "(" + " + ".join(n + "'" if v else n for n, v in zip(names, r)) + ")"
    print("SOP: F = Σm" + str(tuple(ones)), "=", " + ".join(minterm(rows[i]) for i in ones))
    print("POS: F = ΠM" + str(tuple(zeros)), "=", "".join(maxterm(rows[i]) for i in zeros))

canonical(lambda a, b, c: (a & b) | (b & c) | (a & c), ["A", "B", "C"])
SOP: F = Σm(3, 5, 6, 7) = A'BC + AB'C + ABC' + ABC
POS: F = ΠM(0, 1, 2, 4) = (A + B + C)(A + B + C')(A + B' + C)(A' + B + C)

The two lists of row numbers always split the rows between them: every row is either a 1 (a minterm) or a 0 (a maxterm). Canonical forms are correct but long. The next step is to simplify them.

5. Simplifying with a Karnaugh map

A Karnaugh map (K-map) arranges the truth table so that neighbouring cells differ in exactly one variable. For three variables the columns use the order 00, 01, 11, 10 (a Gray code), not 00, 01, 10, 11.

Problem: simplify F(A, B, C) = Σm(0, 2, 4, 5, 6).

Three-variable K-map for F = sum of minterms 0, 2, 4, 5 and 6: rows are A = 0 and A = 1, columns are BC in Gray-code order 00, 01, 11, 10; a group of four cells in the C = 0 columns gives C prime and a group of two in row A = 1 gives A B prime, so F = C prime plus A B prime

  1. Put a 1 in each listed cell.
  2. Cover all the 1s with the largest possible rectangles of size 1, 2, 4 or 8. The left and right edges of the map wrap around and count as neighbours.
  3. Each group keeps only the variables that stay the same across the whole group.
  • The four cells with C = 0 (columns 00 and 10, both rows) form one group: C′.
  • Cells 4 and 5 (A = 1, B = 0) form a pair: AB′.
  • F = C′ + AB′: two terms instead of five three-letter minterms.

Always check the simplified form against the original:

from itertools import product

minterms = {0, 2, 4, 5, 6}
original = lambda a, b, c: (a * 4 + b * 2 + c) in minterms
simplified = lambda a, b, c: (1 - c) | (a & (1 - b))
print("same on all 8 rows:", all(original(*r) == bool(simplified(*r)) for r in product([0, 1], repeat=3)))
same on all 8 rows: True

6. NAND can build everything

A set of operations is functionally complete if it can express every Boolean function. {AND, OR, NOT} is complete because SOP form uses only those. Remarkably, NAND alone (NOT-AND: (xy)′) is complete too, which is why chips are often built mostly from NAND gates.

Building NOT, AND and OR from NAND gates only: NOT x is x NAND x; AND is NOT of x NAND y; OR is NOT x NAND NOT y by De Morgan's law

from itertools import product

nand = lambda x, y: 1 - (x & y)
NOT = lambda x: nand(x, x)
AND = lambda x, y: NOT(nand(x, y))
OR = lambda x, y: nand(NOT(x), NOT(y))          # De Morgan: (x'y')' = x + y

print("NOT ok:", all(NOT(x) == 1 - x for x in (0, 1)))
print("AND ok:", all(AND(x, y) == (x & y) for x, y in product((0, 1), repeat=2)))
print("OR  ok:", all(OR(x, y) == (x | y) for x, y in product((0, 1), repeat=2)))
NOT ok: True
AND ok: True
OR  ok: True

NOR alone is also complete. AND and OR together, without NOT, are not complete: they can never turn all-0 inputs into a 1.

7. Valid arguments

An argument is a list of premises followed by a conclusion. It is valid if the conclusion is true in every row where all the premises are true. One row with true premises and a false conclusion — a counterexample — makes it invalid.

Example: "If the server is down, the site shows an error. The site does not show an error. So the server is not down." Let s = server down, e = error shown. Premises: s → e, ¬e. Conclusion: ¬s. Is it valid? A truth table answers it:

from itertools import product

imp = lambda a, b: (not a) or b

def check(name, premises, conclusion):
    for p, q in product([True, False], repeat=2):
        if all(f(p, q) for f in premises) and not conclusion(p, q):
            return print(f"{name:26} INVALID, counterexample p={p}, q={q}")
    print(f"{name:26} valid")

check("modus ponens", [lambda p, q: imp(p, q), lambda p, q: p], lambda p, q: q)
check("modus tollens", [lambda p, q: imp(p, q), lambda p, q: not q], lambda p, q: not p)
check("disjunctive syllogism", [lambda p, q: p or q, lambda p, q: not p], lambda p, q: q)
check("affirming the consequent", [lambda p, q: imp(p, q), lambda p, q: q], lambda p, q: p)
check("denying the antecedent", [lambda p, q: imp(p, q), lambda p, q: not p], lambda p, q: not q)
modus ponens               valid
modus tollens              valid
disjunctive syllogism      valid
affirming the consequent   INVALID, counterexample p=False, q=True
denying the antecedent     INVALID, counterexample p=False, q=True

The server argument is modus tollens, so it is valid. The last two are common fallacies. "If it rains the road is wet; the road is wet; so it rained" is affirming the consequent — the road may be wet because a tanker spilled water.

RulePremisesConclusion
Modus ponensp → q, pq
Modus tollensp → q, ¬q¬p
Hypothetical syllogismp → q, q → rp → r
Disjunctive syllogismp ∨ q, ¬pq
Resolutionp ∨ q, ¬p ∨ rq ∨ r

Resolution is the rule SAT solvers and logic programming languages (like Prolog) are built on.

Common mistakes

  • Treating + as ordinary addition: in Boolean algebra 1 + 1 = 1.
  • Using the binary column order 00, 01, 10, 11 in a K-map. It must be Gray code: 00, 01, 11, 10.
  • Forgetting that K-map edges wrap around, and making two small groups where one big group fits.
  • Writing maxterms with the wrong primes: in a maxterm, a variable is primed where its value is 1.
  • Calling an argument valid because the conclusion happens to be true. Validity is about every row where the premises hold.

Quick recap

  • Boolean algebra = logic with 1, 0, +, ·, ′; duality swaps + with · and 0 with 1.
  • Laws include absorption, De Morgan and x + yz = (x + y)(x + z); check any law on all 2ⁿ rows.
  • SOP = Σm of rows where F = 1; POS = ΠM of rows where F = 0.
  • K-maps use Gray-code order; cover 1s with the largest groups of 1, 2, 4, 8 (edges wrap).
  • NAND alone (or NOR alone) is functionally complete.
  • An argument is valid if no row makes all premises true and the conclusion false; affirming the consequent and denying the antecedent are fallacies.

Practice what you learned

📝 Quiz: Boolean Algebra and Logic5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →