Logic and proof basics

A proposition is a statement that is either true or false: “7 is prime” is true, “x > 3” is a proposition only once x has a value. In code a proposition is a boolean expression. Connectives combine them: AND (∧, &&), OR (∨, ||), NOT (¬, !), and the implication p → q.

Preconditions, loop conditions and invariants are all propositions about program state.

Boolean algebra gives rewrite rules: De Morgan's laws ¬(p ∧ q) = ¬p ∨ ¬q and ¬(p ∨ q) = ¬p ∧ ¬q, distribution p ∧ (q ∨ r) = (p ∧ q) ∨ (p ∧ r), absorption p ∨ (p ∧ q) = p, and double negation ¬¬p = p. They simplify conditions and negate them correctly.

Pick De Morgan's expressions in the truth-table tool and compare the two columns.

1// !(a && b) == (!a || !b)
2boolean ok = true;
3for (boolean a : new boolean[]{false, true})
4    for (boolean b : new boolean[]{false, true})
5        ok &= !(a && b) == (!a || !b);   // stays true for all four rows

1// every row of a truth table is one assignment of true/false to the variables
2for (int mask = 0; mask < (1 << vars); mask++) {
3    boolean A = (mask & 4) != 0, B = (mask & 2) != 0, C = (mask & 1) != 0;
4    boolean result = expression(A, B, C);          // implication: !A || B
5    print(A, B, C, result);
6}
7// 2 variables -> 4 rows, 3 variables -> 8 rows: 2^n rows in general

A truth table lists every combination of input values and the resulting value. With n variables there are 2ⁿ rows. Two expressions are equivalent exactly when their columns match in every row. The tool below builds the table for a chosen expression.

For small n this is a complete proof by exhaustion.

1// every row of a truth table is one assignment of true/false to the variables
2for (int mask = 0; mask < (1 << vars); mask++) {
3    boolean A = (mask & 4) != 0, B = (mask & 2) != 0, C = (mask & 1) != 0;
4    boolean result = expression(A, B, C);          // implication: !A || B
5    print(A, B, C, result);
6}
7// 2 variables -> 4 rows, 3 variables -> 8 rows: 2^n rows in general

∀x P(x) says P holds for every x; ∃x P(x) says it holds for at least one. Negation swaps them: ¬∀x P(x) = ∃x ¬P(x), and ¬∃x P(x) = ∀x ¬P(x). In Java, allMatch is ∀ and anyMatch is ∃.

Note that ∀ over an empty collection is true (vacuously) and ∃ over an empty collection is false.

1int[] a = {2, 4, 6};
2boolean allEven = Arrays.stream(a).allMatch(x -> x % 2 == 0);   // true
3boolean someOdd = Arrays.stream(a).anyMatch(x -> x % 2 != 0);   // false
4boolean notAllEven = Arrays.stream(a).anyMatch(x -> x % 2 != 0);  // negation: some odd
5boolean vacuous = Arrays.stream(new int[0]).allMatch(x -> false);   // true

p → q (“if p then q”) is false only when p is true and q is false. When p is false the implication is true regardless of q. It equals ¬p ∨ q. Think of it as a promise: it is only broken if the condition holds and the result does not.

Compare p → q with ¬p ∨ q in the table tool.

1static boolean implies(boolean p, boolean q) { return !p || q; }
2// "if the array is sorted then binary search finds the key"
3// implies(false, anything) is true: nothing is promised for unsorted input

1// every row of a truth table is one assignment of true/false to the variables
2for (int mask = 0; mask < (1 << vars); mask++) {
3    boolean A = (mask & 4) != 0, B = (mask & 2) != 0, C = (mask & 1) != 0;
4    boolean result = expression(A, B, C);          // implication: !A || B
5    print(A, B, C, result);
6}
7// 2 variables -> 4 rows, 3 variables -> 8 rows: 2^n rows in general

The contrapositive of p → q is ¬q → ¬p, and it is logically equivalent to the original. Often it is easier to prove. The converse q → p and the inverse ¬p → ¬q are not equivalent to the original.

Example: “if n² is even then n is even” is easiest to prove through its contrapositive “if n is odd then n² is odd”: (2k + 1)² = 4k² + 4k + 1 is odd.

1// every row of a truth table is one assignment of true/false to the variables
2for (int mask = 0; mask < (1 << vars); mask++) {
3    boolean A = (mask & 4) != 0, B = (mask & 2) != 0, C = (mask & 1) != 0;
4    boolean result = expression(A, B, C);          // implication: !A || B
5    print(A, B, C, result);
6}
7// 2 variables -> 4 rows, 3 variables -> 8 rows: 2^n rows in general

To prove P by contradiction, assume ¬P and derive something impossible. Classic example: there is no largest prime. Suppose p is the largest and form N = (product of all primes) + 1. N leaves remainder 1 for every prime, so it has a prime factor not in the list, a contradiction.

In algorithms: “assume a faster comparison sort existed” leads to the Ω(n log n) lower bound argument.

Induction proves a statement P(n) for all n ≥ n₀: show the base case P(n₀), then show that P(k) implies P(k + 1). Example: 1 + 2 + … + n = n(n + 1)/2. Base n = 1: 1 = 1. Step: if the sum to k is k(k + 1)/2 then the sum to k + 1 is k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2.

Induction mirrors recursion: the base case is the base case and the step is the recursive call. It is the standard way to prove a loop invariant or a recursive algorithm correct.

1static long sumTo(int n) { return n == 0 ? 0 : n + sumTo(n - 1); }
2// induction proves sumTo(n) == n * (n + 1) / 2:
3// base: sumTo(0) == 0; step: sumTo(k + 1) = (k + 1) + k(k + 1)/2

Strong induction assumes P holds for all values up to k, not only k itself, and proves P(k + 1). It fits problems that split into several smaller cases, like divide and conquer. Example: every integer n ≥ 2 is a product of primes. If n is prime we are done; otherwise n = ab with 2 ≤ a, b < n, and by hypothesis both are products of primes.

Merge sort's correctness uses it: assuming both halves are sorted (any smaller size), merging yields a sorted whole.