Discrete mathematics studies things you can count one by one: statements, integers, sets, networks and sequences. It is the language behind computer science, cryptography and the proofs you will meet in every upper-level math course. In this chapter you will learn to reason precisely, to write short proofs, and to count and model discrete structures.
1. Propositional logic
A proposition is a statement that is either true (T) or false (F), never both. “17 is prime” is a proposition; “Close the door” is not. We build new propositions with connectives: not (\(\lnot p\)), and (\(p\land q\)), or (\(p\lor q\), inclusive), and the implication \(p\Rightarrow q\) (“if \(p\) then \(q\)”).
| \(p\) | \(q\) | \(\lnot p\) | \(p\land q\) | \(p\lor q\) | \(p\Rightarrow q\) |
|---|---|---|---|---|---|
| T | T | F | T | T | T |
| T | F | F | F | T | F |
| F | T | T | F | T | T |
| F | F | T | F | F | T |
\(p\Rightarrow q\) is false only when \(p\) is true and \(q\) is false. For \(p\Rightarrow q\):
- the converse is \(q\Rightarrow p\);
- the contrapositive is \(\lnot q\Rightarrow\lnot p\), which is always equivalent to the original.
\(\lnot(p\land q)\equiv \lnot p\lor\lnot q\) and \(\lnot(p\lor q)\equiv \lnot p\land\lnot q\). Also \(\lnot(p\Rightarrow q)\equiv p\land\lnot q\).
“It is sunny and the temperature is above 70°F.” Its negation is “It is not sunny or the temperature is at most 70°F.” The converse of “If it rains, the game is canceled” is “If the game is canceled, it rained,” which is not equivalent; the contrapositive “If the game is not canceled, it did not rain” is.
2. Quantifiers
A statement about a variable needs quantifiers. The symbol \(\forall\) means “for all” and \(\exists\) means “there exists.” For example, \(\forall x\in\mathbb{R},\ x^2\ge 0\) is true, while \(\exists x\in\mathbb{R},\ x^2=-1\) is false.
\(\lnot(\forall x,\,P(x))\equiv\exists x,\,\lnot P(x)\) and \(\lnot(\exists x,\,P(x))\equiv\forall x,\,\lnot P(x)\). To disprove a “for all” claim, one counterexample is enough.
Over the integers, \(\forall x\,\exists y\ (x+y=0)\) is true (take \(y=-x\)), but \(\exists y\,\forall x\ (x+y=0)\) is false, because one single \(y\) cannot work for every \(x\).
3. Direct proof and contradiction
A direct proof starts from the hypotheses and reaches the conclusion by valid steps. A proof by contrapositive proves \(\lnot q\Rightarrow\lnot p\) instead. A proof by contradiction assumes the statement is false and derives something impossible.
Claim: the product of two odd integers is odd. Write the integers as \(2a+1\) and \(2b+1\). Then \((2a+1)(2b+1)=4ab+2a+2b+1=2(2ab+a+b)+1\), which has the form \(2k+1\). So the product is odd.
Claim: \(\sqrt2\) is irrational. Suppose \(\sqrt2=\dfrac ab\) with \(a,b\) integers and the fraction in lowest terms. Then \(a^2=2b^2\), so \(a^2\) is even, so \(a\) is even: \(a=2k\). Then \(4k^2=2b^2\), so \(b^2=2k^2\) and \(b\) is even too. Both are even, which contradicts “lowest terms.” Hence \(\sqrt2\) is irrational.
4. Mathematical induction
Induction proves a statement \(P(n)\) for every integer \(n\ge n_0\).
- Base case: check \(P(n_0)\).
- Inductive step: assume \(P(n)\) for some \(n\ge n_0\) (the inductive hypothesis) and prove \(P(n+1)\).
- Conclude that \(P(n)\) holds for all \(n\ge n_0\).
Think of dominoes: the base case knocks over the first one, and the inductive step guarantees each domino knocks over the next.
Claim: \(3\mid 4^n-1\) for all \(n\ge1\). Base: \(4^1-1=3\). Step: if \(4^n-1=3m\), then \(4^{n+1}-1=4(4^n-1)+3=12m+3=3(4m+1)\), a multiple of 3. So the claim holds for every \(n\ge1\).
5. Sets and functions
A set is a collection of distinct objects. We use union \(A\cup B\), intersection \(A\cap B\), difference \(A\setminus B\) and size \(|A|\). For finite sets, inclusion–exclusion gives \(|A\cup B|=|A|+|B|-|A\cap B|\).
In the diagram, \(|A|=6\), \(|B|=5\), \(|A\cap B|=3\), so \(|A\cup B|=6+5-3=8\).
A function \(f:X\to Y\) assigns exactly one output in \(Y\) to each input in \(X\). It is injective (one-to-one) if \(f(a)=f(b)\Rightarrow a=b\); surjective (onto) if every element of \(Y\) is an output; bijective if both. A bijection has an inverse function \(f^{-1}\).
A set with \(n\) elements has \(2^n\) subsets, since each element is either in or out.
6. Counting and combinations
- Multiplication principle: independent choices multiply.
- Permutations: ordered selections of \(k\) from \(n\): \(P(n,k)=\dfrac{n!}{(n-k)!}\).
- Combinations: unordered selections: \(C(n,k)=\dbinom nk=\dfrac{n!}{k!\,(n-k)!}\).
Each number in Pascal’s triangle is the sum of the two above it, because \(C(n,k)=C(n-1,k-1)+C(n-1,k)\). When some objects repeat, divide by the factorials of the repeat counts.
A club of 10 students picks a 3-person committee: \(C(10,3)=\dfrac{10\cdot9\cdot8}{3\cdot2\cdot1}=120\). If instead it picks a president, a secretary and a treasurer, order matters: \(P(10,3)=10\cdot9\cdot8=720\). The letters of “SEEDS” can be arranged in \(\dfrac{5!}{2!\,2!}=30\) ways.
7. Graphs basics
A graph has vertices (dots) joined by edges (lines). The degree of a vertex is the number of edges at it. A path moves along edges; a graph is connected if a path joins any two vertices.
The sum of all degrees equals twice the number of edges. So the number of odd-degree vertices is always even. In the graph above, \(2+2+3+2+1=10=2\cdot5\).
An Euler path uses every edge exactly once. A connected graph has one exactly when it has 0 or 2 vertices of odd degree. Here C and E are the only odd vertices, so an Euler path exists and must start at one and end at the other. The complete graph \(K_n\) (every pair joined) has \(\dfrac{n(n-1)}2\) edges.
8. Recurrence relations
A recurrence relation defines each term from earlier ones, together with starting values. Solving it means finding a closed form that gives the \(n\)th term directly.
Moving \(n\) disks takes \(h_n=2h_{n-1}+1\) moves, with \(h_1=1\). The terms are 1, 3, 7, 15, 31, 63. They match \(h_n=2^n-1\). Check by induction: \(2(2^{n-1}-1)+1=2^n-1\).
- Arithmetic type \(a_n=a_{n-1}+d\): \(a_n=a_0+nd\).
- Geometric type \(a_n=r\,a_{n-1}\): \(a_n=a_0r^n\).
- For \(a_n=\alpha a_{n-1}+\beta a_{n-2}\), try \(a_n=r^n\), solve \(r^2=\alpha r+\beta\), and fit the two starting values.
On my home planet we test every closed form on the first three terms before celebrating. It takes ten seconds and catches almost every slip!
Key takeaways
- \(p\Rightarrow q\) is false only when \(p\) is true and \(q\) is false; it is equivalent to its contrapositive, not to its converse.
- Negating swaps \(\forall\) and \(\exists\) and negates the inside; one counterexample kills a “for all.”
- Direct proof, contrapositive and contradiction are your three basic proof tools.
- Induction needs a base case and an inductive step.
- \(|A\cup B|=|A|+|B|-|A\cap B|\); \(P(n,k)=\frac{n!}{(n-k)!}\); \(C(n,k)=\frac{n!}{k!(n-k)!}\).
- In any graph, the sum of the degrees is twice the number of edges.
- Test every closed form of a recurrence on the first terms.
Test yourself: quick challenge for College
Speed drill for College: how many in 60 seconds?
🚀 Keep exploring with Zyro
✏️ Math practiceLogic, Proofs and Discrete Math: math practice, College
📝 Math testsLogic, Proofs and Discrete Math: math test, College
🎯 Math quizzesLogic, Proofs and Discrete Math: math quiz, College
✏️ Math practiceLimits and Continuity: math practice, College
✏️ Math practiceThe Derivative and Its Definition: math practice, College
📝 Math testsLimits and Continuity: math test, College