Every “if … then …” in a program, every WHERE condition in a database query and every chip in your phone rests on the logic of true and false. In the 1730s Leonhard Euler asked whether one could walk through Königsberg crossing each of its seven bridges exactly once, and to prove that it is impossible he laid the foundations of graph theory. Discrete mathematics (logic, sets, functions and graphs) is the language of proofs and of computer science.
Propositions, truth tables and quantifiers
PropositionDefinition
A sentence that is either true (1) or false (0), for example “7 is prime”. Compound propositions are built with the connectives ¬ (not), ∧ (and), ∨ (or), → (if … then) and ↔ (if and only if).
| p | q | ¬p | p ∧ q | p ∨ q | p → q | p ↔ q |
|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 | 1 |
The implication p → q is false only when p is true and q is false. The promise “if it rains, I take an umbrella” is broken only by a rainy day without an umbrella; on a dry day it is kept whatever I do. That is why an implication with a false premise counts as true.
Where
- ≡
- logically equivalent: the same truth value in every row
De Morgan's laws.
Where
- ¬q → ¬p
- the contrapositive, equivalent to p → q
- q → p
- the converse, which is not equivalent
Statements about many objects use the quantifiers ∀ (“for all”) and ∃ (“there exists”). For example, ∀x ∈ ℝ: x² ≥ 0 is true, while ∃n ∈ ℕ: n² = 2 is false. To negate a quantified statement, swap ∀ and ∃ and negate what follows:
Where
- P(x)
- a property of x (a predicate)
- ∀
- the universal quantifier
- ∃
- the existential quantifier
Negating a statement
Problem
Negate: a) “Every student of the group passed at least one exam”; b) “If a number is divisible by 4, it is even”.
Show solutionHide solution
Solution
b) p → q with p = “divisible by 4” and q = “even”. The negation is p ∧ ¬q: “there is a number divisible by 4 that is not even”. This is false, so the original statement is true.
Interactive
Methods of proof
- Direct proof: start from the assumptions and reach the conclusion by valid steps.
- Contrapositive: to prove p → q, prove ¬q → ¬p instead.
- Proof by contradiction: assume the statement is false and derive something impossible.
- Mathematical induction: prove P(1), then prove that P(n) implies P(n + 1); then P(n) holds for every natural n, like an endless row of falling dominoes.
A direct proof and a proof by contradiction
Problem
Prove: a) the sum of two odd numbers is even; b) √2 is irrational.
Show solutionHide solution
Solution
b) Suppose √2 = p/q, a fraction in lowest terms. Then p² = 2q², so p² is even and therefore p is even (if p were odd, p² would be odd): p = 2k.
Then 4k² = 2q², so q² = 2k² and q is even too.
Both p and q are even, which contradicts “lowest terms”. Hence √2 is irrational ∎.
Where
- P(1)
- the base case
- P(n) → P(n + 1)
- the induction step; P(n) is the induction hypothesis
Induction: the sum of odd numbers
Problem
Prove that 1 + 3 + 5 + … + (2n − 1) = n² for every natural n.
Show solutionHide solution
Solution
Step: assume 1 + 3 + … + (2n − 1) = n². Add the next odd number, 2n + 1:
1 + 3 + … + (2n − 1) + (2n + 1) = n² + 2n + 1 = (n + 1)².
This is the statement for n + 1, so by induction it holds for all n ∎. For example, 1 + 3 + 5 + 7 = 16 = 4².
Sets and Venn diagrams
Where
- A ∪ B
- union: elements in A or in B (or in both)
- A ∩ B
- intersection: elements in both
- A \ B
- difference: in A but not in B
- Aᶜ
- complement: the elements of the universal set U not in A
Set operations mirror logic: ∪ corresponds to ∨, ∩ to ∧ and the complement to ¬, so De Morgan's laws hold again: (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ and (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ. A ⊆ B means that every element of A is in B. A set with n elements has 2ⁿ subsets, and the Cartesian product A × B consists of all ordered pairs (a, b).
Where
- |A|
- the number of elements of A
Inclusion–exclusion: elements in both sets were counted twice, so we subtract them once. For three sets: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.
Languages in a group
Problem
In a group of 40 students, 25 study English, 18 study Russian and 7 study both. How many study at least one of the languages, how many study neither, and how many study only English?
Show solutionHide solution
Solution
Neither: 40 − 36 = 4.
Only English: 25 − 7 = 18; only Russian: 18 − 7 = 11.
Check with the regions of the Venn diagram: 18 + 7 + 11 + 4 = 40 ✓.
Relations and functions
A relation from A to B is any subset R ⊆ A × B. A relation on one set can be reflexive (a R a), symmetric (a R b ⇒ b R a) and transitive (a R b and b R c ⇒ a R c). All three together make an equivalence relation, which splits the set into classes: for example, “gives the same remainder when divided by 3” splits ℤ into three classes.
FunctionDefinition
A relation f: A → B in which every element a ∈ A has exactly one image f(a) ∈ B. A is the domain and B is the codomain.
| Type | Meaning | Example |
|---|---|---|
| Injective (one-to-one) | Different elements have different images: f(a₁) = f(a₂) ⇒ a₁ = a₂ | f(x) = 2x, ℤ → ℤ (not surjective: odd numbers are missed) |
| Surjective (onto) | Every b ∈ B is the image of some a | f(x) = x³ − x, ℝ → ℝ (not injective: f(0) = f(1) = 0) |
| Bijective | Both injective and surjective; it has an inverse f⁻¹ | f(x) = x³, ℝ → ℝ; f(x) = x², [0, ∞) → [0, ∞) |
| Neither | Neither injective nor surjective | f(x) = x², ℝ → ℝ: f(−2) = f(2), and negative numbers are never values |
Graphs
GraphDefinition
A set V of vertices together with a set E of edges, each joining two vertices: G = (V, E). The degree deg(v) is the number of edges at v. A path is a sequence of vertices joined by edges, a cycle is a closed path, and a graph is connected if any two vertices are joined by a path.
Where
- deg(v)
- the degree of vertex v
- |E|
- the number of edges
The handshake lemma: every edge has two ends. Consequence: the number of vertices of odd degree is always even.
Where
- |V|
- the number of vertices of the tree
A tree is a connected graph without cycles (a family tree, the folders on a computer, a network built with as few links as possible). Every tree has exactly one edge fewer than vertices: adding any edge creates a cycle, and removing any edge disconnects it.
An Euler path uses every edge exactly once; an Euler circuit also returns to its start. Euler's theorem: a connected graph has an Euler circuit exactly when all degrees are even, and an (open) Euler path exactly when exactly two vertices have odd degree; the path must start at one of them and end at the other. In Königsberg the four land areas had degrees 5, 3, 3 and 3: four odd vertices, so the walk is impossible. A Hamilton path visits every vertex exactly once; no simple test for it is known, and finding the shortest such tour (the travelling salesman problem) is one of the famous hard problems of computer science.
Draw the house without lifting the pencil
Problem
A “house”: the square ABCD (A bottom left, B bottom right, C top right, D top left) with both diagonals AC and BD and a roof D–E–C. Can it be drawn in one stroke without drawing any line twice?
Show solutionHide solution
Solution
Degrees: A = 3, B = 3, C = 4, D = 4, E = 2; the sum is 16 = 2 · 8 ✓ (handshake lemma).
Exactly two vertices are odd (A and B), so an Euler path exists, and it must start at A or at B.
One solution: A → B → D → E → C → D → A → C → B.
An Euler circuit is impossible, because A and B have odd degree.
Handshakes
Problem
a) 10 people meet, and each shakes hands with exactly 3 others. How many handshakes are there? b) Can each of 7 people shake hands with exactly 3 others?
Show solutionHide solution
Solution
b) The sum would be 7 · 3 = 21, an odd number, but it must equal 2|E|. Impossible.
Remember
- p → q is false only when p = 1 and q = 0; p → q ≡ ¬q → ¬p, but it is not equivalent to q → p.
- Negation: ∀ and ∃ swap, ∧ and ∨ swap (De Morgan), and ¬(p → q) ≡ p ∧ ¬q.
- Induction: base P(1) plus step P(n) ⇒ P(n + 1); both parts are compulsory.
- |A ∪ B| = |A| + |B| − |A ∩ B|; (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ.
- Bijection = injection + surjection; only a bijection has an inverse.
- ∑ deg(v) = 2|E|; a tree has |E| = |V| − 1; an Euler path needs 0 or 2 odd vertices.