Lab 1 · Explore: truth tables, explosions and a famous equivalence

Discrete Mathematics (YMT211) · Fall 2026

This notebook is the playground half of Lab 1. Nothing here is graded: run each cell (Shift+Enter), read the output, change something, run it again. The graded half is truth.py, checked with python check.py.

Where to run it: in your cs50.dev workspace (open the file, pick a Python kernel) or in Google Colab (the Open in Colab button on the lab page).

1 · Every row of a truth table

itertools.product([True, False], repeat=n) produces every assignment of n variables in standard order. It is the single most useful line for this lab.

from itertools import product

for row in product([True, False], repeat=3):
    print(row)

(True, True, True)
(True, True, False)
(True, False, True)
(True, False, False)
(False, True, True)
(False, True, False)
(False, False, True)
(False, False, False)

Let's print a real truth table for $p \to q$, using $\neg p \lor q$ as its definition:

print("p q | p→q")
for p, q in product([True, False], repeat=2):
    print(int(p), int(q), "|", int((not p) or q))

p q | p→q
1 1 | 1
1 0 | 0
0 1 | 1
0 0 | 1

2 · A prettier table with pandas

Engineers look at truth tables as data. A DataFrame gives us colors and columns for free.

import pandas as pd

def table(f, names):
    rows = [dict(zip(names, map(int, r)), result=int(f(*r))) for r in product([True, False], repeat=len(names))]
    return pd.DataFrame(rows)

df = table(lambda p, q, r: ((not p) or q) and r, ["p", "q", "r"])
df.style.map(lambda v: "background-color:#dcf3ea;color:#0e8a63" if v == 1 else "background-color:#fbe3e3;color:#d83a3f")

	p	q	r	result
0	1	1	1	1
1	1	1	0	0
2	1	0	1	0
3	1	0	0	0
4	0	1	1	1
5	0	1	0	0
6	0	0	1	1
7	0	0	0	0

3 · The contrapositive, checked by brute force

A claim about all truth values of two variables has only 4 cases, so the computer can check every one. This is a proof by exhaustion: with finitely many cases, checking them all is a proof.

implies = lambda p, q: (not p) or q

contrapositive = all(implies(p, q) == implies(not q, not p) for p, q in product([True, False], repeat=2))
converse       = all(implies(p, q) == implies(q, p)         for p, q in product([True, False], repeat=2))

print("p → q  ≡  ¬q → ¬p ?", contrapositive)
print("p → q  ≡   q →  p ?", converse)

p → q  ≡  ¬q → ¬p ? True
p → q  ≡   q →  p ? False

Which rows break the converse? Let's find the counterexamples:

for p, q in product([True, False], repeat=2):
    if implies(p, q) != implies(q, p):
        print(f"counterexample: p={p}, q={q}   p→q={implies(p, q)}, q→p={implies(q, p)}")

counterexample: p=True, q=False   p→q=False, q→p=True
counterexample: p=False, q=True   p→q=True, q→p=False

4 · The explosion: $2^n$ rows

Each new variable doubles the table. Let's time a brute-force tautology check as $n$ grows.

import time
import matplotlib.pyplot as plt

ns, secs = [], []
for n in range(4, 22, 2):
    f = lambda *v: any(v) or not any(v)          # a tautology, so we must check every row
    t0 = time.perf_counter()
    all(f(*row) for row in product([True, False], repeat=n))
    ns.append(n); secs.append(time.perf_counter() - t0)

fig, ax = plt.subplots(figsize=(7, 3.5))
ax.plot(ns, secs, "o-", color="#3a39d0")
ax.set_xlabel("number of variables n"); ax.set_ylabel("seconds"); ax.set_title("Brute-force tautology check: time doubles with every variable")
ax.grid(alpha=.3); plt.tight_layout(); plt.show()

for n in [10, 20, 40, 64, 300]:
    rows = 2 ** n
    print(f"n = {n:>3}: 2^n = {rows:.3e} rows")
print("atoms in the observable universe ≈ 1e80")

n =  10: 2^n = 1.024e+03 rows
n =  20: 2^n = 1.049e+06 rows
n =  40: 2^n = 1.100e+12 rows
n =  64: 2^n = 1.845e+19 rows
n = 300: 2^n = 2.037e+90 rows
atoms in the observable universe ≈ 1e80

Think: if checking one row took a nanosecond, how long would $n = 64$ take? (Hint: about 585 years.) This is why SAT solvers are clever searches, not truth tables. We meet them in week 3.

5 · How many different truth tables exist?

A truth table with $n$ variables has $2^n$ rows, and each row can end in 0 or 1. So there are $2^{2^n}$ different Boolean functions of $n$ variables. For $n = 2$ that is 16: our five connectives are just a few of them.

for n in range(1, 6):
    print(f"n = {n}: {2 ** n:>2} rows, {2 ** (2 ** n):,} different Boolean functions")

n = 1:  2 rows, 4 different Boolean functions
n = 2:  4 rows, 16 different Boolean functions
n = 3:  8 rows, 256 different Boolean functions
n = 4: 16 rows, 65,536 different Boolean functions
n = 5: 32 rows, 4,294,967,296 different Boolean functions

6 · Logic on bits

Python's &, |, ^ and ~ apply the connectives to every bit of an integer at once.

a, b = 0b0110_1100, 0b1010_1010
for name, v in [("a", a), ("b", b), ("a & b", a & b), ("a | b", a | b), ("a ^ b", a ^ b)]:
    print(f"{name:>6} = {v:08b}")

     a = 01101100
     b = 10101010
 a & b = 00101000
 a | b = 11101110
 a ^ b = 11000110

A classic trick: XOR swaps two variables without a temporary, because $x \oplus y \oplus y = x$.

x, y = 0b1010, 0b0110
x ^= y; y ^= x; x ^= y
print(f"x = {x:04b}, y = {y:04b}")

x = 0110, y = 1010

7 · Connect to your lab

Once your truth.py passes some checks, import it here and play with your own engine. (This cell only works inside your lab repository, next to truth.py.)

from truth import format_table, is_tautology, implies, iff

print(format_table(lambda p, q: implies(p, q), ["p", "q"], "p→q"))
print("De Morgan is a tautology:", is_tautology(lambda p, q: iff(not (p and q), (not p) or (not q)), 2))

Your turn

1. Use table(...) from section 2 to print the truth table of $(p \oplus q) \leftrightarrow \neg(p \leftrightarrow q)$. What kind of formula is it?
2. Find all counterexamples to "$p \to (q \to r)$ is equivalent to $(p \to q) \to r$".
3. Change the timing loop in section 4 to go up to $n = 24$. Estimate from the plot how long $n = 30$ would take, then check your guess.