Module 04: Mathematical foundations

A proposition is a statement with a truth value. Negation flips it; conjunction requires both inputs; disjunction requires at least one. Implication p→q means not p or q: it is false only when p is true and q is false. This models a promise: when the precondition holds, the postcondition must hold. It is not a claim that p causes q. Quantifiers extend statements: every record has an ID differs from some record has an ID. Negating ∀x P(x) gives ∃x not P(x); one counterexample defeats a universal claim.

A set contains distinct elements without positional order. Union collects elements in either set; intersection keeps elements in both; difference A−B keeps elements only in A. A relation is a set of ordered pairs: borrowed_by can relate a book ID to a member ID. Reflexive means each element relates to itself; symmetric means each related pair reverses; transitive means xRy and yRz imply xRz. Equality has all three properties. A directed dependency relation need not be symmetric.

A function maps each domain element to exactly one codomain element. Injective means distinct inputs have distinct outputs; surjective means every codomain element is reached; bijective means both. If an ID-to-record function is injective, no two IDs map to the same record under that model. A pair of independent choices with a and b possibilities has a×b combinations. This counts configurations, not probabilities unless outcomes are equally likely. Mapping more than k objects into k buckets forces at least one shared bucket: the pigeonhole principle explains why hash collisions cannot always be avoided.

A direct proof starts from assumptions and derives the claim. A counterexample disproves a universal statement. Induction proves a statement indexed by nonnegative integers: establish a base case, then prove that assuming it at k implies it at k+1. For 1+…+n=n(n+1)/2, n=0 gives zero. Add k+1 to k(k+1)/2 to obtain (k+1)(k+2)/2. Checking ten values is useful debugging but does not replace that step for infinitely many n. Loop invariants use a related initialisation-and-preservation structure.

A finite sample space lists outcomes. For equally likely outcomes, P(A)=|A|/|Ω|. Conditional probability restricts attention to B: P(A|B)=P(A∩B)/P(B), requiring P(B)>0. Independence means P(A∩B)=P(A)P(B); it is not the same as disjointness. Expected value weights values by probabilities. A fair die has expected value 3.5 even though no roll is 3.5. Linearity gives E[X+Y]=E[X]+E[Y] without requiring independence; other identities, such as multiplying expectations, do require additional assumptions.

Download each script and run it in a terminal with Python 3.11 or later: python m04_logic.py. On Windows, py -3 is an alternative; on some systems use python3. The labs use only the standard library. Predict the result before running, then complete the variations. Run without -O so assertions remain enabled. Outputs below were captured by the builder. Code and output are identical in both language editions.

Enumerate all four Boolean input pairs. The code checks implication against its contrapositive and verifies De Morgan's law.

Download m04_logic.py

"""Enumerate finite cases to check logical equivalence and set operations."""
from itertools import product
for p, q in product([False, True], repeat=2):
    implication = (not p) or q
    contrapositive = q or (not p)  # (not q) implies (not p)
    assert implication == contrapositive
    assert (not (p and q)) == ((not p) or (not q))
    print(int(p), int(q), "implies:", int(implication))
available = {1, 2, 3}
requested = {2, 3, 4}
print("intersection:", sorted(available & requested))
print("union:", sorted(available | requested))
print("missing:", sorted(requested - available))

0 0 implies: 1
0 1 implies: 1
1 0 implies: 0
1 1 implies: 1
intersection: [2, 3]
union: [1, 2, 3, 4]
missing: [4]

1. Replace the contrapositive with q→p and find a counterexample.
2. Add symmetric difference for the sets.

Two labelled dice have 36 equally likely ordered outcomes. Fractions avoids float approximation.

Download m04_probability.py

"""Exact finite probability, conditional probability and a summation identity."""
from fractions import Fraction
outcomes = [(a, b) for a in range(1, 7) for b in range(1, 7)]
event = [(a, b) for a, b in outcomes if a + b == 7]
condition = [(a, b) for a, b in outcomes if a == 1]
joint = [x for x in condition if sum(x) == 7]
print("P(sum=7):", Fraction(len(event), len(outcomes)))
print("P(sum=7 | first=1):", Fraction(len(joint), len(condition)))
for n in [0, 1, 5, 10]:
    total = sum(range(1, n + 1))
    assert total == n * (n + 1) // 2
    print("n:", n, "sum:", total)

P(sum=7): 1/6
P(sum=7 | first=1): 1/6
n: 0 sum: 0
n: 1 sum: 1
n: 5 sum: 15
n: 10 sum: 55

1. Compute P(sum=8) and P(sum=8 | first=1).
2. Change the summation endpoint to exclude n; find a failing case.

Try before opening the solution. ★ applies an idea; ★★ combines ideas; ★★★ asks for design or proof.

Choose an answer for feedback; reset to retry. A text answer key is available without JavaScript.

• MIT Mathematics for Computer Science — Read the opening proof and induction chapters; identify assumptions in one proof.

Explain why tests and proofs provide different evidence. Write one invariant for catalogue counting. Module 05 uses these tools to analyse search and sorting.