Skip to main content

CM1000 Discrete mathematics 8.0 credits

Choose semester and course offering

Choose semester and course offering to see current information and more about the course, such as course syllabus, study period, and application information.

Headings with content from the Course syllabus CM1000 (Autumn 2022–) are denoted with an asterisk ( )

Content and learning outcomes

Course contents

The course contents are divided into mandatory topics and deepening topics. The mandatory topics are all necessary for a passed grade whereas the study of deepening topics can give higher grades. Throughout the course an emphasis on sound mathematical arguments and methods of proof will be present. This means that each area of the course will be a training in sound reasoning applied to the particular subject matter of that area. For example, the study of sets will involve the study of how to prove set formulas.

The mandatory topics are:

* Elementary logic, involving basic logical connectives and the study of sound arguments and methods of proof.

* Introductory set theory, involving basic set operations.

* Functions, in particular used for the articulations of isomorphisms of graphs.

* Basic number theory (divisibility, congruences, prime numbers etc.)

* Graph theory, the isomorphism concept, trees, directed graphs, matrix representations, Eulerian circuits and paths and related properties. The usage of graphs to model properties worth reasoning about and computing possibly involving applications like finding the minimal spanning tree or the shortest path between two nodes in a weighted graph.

* Basic combinatorics including the study of the principle of multiplication, the principle of inclusion and exclusion, the binomial theorem, combinations and permutations.

The deepening topics are:

* Relations including partial orders and equivalence relations, with applications and examples from number theory including the congruence relation.

* More advanced number theory with methods of proof such as mathematical induction possibly with applications in cryptography or similar areas of interest.

* Basic discrete probability theory, event space, conditional events, and independent events.

Intended learning outcomes

After passing the course, the student should be able to

·     formulate basic theorems and definitions of important concepts within discrete mathematics and discuss a selections of proofs and resulting applications.

·     apply theorems and methods within discrete mathematics.

After the course it is expected that the student will have a theoretic foundation that will support further studies in software development.

Course disposition

No information inserted

Literature and preparations

Specific prerequisites

Knowledge corresponding to elementary linear algebra and the calculus of one real variable.

Recommended prerequisites

No information inserted


No information inserted


No information inserted

Examination and completion

If the course is discontinued, students may request to be examined during the following two academic years.

Grading scale

A, B, C, D, E, FX, F


  • RED1 - Oral examination, 3.0 credits, grading scale: P, F
  • TEN1 - Written exam, 5.0 credits, grading scale: A, B, C, D, E, FX, F

Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability.

The examiner may apply another examination format when re-examining individual students.

Opportunity to complete the requirements via supplementary examination

No information inserted

Opportunity to raise an approved grade via renewed examination

No information inserted


Ethical approach

  • All members of a group are responsible for the group's work.
  • In any assessment, every student shall honestly disclose any help received and sources used.
  • In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution.

Further information

Course web

Further information about the course can be found on the Course web at the link below. Information on the Course web will later be moved to this site.

Course web CM1000

Offered by

Main field of study


Education cycle

First cycle

Add-on studies

No information inserted


Johnny Panrike (