Logic and Proofs

Logic is the language of precise reasoning. In software, it appears everywhere: boolean expressions in code, query conditions in SQL, type system rules in compilers, correctness arguments for algorithms. Understanding the formal underpinning makes you better at all of them.

Propositions

A proposition is a statement that is either true or false — never both, never neither.

• "5 is greater than 3" — True
• "Python is a compiled language" — False
• "This statement is false" — Not a proposition (paradox)

Propositions are usually denoted p, q, r.

Logical Connectives

Truth Tables

Truth tables enumerate all possible input combinations and their outputs.

Implication (p → q):

The only false case: the premise is true but the conclusion is false. "If it rains, the ground is wet" is only violated if it rains and the ground is dry.

In code: if condition: result — the program's contract is violated only when condition is met but result doesn't hold.

Logical Equivalences

Two expressions are logically equivalent (≡) if they have identical truth tables.

De Morgan's Laws — the most important equivalences in programming:

¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q

In code:

# These are equivalent:
not (a and b)    # ≡   not a or not b
not (a or b)     # ≡   not a and not b

This is why !(A && B) becomes !A || !B when you push a negation inward — a transformation compilers and query optimisers use constantly.

Other key equivalences:

Proof Techniques

Direct Proof

Assume the premise is true; derive the conclusion by logical steps.

Claim: if n is even, then n² is even.

Proof: Let n be even. Then n = 2k for some integer k. So n² = (2k)² = 4k² = 2(2k²). This is 2 times an integer, so n² is even. ∎

Proof by Contrapositive

Instead of proving "if p then q," prove the equivalent "if ¬q then ¬p."

Claim: if n² is odd, then n is odd.

Proof by contrapositive: assume n is even (¬q). Then n = 2k, so n² = 4k² = 2(2k²), which is even (¬p). So if n² is odd, n must be odd. ∎

Proof by Contradiction

Assume the conclusion is false; derive a contradiction — showing the assumption must be wrong.

Claim: √2 is irrational.

Proof: Assume √2 = p/q in lowest terms (p, q integers, no common factors). Then 2 = p²/q², so p² = 2q². This means p² is even, so p is even (p = 2k). Then p² = 4k² = 2q², so q² = 2k², meaning q is even. But then p and q are both even — contradicting that p/q is in lowest terms. ∎

Proof by Induction

Used to prove a statement holds for all natural numbers n.

Structure:

1. Base case: prove it holds for n = 0 (or 1).
2. Inductive step: assume it holds for n = k (inductive hypothesis); prove it holds for n = k + 1.

Claim: 1 + 2 + 3 + ... + n = n(n+1)/2

Base case (n = 1): LHS = 1. RHS = 1×2/2 = 1. ✓

Inductive step: assume 1 + 2 + ... + k = k(k+1)/2. Then: 1 + 2 + ... + k + (k+1) = k(k+1)/2 + (k+1) = (k+1)(k/2 + 1) = (k+1)(k+2)/2 ✓

This is how algorithms over recursive data structures are often proved correct — base case is an empty or single-element structure; inductive step shows correctness extends from smaller to larger inputs.

Logical Quantifiers

Universal quantifier (∀): "for all." ∀x, P(x) means P(x) is true for every x.

Existential quantifier (∃): "there exists." ∃x, P(x) means P(x) is true for at least one x.

Negating quantifiers:

¬(∀x, P(x)) ≡ ∃x, ¬P(x)   — "not all" = "some are not"
¬(∃x, P(x)) ≡ ∀x, ¬P(x)   — "none" = "all are not"

In code: to disprove "all elements satisfy condition," find one counterexample. To disprove "some element satisfies condition," show none do.

Key Takeaways

• Propositions are true/false statements; logical connectives combine them.
• Implication p → q is false only when p is true and q is false.
• De Morgan's laws: ¬(p ∧ q) ≡ ¬p ∨ ¬q and ¬(p ∨ q) ≡ ¬p ∧ ¬q — essential for simplifying boolean expressions.
• Proof by contrapositive: proving "¬q → ¬p" is equivalent to proving "p → q."
• Proof by induction: base case + inductive step proves a property holds for all natural numbers.