Topic 01 — CS 70 Discrete Mathematics
Propositional Logic
& Proofs
The language of mathematics. Every theorem, every algorithm, every claim in this course is ultimately expressed in the formal language of logic. Master this first, and everything else follows.
What Is Propositional Logic?
Propositional logic is a formal system for reasoning about statements that are either true or false. It gives us a precise language to express and analyze mathematical claims — replacing vague English with unambiguous symbols.
A proposition is a declarative statement that has a definite truth value: either True (T) or False (F). It cannot be both, and it cannot be neither.
✓ Valid Propositions
"7 is prime." (T)
"4 is odd." (F)
"All primes are odd." (F)
✗ Not Propositions
"What is 2+2?" (question)
"x > 5" (open — depends on x)
"Do your homework!" (command)
We use uppercase letters P, Q, R, ... to denote propositions, and combine them using logical connectives to form more complex statements called compound propositions.
Logical Connectives
These are the fundamental operations of propositional logic — the "arithmetic" of true and false.
Negation (NOT) — ¬P
¬P is True when P is False, and False when P is True. It simply flips the truth value.
Conjunction (AND) — P ∧ Q
P ∧ Q is True only when both P and Q are True. If either is False, the whole conjunction is False.
Disjunction (OR) — P ∨ Q
P ∨ Q is True when at least one of P or Q is True. It is False only when both are False. This is inclusive or — both can be true simultaneously.
Exclusive OR — P ⊕ Q
P ⊕ Q is True when exactly one of P or Q is true (but not both). Less common in proofs, more common in CS/circuits.
Biconditional — P ↔ Q
P ↔ Q (read "P if and only if Q" or "P iff Q") is True when P and Q have the same truth value — both True or both False.
Truth Tables
A truth table enumerates all possible combinations of truth values for the variables and computes the resulting truth value of a compound proposition. For n variables, there are exactly 2ⁿ rows.
Complete Truth Table for Core Connectives
| P | Q | ¬P | P ∧ Q | P ∨ Q | P ⊕ Q | P ↔ Q |
|---|---|---|---|---|---|---|
| T | T | F | T | T | F | T |
| T | F | F | F | T | T | F |
| F | T | T | F | T | T | F |
| F | F | T | F | F | F | T |
Logical Equivalence
Two propositions are logically equivalent (written P ≡ Q) if they have identical truth tables — the same truth value for every possible assignment of variables.
De Morgan's Laws:
Double Negation: ¬(¬P) ≡ P
Contrapositive: (P → Q) ≡ (¬Q → ¬P)
Biconditional: (P ↔ Q) ≡ (P → Q) ∧ (Q → P)
Implication (If–Then)
The implication P → Q (read "if P then Q", or "P implies Q") is the most important — and most frequently misunderstood — connective in mathematics.
| P | Q | P → Q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
Related Forms of an Implication
Original: P → Q
"If P then Q"
Converse: Q → P
Not equivalent to original
Inverse: ¬P → ¬Q
Not equivalent to original
Contrapositive: ¬Q → ¬P
Logically equivalent to original ✓
Students often confuse the converse (Q → P) with the contrapositive (¬Q → ¬P). Only the contrapositive is equivalent to the original implication. If you prove the converse, you've proven nothing about the original!
Quantifiers
Propositions about all or some elements of a set require quantifiers. They turn open statements like "x > 5" (which has no truth value on its own) into actual propositions.
∀x ∈ S, P(x) — "For all x in S, P(x) is true." True if P holds for every single element. False if there exists even one counterexample.
∃x ∈ S, P(x) — "There exists some x in S such that P(x) is true." True if at least one element satisfies P. False only if no element satisfies P.
Negating Quantified Statements
Negation "flips" quantifiers and negates the predicate. This is the quantifier version of De Morgan's Laws:
Statement: "Every integer has at least one divisor." → ∀n ∈ ℤ, ∃d ∈ ℤ, d | n
Negation: "There exists an integer with no divisors." → ∃n ∈ ℤ, ∀d ∈ ℤ, d ∤ n
The original is True (1 always divides n). The negation is False.
∀x ∃y, P(x,y) and ∃y ∀x, P(x,y) are very different. The first says: for each x, we can find a y (y can depend on x). The second says: there's one y that works for all x simultaneously — a much stronger statement.
The Four Proof Strategies
Every proof in this course uses one or more of these four strategies. Learn to recognize which one fits the structure of the claim you want to prove.
1. Direct Proof
To prove P → Q: Assume P is true, then use definitions, algebra, and logic to derive that Q must be true.
- Assume n is even. By definition of even: n = 2k for some integer k.
- Compute n²: n² = (2k)² = 4k² = 2(2k²).
- Since 2k² is an integer, n² = 2·(integer), so n² is even. ∎
When to use it: When the hypothesis gives you something concrete to work with, and a chain of algebra/logic naturally leads to the conclusion.
2. Proof by Contrapositive
To prove P → Q, instead prove ¬Q → ¬P. These are logically equivalent, so proving either one suffices. Assume ¬Q is true, then derive that ¬P must be true.
Contrapositive: If n is not odd (i.e., n is even), then n² is not odd (i.e., n² is even).
- Assume n is even. Then n = 2k for some integer k.
- n² = 4k² = 2(2k²), which is even.
- Therefore, if n is even then n² is even. By contrapositive, if n² is odd then n is odd. ∎
When to use it: When the conclusion is of the form "n has property X" and it's easier to start from "n does NOT have property X." Common when negating the conclusion gives you something concrete (like "n is even" from "n is not odd").
3. Proof by Contradiction
To prove P: Assume ¬P, then through logical deductions arrive at a contradiction — a statement of the form R ∧ ¬R (something that is simultaneously true and false). This contradiction shows ¬P cannot hold, so P must be true.
- Assume √2 is rational. Then √2 = p/q where p, q ∈ ℤ, q ≠ 0, and gcd(p,q) = 1 (fraction in lowest terms).
- Squaring: 2 = p²/q², so p² = 2q². Thus p² is even, so p is even (by our earlier result).
- Write p = 2m. Then (2m)² = 2q² → 4m² = 2q² → q² = 2m². So q² is even, meaning q is even.
- Both p and q are even → gcd(p,q) ≥ 2. But we assumed gcd(p,q) = 1. Contradiction! ∎
When to use it: When you want to prove something exists, or prove a negative ("there is no ..."), or when assuming the opposite gives you rich structure to work with. The contradiction (R and ¬R) often arises naturally.
4. Proof by Cases
Divide the universe of possibilities into exhaustive, non-overlapping cases. Prove the claim in each case separately. Together, they cover all possibilities.
Note: n² + n = n(n+1). We case split on parity of n.
Case 1: n is even. Then n = 2k, so n(n+1) = 2k(2k+1) = 2·[k(2k+1)], which is even.
Case 2: n is odd. Then n+1 is even, so n+1 = 2k, thus n(n+1) = n·2k = 2·[nk], which is even.
In both exhaustive cases, n(n+1) is even. ∎
When to use it: When the statement is true "for different reasons" depending on which case you're in. Common when splitting on parity (even/odd), sign (positive/negative/zero), or magnitude.
Worked Examples from Discussion
Perfect Squares (DIS 0B)
We know n² is odd implies n is odd (proven by contrapositive above). So write n = 2m+1.
- n = 2m+1 for some integer m.
- n² = (2m+1)² = 4m² + 4m + 1 = 4m(m+1) + 1.
- Notice m(m+1) is always even (product of consecutive integers). Write m(m+1) = 2j.
- Then n² = 4(2j) + 1 = 8j + 1. Set k = j. ∎
Numbers of Friends (DIS 0B — Pigeonhole)
Key insight: Each person has a friend count in {0, 1, 2, ..., n−1}. That's n possible values for n people. But values 0 and n−1 cannot both occur: if someone knows everyone (n−1 friends), then nobody knows 0 people.
- Each person's friend count ∈ {0, 1, ..., n−1} — that's n values.
- If someone has n−1 friends, they know everyone, so no one has 0 friends. Similarly if someone has 0 friends, no one has n−1 friends. So the actual range has at most n−1 distinct values.
- By Pigeonhole: n people, at most n−1 possible friend counts → at least two people share the same count. ∎
Pebbles (DIS 0B — Contradiction)
- Assume for contradiction that no column is all-red. Then every column has at least one blue pebble.
- Select one blue pebble from each column. This gives a selection of one pebble per column.
- But all selected pebbles are blue — no red pebble among them. This contradicts our hypothesis. ∎
Common Pitfalls & Mistakes
Proving Q → P does NOT prove P → Q. They are different implications. The contrapositive (¬Q → ¬P) is equivalent; the converse (Q → P) is not.
In a direct proof, you assume P and derive Q. You must not assume Q anywhere in your derivation — that's circular reasoning.
In proof by cases, you must cover ALL possibilities. "n is positive or n is negative" misses n = 0. "n is divisible by 2 or 3" misses numbers like 7.
∀x ∃y is different from ∃y ∀x. Always write quantifiers carefully. "Every student has a favorite class" ≠ "There is a class that is every student's favorite."
Practice Problems
Let P = True, Q = False. Evaluate:
(i) P ∧ Q → F (both must be true)
(ii) P → Q → F (T → F is False)
(iii) ¬P → Q → T (F → F is True — vacuously)
(iv) ¬Q → ¬P → T (T → F... wait: ¬Q = T, ¬P = F → F)
Note: (ii) and (iv) have the same truth value — they are contrapositives of each other ✓
English: "There is no largest integer."
Logic: ¬(∃M ∈ ℤ, ∀n ∈ ℤ, n ≤ M)
Equivalent form: ∀M ∈ ℤ, ∃n ∈ ℤ, n > M
Prove: for all integers n, if n³ is even, then n is even.
Hint: Try contrapositive. If n is odd, show n³ is odd.
Contrapositive: Assume n is odd, so n = 2k+1. Then n³ = (2k+1)³ = 8k³ + 12k² + 6k + 1 = 2(4k³+6k²+3k) + 1, which is odd. Done ∎