📋 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.
📝 Preview Changes: This page has been modified in this pull request (~1% of content changed).
🎨 Highlighting Legend:
Modified text (yellow) shows changed words/phrases,
added text (green) shows new content, and
new sections (blue) highlight entirely new paragraphs.
Adapted from Kameron Decker Harris’s Fall 2026 lecture notes “Logic 3”, which are typed transcriptions of Scott Wehrwein’s Spring 2025 handwritten lecture notes. The truth table for the distributive law of “and” over “or” comes from those notes; the exercises are new.
Logical equivalence
Exercise 1 (A rule with a redundant part) A server grants access to a user who is an administrator, or who is an administrator and is on the office network. Let \(P\) be “the user is an administrator” and \(Q\) be “the user is on the office network”.
Make a truth table for \(P \lor (P \land Q)\). In which rows does it have the same truth value as \(P\)?
Solution 1.
| T |
T |
T |
T |
| T |
F |
F |
T |
| F |
T |
F |
F |
| F |
F |
F |
F |
The last column matches the \(P\) column in every row, so the rule grants access exactly to the administrators, and the part about the office network changes nothing.
Example 1 (An equivalence) By Exercise 1, \(P \lor (P \land Q)\) is logically equivalent to \(P\): the truth table of \(P \lor (P \land Q)\) has the same column as \(P\), in a table with columns for both \(P\) and \(Q\).
Exercise 2 (Not both) A continuous integration server runs two test suites. Let \(P\) be “the unit tests pass” and \(Q\) be “the integration tests pass”.
Is “it is not the case that both suites pass”, \(\neg (P \land Q)\), logically equivalent to “neither suite passes”, \(\neg P \land \neg Q\)?
Solution 2.
| T |
T |
T |
F |
F |
F |
F |
| T |
F |
F |
T |
F |
T |
F |
| F |
T |
F |
T |
T |
F |
F |
| F |
F |
F |
T |
T |
T |
T |
No. The two columns differ in the second and third rows, where exactly one suite passes: then it is true that not both pass, but false that neither passes.
Example 2 (A tautology) \(P \lor \neg P\) is a tautology (Definition 2):
Example 3 (A contradiction) \(P \land \neg P\) is a contradiction (Definition 3):
Proof. By the definition of if and only if, \(A \Leftrightarrow B\) is true in a row of the truth table exactly when \(A\) and \(B\) have the same truth value in that row. So \(A \Leftrightarrow B\) is true in every row exactly when \(A\) and \(B\) have the same truth value in every row, which is the definition of \(A \equiv B\).
Example 4 (An equivalence as a tautology) Since \(P \lor (P \land Q) \equiv P\) (Example 1), Theorem 1 says that \((P \lor (P \land Q)) \Leftrightarrow P\) is a tautology.
Exercise 3 (Does “or” distribute over “and”?) In arithmetic, multiplication distributes over addition: \(a (b + c) = a b + a c\). Use a truth table to decide whether “or” distributes over “and”: is \(A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)\)?
Solution 3.
| T |
T |
T |
T |
T |
T |
T |
T |
| T |
T |
F |
F |
T |
T |
T |
T |
| T |
F |
T |
F |
T |
T |
T |
T |
| T |
F |
F |
F |
T |
T |
T |
T |
| F |
T |
T |
T |
T |
T |
T |
T |
| F |
T |
F |
F |
F |
T |
F |
F |
| F |
F |
T |
F |
F |
F |
T |
F |
| F |
F |
F |
F |
F |
F |
F |
F |
Yes: the fifth and last columns match in every row. Addition does not distribute over multiplication in arithmetic: \(1 + 2 \cdot 3 = 7\), but \((1 + 2)(1 + 3) = 12\). But “or” distributes over “and”.
Theorem 2 (Distributive laws for propositions) For propositions \(A\), \(B\) and \(C\):
\[
\begin{aligned}
A \land (B \lor C) &\equiv (A \land B) \lor (A \land C) \\
A \lor (B \land C) &\equiv (A \lor B) \land (A \lor C)
\end{aligned}
\]
Proof. By the definitions of and and or, the truth table for the first law is:
| T |
T |
T |
T |
T |
| T |
T |
F |
T |
T |
| T |
F |
T |
T |
T |
| T |
F |
F |
F |
F |
| F |
T |
T |
F |
F |
| F |
T |
F |
F |
F |
| F |
F |
T |
F |
F |
| F |
F |
F |
F |
F |
and for the second law:
| T |
T |
T |
T |
T |
| T |
T |
F |
T |
T |
| T |
F |
T |
T |
T |
| T |
F |
F |
T |
T |
| F |
T |
T |
T |
T |
| F |
T |
F |
F |
F |
| F |
F |
T |
F |
F |
| F |
F |
F |
F |
F |
In each table the last two columns match in every row, so each law is a logical equivalence.
Example 5 (Distributing “and”) For an integer \(x\), “\(x\) is even, and \(x > 0\) or \(x < 0\)” is logically equivalent, by law 1 of Theorem 2, to “\(x\) is even and \(x > 0\), or \(x\) is even and \(x < 0\)”.
Negation
Exercise 4 (When is the door locked?) A door opens when the badge is valid, the PIN is correct, and it is a weekday. Let \(B\) be “the badge is valid”, \(N\) be “the PIN is correct” and \(W\) be “it is a weekday”, so the door stays locked when \(\neg (B \land N \land W)\) is true.
Describe when the door stays locked with a sentence that puts “not” only in front of \(B\), \(N\) or \(W\), never in front of a compound proposition.
Solution 4. The door stays locked when the badge is not valid, the PIN is not correct, or it is not a weekday: \(\neg B \lor \neg N \lor \neg W\). \(B \land N \land W\) is false exactly when at least one of \(B\), \(N\) and \(W\) is false.
Theorem 3 (Double negation) For a proposition \(P\),
\[
\neg \neg P \equiv P.
\]
Example 6 (Not unreadable) “It is not the case that the file is not readable” means “the file is readable” (Theorem 3).
Proof. The truth value of \(F\) in a row of its truth table is computed from the truth values of its parts in that row, using the truth table of each connective. \(F'\) is computed the same way, except that \(B\) takes the place of \(A\). \(A\) and \(B\) have the same truth value in every row, so each step of the computation gives the same value for \(F'\) as for \(F\). So \(F\) and \(F'\) have the same truth value in every row.
Example 7 (Replacing a part) Since \(P \lor (P \land Q) \equiv P\) (Example 1), Theorem 4 gives \(R \land (P \lor (P \land Q)) \equiv R \land P\) and \(\neg (P \lor (P \land Q)) \equiv \neg P\).
Example 8 (Simplifying part of a proposition)
By double negation, \(\neg \neg Q \equiv Q\). Take \(F\) to be \(\neg P \lor \neg \neg Q\), with \(A = \neg \neg Q\) and \(B = Q\). By replacing a part by an equivalent part,
\[
\neg P \lor \neg \neg Q \equiv \neg P \lor Q.
\]
Theorem 5 (De Morgan’s laws for propositions) For any propositions \(P\) and \(Q\) (Wikipedia contributors 2026a):
\[
\begin{aligned}
\neg (P \land Q) &\equiv \neg P \lor \neg Q \\
\neg (P \lor Q) &\equiv \neg P \land \neg Q
\end{aligned}
\]
Proof. Each side of each law is built from \(P\) and \(Q\), so by Definition 1 it is enough to compare the two sides in each of the four rows of a truth table:
| T |
T |
F |
F |
F |
F |
| T |
F |
T |
T |
F |
F |
| F |
T |
T |
T |
F |
F |
| F |
F |
T |
T |
T |
T |
The third and fourth columns agree in every row, which proves the first law, and the fifth and sixth columns agree in every row, which proves the second.
Example 9 (Neither coordinate positive) For real numbers \(x\) and \(y\), by the second of De Morgan’s laws, “not (\(x > 0\) or \(y > 0\))” is logically equivalent to “\(x \le 0\) and \(y \le 0\)”.
Exercise 5 (A broken deployment rule) A team’s rule is “if the tests pass, then the build is deployed”. Let \(P\) be “the tests pass” and \(Q\) be “the build is deployed”. The rule is broken on the days when \(\neg (P \Rightarrow Q)\) is true.
Write \(\neg (P \Rightarrow Q)\) without \(\Rightarrow\), and in English.
Solution 5. The rule is broken on a day when the tests pass and the build is not deployed: \(P \land \neg Q\). On a day when the tests fail, the rule is not broken, whether or not the build is deployed.
“If the tests pass, then the build is not deployed”, \(P \Rightarrow \neg Q\), is not the negation: on a day when the tests fail, it is true, and so is the rule.
Theorem 6 (Negating a conditional) For propositions \(P\) and \(Q\),
\[
\neg (P \Rightarrow Q) \equiv P \land \neg Q.
\]
Proof. By the definition of implies, \(P \Rightarrow Q\) is false exactly when \(P\) is true and \(Q\) is false. So \(\neg (P \Rightarrow Q)\) is true exactly in that row of the truth table. By the definition of and, \(P \land \neg Q\) is true exactly when \(P\) is true and \(\neg Q\) is true. That is the same row.
Example 10 (When a search claim fails) The negation of “if the list is sorted, then binary search finds the key” is “the list is sorted and binary search does not find the key” (Theorem 6).
Corollary 1 (A conditional without the arrow) For propositions \(P\) and \(Q\),
\[
(P \Rightarrow Q) \equiv (\neg P \lor Q).
\]
Example 11 (A rule as an “or”) By Corollary 1, “if the tests pass, then the build is deployed” is logically equivalent to “the tests fail or the build is deployed”.
Negating quantified propositions
Exercise 6 (Not every test passes) Let \(T\) be the set of tests in a test suite, and let \(P(t)\) be “test \(t\) passes”. The report “every test passes” is \(\forall t \in T, P(t)\).
Write the negation of this report in English and in symbols, without putting \(\neg\) in front of a quantifier.
Solution 6. “Some test fails”: \(\exists t \in T, \neg P(t)\). “Every test passes” is false exactly when at least one test does not pass.
“Every test fails”, \(\forall t \in T, \neg P(t)\), is not the negation: when some tests pass and some fail, both it and “every test passes” are false.
Theorem 7 (De Morgan’s laws for quantifiers) For a set \(S\) and a predicate \(P(x)\) whose domain of discourse is \(S\):
\[
\begin{aligned}
\neg (\forall x \in S, P(x)) &\equiv \exists x \in S, \neg P(x) \\
\neg (\exists x \in S, P(x)) &\equiv \forall x \in S, \neg P(x)
\end{aligned}
\]
Proof.
- By the definition of the universal quantifier, \(\forall x \in S, P(x)\) is false exactly when \(P(x)\) is false for at least one \(x\) in \(S\). By the definition of the existential quantifier, that is exactly when \(\exists x \in S, \neg P(x)\) is true.
- By the definition of the existential quantifier, \(\exists x \in S, P(x)\) is false exactly when \(P(x)\) is false for every \(x\) in \(S\). By the definition of the universal quantifier, that is exactly when \(\forall x \in S, \neg P(x)\) is true.
Example 12 (No natural square root of 2) By part 2 of Theorem 7, \(\neg (\exists n \in \mathbb{N}, n^2 = 2)\) has the same truth value as \(\forall n \in \mathbb{N}, n^2 \ne 2\).
Exercise 7 (Completing a palindrome) Let \(W\) be the set of words made of the letters a and b, including the empty word, and write \(s t\) for word \(s\) followed by word \(t\). A palindrome is a word that reads the same forwards and backwards, such as abba.
Write the negation of \[
\forall s \in W,\ \exists t \in W,\ s t \text{ is a palindrome}
\] without putting \(\neg\) in front of a quantifier.
Solution 7. Apply Theorem 7 twice, from the outside in. First, the negation has the truth value of \[
\exists s \in W,\ \neg (\exists t \in W,\ s t \text{ is a palindrome}).
\] For each word \(s\), Theorem 7 says that \(\neg (\exists t \in W,\ s t \text{ is a palindrome})\) has the truth value of \(\forall t \in W,\ s t \text{ is not a palindrome}\). These have the same truth value for every \(s\), so the \(\exists s\) propositions built from them do too (Definition: Existential quantifier), and the negation has the truth value of \[
\exists s \in W,\ \forall t \in W,\ s t \text{ is not a palindrome}.
\] In English: some word cannot be made into a palindrome by adding letters at its end.
Exercise 8 (Which one is true?) Which is true: \(\forall s \in W,\ \exists t \in W,\ s t \text{ is a palindrome}\), from Exercise 7, or its negation?
Solution 8. The original is true, so its negation is false. For any word \(s\), let \(t\) be \(s\) written backwards; then \(s t\) reads the same backwards. For example, for \(s = \text{aab}\), \(t = \text{baa}\) and \(s t = \text{aabbaa}\).
Back to top