Logic and Sets for CS

2026-2027

Algemene informatie

Vakcode XB_0086
Studiepunten 6 EC
Periode P1
Vakniveau 100
Onderwijstaal Engels
Faculteit Faculteit der Bètawetenschappen
Vakcoördinator prof. dr. W.J. Fokkink
Examinator prof. dr. W.J. Fokkink
Docenten dr. S.R. Dahmen
prof. dr. W.J. Fokkink
Onderdeel van opleiding(en)

Praktische informatie

Voor dit vak moet je zelf intekenen. De inteken- en afmeldtermijnen staan op VU.nl

Onderwijsvorm Werkcollege, Deeltentamen schriftelijk, Hoorcollege
Dit vak wordt in het Engels aangeboden. Omschrijvingen kunnen daardoor mogelijk alleen in het Engels worden weergegeven.

Doel vak

After completing this course, the student can:

  1. express logical statements in propositional and predicate logic (Knowledge and understanding) (Applying knowledge and understanding)
  2. reason about the meaning of such formulas through truth tables and models (Applying knowledge and understanding) (Making judgements)
  3. argue formally whether one formula implies another one, or that they are equivalent (Applying knowledge and understanding) (Making judgements)
  4. reduce a propositional formula to disjunctive or conjunctive normal form (Knowledge and understanding) (Applying knowledge and understanding)
  5. express propositional formulas in logic circuits and OBDDs (Knowledge and understanding) (Applying knowledge and understanding)

Furthermore, the student is able to:

  1. reason about set constructions through Venn diagrams and the algebra of sets (Applying knowledge and understanding) (Making judgements)
  2. construct and interpret formal, graphic, and matrix representations of sets, relations, and functions (Applying knowledge and understanding) (Making judgements)
  3. determine and argue whether: (Applying knowledge and understanding) (Making judgements)
    a. a relation is reflexive, transitive, symmetric, or antisymmetric.
    b. a relation is an ordering relation, equivalence relation, or a function
    c. a function is injective or surjective
  4. construct and interpret compositions of relations (or functions) and their inverses (Applying knowledge and understanding) (Making judgements)
  5. construct a proof by mathematical induction (Applying knowledge and understanding)

Inhoud vak

The sets part of the course starts by introducing the concepts of sets, Venn diagrams, product sets and relations. The student then learns the main characteristics and properties of three particular types of relation: ordering relations, equivalence relations and functions. The sets part concludes with a study of the principle of mathematical induction.

The logic part focuses in the first place on propositional logic: truth tables, boolean operators, functional completeness, logical puzzles, SAT-solving, logic circuits and OBDDs. In addition the student will learn the meaning and use formulas of predicate logic, to express mathematical properties and sentences from natural language.

Aanvullende informatie onderwijsvormen

Every week, there is one lecture and one exercise class for the logic part of the course, and one lecture and one exercise class for the sets part of the course.

Toetsvorm

A written midterm exam (40% of the grade) and a written final exam (60% of the grade). For both the midterm and the final exam, at least a 5.0 must be achieved (and the overall mark must be at least 5.5.).

The resit exam covers all material of the course.

It is not possible to resit only the midterm exam or only the final exam of the course.

Literatuur

All course materials are provided via Canvas.

Aanvullende informatie doelgroep

Bachelor Computer Science (year 1)

Overige informatie

Use of GenAI is allowed, but cautioned against, as generating solutions to exercises may lead to a lack of understanding or misunderstanding.