📋 Changes in this PR: State Machines and Finite Automata, Calendar, Contrapositive and Contradiction, Inference and Direct Proof, Logical Equivalence and Negation, Functional Programming, Graphs, Proving Non-Conditional Statements, Mathematical Induction, Loop Invariants, Predicates and Quantifiers, Propositional Logic, Recurrence Relations and Growth Rates, Recursion, Relations, Proofs with Sets, Sets, WWU CSCI 201 Syllabus, Trees, Expressions and Algorithms, Functions, Growth Rates, Math for Computer Science, Induction and Recursion, Notation, Number Systems, Proof Writing, Relations, Sets
💡 Tip: If change highlighting is glitchy, add the no-preview-highlights label to this PR to disable it.
Adapted from Kameron Decker Harris’s Fall 2026 lecture notes “Logic 4, Proofs Intro, Direct Proof”, which are typed transcriptions of Scott Wehrwein’s Spring 2025 handwritten lecture notes. The rules of inference, the definition of “divides”, the observation that a definition’s “if” means “if and only if”, the template for a direct proof, and the ideas of proof by cases and “without loss of generality” come from those notes; the exercises are new.
The definitions of logical entailment and proof are on the proof writing page, and those of the integers and of even and odd integers are on the number systems page. The other data science notes link to both pages.
Rules of inference
Exercise 1 (Which conclusions are safe?) Let \(P\) be “the tests pass”, \(Q\) be “the build is deployed” and \(R\) be “the build is rolled back”. Each argument below lists some propositions, then “so”, then one more proposition. For each argument, decide whether the proposition after “so” must be true whenever all of the propositions before it are true.
- \(P \Rightarrow Q\) and \(P\), so \(Q\).
- \(P \Rightarrow Q\) and \(Q\), so \(P\).
- \(P \Rightarrow Q\) and \(\neg Q\), so \(\neg P\).
- \(P \lor R\) and \(\neg R\), so \(P\).
Solution 1.
- Yes. \(P \Rightarrow Q\) is false when \(P\) is true and \(Q\) is false (Definition: Implies), so if \(P \Rightarrow Q\) and \(P\) are both true, \(Q\) is true.
- No. If the tests fail but someone deploys the build by hand, \(P\) is false and \(Q\) is true. Then \(P \Rightarrow Q\) and \(Q\) are both true, and \(P\) is false.
- Yes. \(\neg Q\) is true, so \(Q\) is false (Definition: Not). If \(P\) were true, \(P \Rightarrow Q\) would be false, so \(P\) is false and \(\neg P\) is true.
- Yes. \(\neg R\) is true, so \(R\) is false (Definition: Not). \(P \lor R\) is true only if \(P\) or \(R\) is true (Definition: Or), so \(P\) is true.
Definition 1 (Logical argument) A logical argument is a list of propositions \(P_1, \ldots, P_n\) together with one more proposition \(Q\). It is written with “so” or \(\therefore\) before \(Q\).
Definition 2 (Logical entailment, logical consequence, deductive consequence) Propositions or predicates \(P_1, \ldots, P_n\) (Definition: Proposition, statement, Definition: Predicate) logically entail (Wikipedia contributors 2026c) a proposition or predicate \(Q\) when every choice of values for their variables that makes all of \(P_1, \ldots, P_n\) true also makes \(Q\) true. Then \(Q\) is a logical consequence, or deductive consequence, of \(P_1, \ldots, P_n\).
Example 1 (Entailment in the deployment arguments) In Exercise 1, the premises of arguments 1, 3 and 4 logically entail their conclusions (Definition 2). The premises of argument 2 do not: the values \(P\) false and \(Q\) true make both premises true and the conclusion false.
Definition 3 (Rule of inference) A rule of inference is a pattern of logical argument, written with propositions \(P, Q, \ldots\) as placeholders, whose premises logically entail its conclusion whatever propositions are put in place of \(P, Q, \ldots\). It is written with its premises above a line and its conclusion below:
\[
\frac{P_1, \ldots, P_n}{Q}.
\]
Example 2 (Modus ponens) Argument 1 of Exercise 1 follows the pattern \[
\frac{P \Rightarrow Q, \quad P}{Q},
\] called modus ponens. It is a rule of inference (Definition 3): by Solution 1, its premises entail its conclusion for any propositions \(P\) and \(Q\), not only for tests and builds.
Theorem 1 (Common rules of inference) For propositions \(P\) and \(Q\), each of the following is a rule of inference (Definition 3):
- modus ponens: \[
\frac{P \Rightarrow Q, \quad P}{Q}
\]
- modus tollens: \[
\frac{P \Rightarrow Q, \quad \neg Q}{\neg P}
\]
- disjunctive syllogism: \[
\frac{P \lor Q, \quad \neg P}{Q}
\]
- simplification: \[
\frac{P \land Q}{P}
\]
- conjunction: \[
\frac{P, \quad Q}{P \land Q}
\]
- addition: \[
\frac{P}{P \lor Q}
\]
Proof. For each rule, suppose every premise is true, and show that the conclusion is true.
- \(P \Rightarrow Q\) is false when \(P\) is true and \(Q\) is false (Definition: Implies). \(P\) is true and \(P \Rightarrow Q\) is true, so \(Q\) is not false.
- \(\neg Q\) is true, so \(Q\) is false (Definition: Not). If \(P\) were true, \(P \Rightarrow Q\) would be false, so \(P\) is false and \(\neg P\) is true.
- \(\neg P\) is true, so \(P\) is false. \(P \lor Q\) is true only if \(P\) or \(Q\) is true (Definition: Or), so \(Q\) is true.
- \(P \land Q\) is true only if both \(P\) and \(Q\) are true (Definition: And), so \(P\) is true.
- \(P\) and \(Q\) are both true, so \(P \land Q\) is true (Definition: And).
- \(P\) is true, so \(P \lor Q\) is true (Definition: Or).
Example 3 (Modus tollens on a slow page) “If the cache is warm, then the page loads in under a second” and “the page did not load in under a second” together give “the cache is not warm”, by modus tollens (Theorem 1).
Even, odd and divisible
Exercise 2 (Two times something, plus maybe one) Write each of \(14\), \(15\), \(-7\) and \(0\) as \(2k\) or as \(2k + 1\), for an integer \(k\).
Solution 2.
- \(14 = 2 \cdot 7\).
- \(15 = 2 \cdot 7 + 1\).
- \(-7 = 2 \cdot (-4) + 1\).
- \(0 = 2 \cdot 0\).
Definition 4 (Integers) The integers (Wikipedia contributors 2026b) are the whole numbers, together with their negatives and \(0\):
\[\mathbb{Z} \stackrel{\text{def}}{=}\mathopen{}\left\{\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots\right\}\mathclose{}\]
An integer is an element of \(\mathbb{Z}\).
Definition 5 (Positive integers) The integers (Definition 4) greater than \(0\) are the positive integers.
Definition 6 (Negative integers) The integers (Definition 4) less than \(0\) are the negative integers.
Example 4 (Integers and non-integers)
- \(-7\), \(0\), and \(12\) are integers.
- \(\frac{1}{2}\) and \(-2.5\) are not integers.
- \(\frac{6}{3}\) is an integer, because \(\frac{6}{3} = 2\).
Example 5 (Even and odd integers)
- \(6\) is even, because \(6 = 2 \cdot 3\).
- \(0\) is even, because \(0 = 2 \cdot 0\).
- \(-3\) is odd, because \(-3 = 2 \cdot(-2) + 1\).
- \(7\) is odd, because \(7 = 2 \cdot 3 + 1\).
- \(2.5\) is neither even nor odd, because it is not an integer.
Definition 9 (Divides) Let \(a\) and \(b\) each be an integer. We say that \(a\) divides \(b\), written \(a \mid b\), if \(b = a c\) for some integer \(c\). When \(a\) does not divide \(b\), we write \(a \nmid b\).
Example 6 (Divisors)
- \(3 \mid 12\), because \(12 = 3 \cdot 4\).
- \(-2 \mid 6\), because \(6 = (-2) \cdot (-3)\).
- \(3 \nmid 13\): \(3 c\) increases with \(c\), \(3 \cdot 4 = 12\) and \(3 \cdot 5 = 15\), and there is no integer between \(4\) and \(5\), so no integer \(c\) gives \(3 c = 13\).
- Every integer \(a\) divides \(0\), because \(0 = a \cdot 0\).
- \(0\) divides only \(0\), because \(0 \cdot c = 0\) for every integer \(c\).
Direct proof
Exercise 3 (An odd input) Show that if \(n\) is an odd integer, then \(3 n + 5\) is even.
Solution 3. Suppose \(n\) is an odd integer. By Definition 8, \(n = 2 k + 1\) for some integer \(k\). Then \[
3 n + 5 = 3 (2 k + 1) + 5 = 6 k + 3 + 5 = 6 k + 8 = 2 (3 k + 4).
\] Since \(3 k + 4\) is an integer (Remark 3), \(3 n + 5\) is even, by Definition 7.
Definition 10 (Proof) A proof (Wikipedia contributors 2026d) of a proposition (Definition: Proposition, statement) is a finite list of statements that ends with that proposition, in which each statement is
- an assumption,
- a definition,
- a previously proved result, or
- a consequence of earlier statements in the list, by one rule of logic or algebra.
Example 7 (A proof, statement by statement) Solution 3 is a proof (Definition 10) of “\(3 n + 5\) is even” in which “\(n\) is an odd integer” is an assumption. Its statements are:
- the assumption: \(n\) is an odd integer;
- a definition: \(n = 2 k + 1\) for some integer \(k\), by Definition 8;
- consequences by algebra: \(3 n + 5 = 6 k + 8 = 2 (3 k + 4)\);
- a definition: \(3 n + 5\) is even, by Definition 7, since \(3 k + 4\) is an integer.
Definition 11 (Direct proof) A direct proof (Wikipedia contributors 2026a) of a proposition \(Q\) starts from the assumptions that \(Q\) is stated under, if any, and reaches \(Q\) through a chain of steps, each of which applies a definition, a previously proved result, or one rule of logic or algebra to the assumptions or to earlier steps. A direct proof never assumes that \(Q\) is false; compare proof by contradiction, which does.
Example 8 (A direct proof) Solution 3 is a direct proof (Definition 11) of “if \(n\) is an odd integer, then \(3 n + 5\) is even”: it assumes \(P\), “\(n\) is an odd integer”, and ends with \(Q\), “\(3 n + 5\) is even”.
Exercise 4 (Divisors of divisors) Let \(a\), \(b\) and \(c\) be integers. Prove that if \(a \mid b\) and \(b \mid c\), then \(a \mid c\).
Solution 4. Suppose \(a \mid b\) and \(b \mid c\). By Definition 9, \(b = a j\) and \(c = b k\) for some integers \(j\) and \(k\). Then \[
c = b k = (a j) k = a (j k).
\] Since \(j k\) is an integer (Remark 3), \(a \mid c\), by Definition 9.
Proof by cases
Exercise 5 (Even for every integer) Prove that \(n^2 + n\) is even for every integer \(n\).
Every integer is even or odd (Remark 3). Handle the two kinds separately.
Solution 5. Let \(n\) be an integer. Every integer is even or odd (Remark 3), so one of these cases holds.
Case 1: \(n\) is even. By Definition 7, \(n = 2 k\) for some integer \(k\), and \[
n^2 + n = (2 k)^2 + 2 k = 4 k^2 + 2 k = 2 (2 k^2 + k).
\]
Case 2: \(n\) is odd. By Definition 8, \(n = 2 k + 1\) for some integer \(k\), and \[
n^2 + n = (2 k + 1)^2 + (2 k + 1) = (4 k^2 + 4 k + 1) + (2 k + 1) = 4 k^2 + 6 k + 2 = 2 (2 k^2 + 3 k + 1).
\]
In each case, \(n^2 + n\) is \(2\) times an integer (Remark 3), so \(n^2 + n\) is even, by Definition 7.
Definition 12 (Proof by cases, proof by exhaustion) A proof by cases (Wikipedia contributors 2026f), also called a proof by exhaustion, of a proposition \(Q\) lists propositions \(C_1, \ldots, C_k\), the cases, shows that at least one of them is true, and proves \(C_i \Rightarrow Q\) for each \(i\).
Exercise 6 (Larger plus smaller) For real numbers \(x\) and \(y\), let \(\max(x, y)\) be the larger of \(x\) and \(y\) and \(\min(x, y)\) the smaller (both equal \(x\) when \(x = y\)). Prove that \(\max(x, y) + \min(x, y) = x + y\).
Solution 6. Let \(x\) and \(y\) be real numbers. Either \(x \le y\) or \(y \le x\). Both sides of the equation stay the same when \(x\) and \(y\) are swapped, so without loss of generality, suppose \(x \le y\). Then \(\max(x, y) = y\) and \(\min(x, y) = x\), so \[
\max(x, y) + \min(x, y) = y + x = x + y.
\]
Back to top