Propositional Logic

The Algebra of True and False

Propositional logic is the foundation of mathematical reasoning. A proposition is any statement that is either true or false. We combine propositions using logical connectives:

A tautology is a formula that is true for every assignment of truth values. A contradiction is always false. A satisfiable formula is true for at least one assignment.

De Morgan's Laws are fundamental: $\neg(p \land q) \equiv \neg p \lor \neg q$ $\neg(p \lor q) \equiv \neg p \land \neg q$

# Check De Morgan's first law
def check_tautology(expr):
    for p in [True, False]:
        for q in [True, False]:
            if not expr(p, q):
                return False
    return True

demorgan = lambda p, q: (not (p and q)) == (not p or not q)
print(check_tautology(demorgan))  # True

Your Task

Implement:

• check_tautology(expr) — returns True if the 2-variable boolean function is a tautology
• count_satisfying(expr, n_vars) — returns how many truth assignments satisfy expr