Propositional and Predicate Logic — Truth Tables, Implications, Equivalences and Quantifiers

Every if statement is logic. So is every database query, every circuit and every security rule. This lesson makes logic precise — and shows how it turns into code.

1. Propositions and connectives

A proposition is a statement that is either true or false: "7 is prime" (T), "2 + 2 = 5" (F).

2. Truth tables

Let Python generate them — no mistakes, any number of variables:

from itertools import product

def table(expr, names):
    print(" ".join(names), "| result")
    for values in product([True, False], repeat=len(names)):
        env = dict(zip(names, values))
        row = " ".join("T" if v else "F" for v in values)
        print(row, "|", "T" if expr(**env) else "F")

print("p -> q")
table(lambda p, q: (not p) or q, ["p", "q"])

p -> q
p q | result
T T | T
T F | F
F T | T
F F | T

3. Understanding implication

p → q ("if p then q") is a promise. It's broken only when p happens and q doesn't.

"If you score 90+, you get a scholarship." You scored 85 and got a scholarship anyway — the promise isn't broken (p false ⇒ implication true).

Check by brute force:

from itertools import product

implies = lambda a, b: (not a) or b
rows = list(product([True, False], repeat=2))
print("p->q == contrapositive:", all(implies(p, q) == implies(not q, not p) for p, q in rows))
print("p->q == converse      :", all(implies(p, q) == implies(q, p) for p, q in rows))
print("p->q == not p or q    :", all(implies(p, q) == ((not p) or q) for p, q in rows))

p->q == contrapositive: True
p->q == converse      : False
p->q == not p or q    : True

4. Tautology, contradiction, contingency

• Tautology: true in every row — e.g. p ∨ ¬p.
• Contradiction: false in every row — e.g. p ∧ ¬p.
• Contingency: sometimes true, sometimes false.
• Two formulas are logically equivalent (≡) if their biconditional is a tautology.

from itertools import product

def kind(expr, n):
    vals = [expr(*v) for v in product([True, False], repeat=n)]
    return "tautology" if all(vals) else "contradiction" if not any(vals) else "contingency"

print("p or not p           :", kind(lambda p: p or not p, 1))
print("p and not p          :", kind(lambda p: p and not p, 1))
print("(p->q) and p -> q    :", kind(lambda p, q: (not (((not p) or q) and p)) or q, 2))
print("p -> (p and q)       :", kind(lambda p, q: (not p) or (p and q), 2))

p or not p           : tautology
p and not p          : contradiction
(p->q) and p -> q    : tautology
p -> (p and q)       : contingency

The third one is modus ponens ("if p then q; p; therefore q") — a tautology, which is why it's a valid rule of reasoning.

5. Laws you'll use constantly

De Morgan in code — simplifying a condition:

# "not (has_paid and is_verified)" is the same as "not has_paid or not is_verified"
from itertools import product
print(all((not (a and b)) == ((not a) or (not b)) for a, b in product([True, False], repeat=2)))

True

6. Predicates and quantifiers

A predicate has variables: P(x) = "x is prime". It becomes a proposition when x is given or quantified:

• ∀x P(x) — "for all x, P(x)" — like Python all(...)
• ∃x P(x) — "there exists x with P(x)" — like any(...)

Negating quantifiers (the exam trap):

• ¬∀x P(x) ≡ ∃x ¬P(x) — "not all are prime" = "some is not prime"
• ¬∃x P(x) ≡ ∀x ¬P(x) — "none is prime" = "all are non-prime"

marks = [72, 45, 88, 91, 39]
passed = lambda m: m >= 40

print("everyone passed (∀)       :", all(passed(m) for m in marks))
print("someone failed  (∃ not)   :", any(not passed(m) for m in marks))
print("negation law holds        :", (not all(passed(m) for m in marks)) == any(not passed(m) for m in marks))

everyone passed (∀)       : False
someone failed  (∃ not)   : True
negation law holds        : True

Nested quantifiers — order matters: ∀x ∃y (y > x) "for every number there's a bigger one" is true on integers; ∃y ∀x (y > x) "there's a number bigger than all numbers" is false.

Common mistakes

• Thinking p → q is false when p is false.
• Confusing converse with contrapositive.
• Negating "all students passed" as "all students failed" (correct: "some student failed").
• Swapping the order of nested quantifiers.

Quick recap

• Connectives: ¬, ∧, ∨, ⊕, →, ↔; p → q ≡ ¬p ∨ q (false only for T → F).
• Contrapositive ≡ original; converse and inverse are not.
• Tautology / contradiction / contingency; use truth tables (or Python) to check.
• De Morgan: ¬(p ∧ q) ≡ ¬p ∨ ¬q.
• ∀ ↔ all, ∃ ↔ any; ¬∀ = ∃¬, ¬∃ = ∀¬; quantifier order matters.