You should know what a set is. You should know how the empty set, set union, intersection ("snitt"), difference, and complement work, and what their properties are (commutativity, associativity).

The sets I expect you to know about are: 𝔹 (booleans, {false, true}), ℕ (natural numbers), ℤ (integer numbers ("heltal")), ℕ+/ℤ+ (positive integers), ℚ (rational numbers), ℝ (real numbers). You do not have to know about the complex numbers.

You should know what a function is. You should know about injectivity, surjectivity. You should know what a bijection is. You should be able to construct examples of functions that do/do not have these properties. You should be able to reason about whether or not functions have these properties. You should know about function composition.

You should know about operators. You should know about commutativity, associativity, unit arguments ("identitet"). You should be able to construct examples of operators that do/do not have these properties. You should be able to reason about whether or not operators have these properties.

You should know what a (binary) relation is. You should know about reflexivity, symmetry, transitivity. You should know what an equivalence relation is. You should know about equivalence classes. You should be able to construct examples of relations that do/do not have these properties. You should be able to reason about whether or not relations have these properties.

You should know about Hilbert's hotel and how it can be used to show whether or not a given set has as many elements or more elements than there are natural numbers.

Book: Sect. 4.1, 4.3, 4.4.

Hilbert's hotel

exercises week 1 (sets and functions) and the answers

exercises week 5 (arithmetic) and the answers (for relations)

You should know and understand the logical operators (connectives) and/conjunction, or/disjunction, implication, equivalence, not/negation.

You should be able to construct truth tables for logical formulas, and use them to reason about which formulas are equivalent to which other ones, or which formulas follow from other ones, in order to check validity of given arguments.

You should understand what universal ("for all") quantification is, and what existential ("there exist") quantification is. You should know and be able to use the proper notation for this.

You should be able to understand what is required to prove or disprove logical formulas that are built from these connectives and quantifiers.

You should be able to formulate a statement in natural language (Swedish) in terms of a logical formulas, and choose the right connectives.

You should be able to construct a proof based on your understanding of what is required to prove/disprove a formula.

Book: Ch. 1, Ch. 3.

predikatlogik övningar, skriva och bevis (pdf)

proof methods (pdf)

exercises week 2 (logic) and the answers

You should be able to understand induction proofs over natural numbers, both simple induction ("enkel induktion") and strong induction ("stark induktion"). You should be able to construct induction proofs, with proper base case and step case. You should be able to be clear about what steps you are taking in an induction proof, and why, and be clear about what the induction hypothesis is and where it is used.

You should know what a geometric sum and an arithmetic sum is, and be able to recognize them. You should know (or be able to derive) how to compute these sums. You should know how to prove that this way of computing them is correct.

You should know what an invariant is. You should be able to find simple invariants for given examples.

You should be able to understand induction proofs over recursive structures, using structural induction. You should be able to construct structural induction proofs, with proper base cases and step cases. You should be able to be clear about what steps you are taking in an induction proof, and why, and be clear about what the induction hypothesis is and where it is used.

Book: Ch. 5, Ch. 2, Sect. 6.2.

induction proofs

exercises week 3 (induction) and the answers

structural induction (pdf)

exercises week 6 (structural induction) and the answers

You should know about divisability, prime numbers, greatest common divisor, and the properties these concepts have. You should be able to prove basic properties for these.

You should know about congruences ("kongruensräkning"), know what calculation steps can be made when dealing with congruences (when we can add/substract/multiply/divide on either side). You should be able to prove these properties.

You should be able to compute the following things, and be able to show how you computed them, using methods that we have used in the course:

• Given two integers a and b, compute the integer division ("heltalsdivision") and remainder ("rest") when dividing a by b.

• Given two integers a and b, compute their greatest common divisor (gcd, or "sgd") using Euclids method.

• Given two integers a and b, compute one integer solution to ax + by = gcd(a,b) using the Pulverizer / Bezouts method. You should also be able to compute all solutions.

• Given three integers a, b, c, investigate what solutions exist to the diophantine equation ax + by = c by computing gcd(a,b) and using the Pulverizer / Bezouts method. You should also be able to compute all solutions.

• Given two integers a and b, and two integers m1 and m2 such that gcd(m1,m2)=1, compute one x such that x ≡ a (mod m1) and x ≡ b (mod m2), using the Chinese remainder theorem ("kinesiska restsatsen"). You should also be able to compute all solutions.

• You should also be able to compute solutions to the Chines remainder theorem that involve more than 2 congruences.

RSA cryptography as such is not part of the exam. But: you should be able to understand how all the material above is used in RSA cryptography; you don't have to be able to reproduce it yourself.

Book: Sect. 9.1, 9.2, 9.3, 9.4, 9.6, 9.7, 9.9.

Euklides and Bezout (pdf)

exercises week 5 (arithmetic) and the answers

You should know what an undirected (simple) graph is. You should know the definition of degree ("gradtal"), walk ("väg"), path ("enkel väg"), closed walk ("sluten väg"), cycle ("cykel"), simple path ("enkel väg"), simple cycle, connectedness ("sammanhängade"), tree ("träd"), and know and be able to prove basic properties of these.

You should know when a graph has an Euler tour, and be able to find an Euler tour for a given graph.

You should know how to prove things about graphs, walks, paths, etc. by induction on the number of nodes and/or number of edges in the graph.

You should know what a directed graph is, about indegree and outdegree, and what a walk, path, closed walk, and cycle is in a directed graph.

You should know what a topological order of a directed graph is. You should know when a graph has a topological order and when not. You should be able to compute topological orders for a given graph.

Book: Sect. 10.1, 10.2, 10.4, 10.5. Sect. 12.1, 12.7, 12.8, 12.9.

Topologisk ordning (pdf)

exercises week 7 (graphs) and the answers

You should know the additive, multiplicative, subtractive, and divisive principle, and how to apply these to calculate numbers of possibilities.

You should know how to count permutations and combinations (the choose ("över") function). And know when these should be applied and how.

You should know basic probability theory: number of possibilities we want / total number of possibilities.

You should know about Pascal's Triangle, the law associated with it, and the binomial coefficients.

You should understand and be able to reproduce how to compute the numbers in the birthday paradox.

You should know about the Pigeon Hole Principle ("hålprincipen") and be able to apply it in reasoning.

Book: Ch. 15.

Kombinatorik (pdf)

Haskell code for combinatorics (.hs)

exercises week 8 (combinatorics)

• The exam questions will be asked in Swedish.

• You may take one A4 sheet of paper with handwritten notes on one side only. You have to submit these notes together with your answers.

• You may use an accepted electronic calculator. Accepted calculators are: Casio FX-82..., Texas TI-30... and Sharp, EL-W531... (There are calculators that can be borrowed on the spot, but it is not sure that there will be enough for everybody.)

• You may not take a text book with you.