Logic, sets and graphs

Propositional logic and truth tables, quantifiers, proof methods (direct, contradiction, induction), set operations and Venn diagrams, relations and functions (injective, surjective, bijective) and graph basics: degrees, paths, trees, Euler and Hamilton paths.

  • University
  • 32 min
  • 10 questions
  • Lesson 92 of 92

In this lesson you will learn

  • Build truth tables, use logical equivalences and negate statements with quantifiers
  • Write direct proofs, proofs by contradiction and proofs by induction
  • Compute with sets and decide whether a function is injective, surjective or bijective
  • Reason about graphs with degrees and decide whether an Euler path exists

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).

pq¬pp ∧ qp ∨ qp → qp ↔ q
1101111
1000100
0110110
0010011
Truth table of the basic connectives (1 = true, 0 = false). With n variables a table has 2ⁿ rows.

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.

¬(p ∧ q) ≡ ¬p ∨ ¬q¬(p ∨ q) ≡ ¬p ∧ ¬q

Where

≡
logically equivalent: the same truth value in every row

De Morgan's laws.

p → q ≡ ¬p ∨ q ≡ ¬q → ¬p¬(p → q) ≡ p ∧ ¬q

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:

¬(∀x P(x)) ≡ ∃x ¬P(x)¬(∃x P(x)) ≡ ∀x ¬P(x)

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

a) ∀s ∃e: passed(s, e). Negation: ∃s ∀e: ¬passed(s, e), that is, “some student failed every exam” (not “nobody passed”!).
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

Loading simulation…
Logic in hardware: a NAND gate outputs ¬(p ∧ q). Remarkably, every truth table can be built from NAND gates alone, which makes them a basic building block of chips.

Sign up free to keep reading

The rest of the lesson, the quiz and your notes open with an Educora account. Signing up takes a minute, and your progress is saved on all your devices.

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

a) Odd numbers are 2k + 1 and 2m + 1 with integers k and m. Their sum is 2k + 2m + 2 = 2(k + m + 1), a multiple of 2 ∎.
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 ∎.
P(1) ∧ [∀n: P(n) → P(n + 1)] ⇒ ∀n ∈ ℕ: P(n)

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

Base: n = 1: 1 = 1² ✓.
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

A ∪ B, A ∩ B, A \ B, Aᶜ

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).

|A ∪ B| = |A| + |B| − |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

|E ∪ R| = 25 + 18 − 7 = 36 study at least one language.
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.

TypeMeaningExample
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 af(x) = x³ − x, ℝ → ℝ (not injective: f(0) = f(1) = 0)
BijectiveBoth injective and surjective; it has an inverse f⁻¹f(x) = x³, ℝ → ℝ; f(x) = x², [0, ∞) → [0, ∞)
NeitherNeither injective nor surjectivef(x) = x², ℝ → ℝ: f(−2) = f(2), and negative numbers are never values
The type of a function depends not only on the formula but also on the sets A and B.

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.

∑ deg(v) = 2 · |E|

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.

|E| = |V| − 1

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

Edges: AB, BC, CD, DA, AC, BD, DE, EC, 8 in total.
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

a) The sum of degrees is 10 · 3 = 30 = 2|E|, so there are 15 handshakes.
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.
Spotted a mistake or something inaccurate in this lesson?

Check yourself

10 questions. Every correct answer earns XP.

Question 1 / 10

Question 1 / 10. Which formula is equivalent to ¬(p → q)?