Informatique fondamentale

• Boolean logic: syntax, semantics, satisfiability testing algorithms, natural deduction, resolution.

• Problem reduction, particularly reduction to the Boolean satisfiability problem, and the use of SAT solvers.

• First-order logic: syntax, semantics, resolution, natural deductin, problem modeling in first-order logic, and use of solvers.

• Finite automata and regular expressions.
  
  Limits on the automatic/algorithmic reasoning in logic.

---

This course aims to familiarize students with the fundamental concepts of computer science: logic and its applications, proof systems, problem reduction, complexity, computability, computational models, program correctness. The course provides a general introduction to these notions and does not replace more advanced Master-level courses, particularly those on computability and complexity.
For problem reduction, the course will focus especially on the Boolean satisfiability problem, for which many solving tools exist.

By the end of this course, students should:

• Understand the basic notions covered,

• Be able to model and formalize concrete computer science problems, especially in logic,

• Be able to formalize mathematical properties,

• Master classical deduction rules for proof formalization.

Required and Corequired knowledge and skills

Basic notions of algorithmic (sorting algorithms, graph algorithms such as graph traversals) and programming (in Python).

Cours co-requis

Cours ayant celui-ci comme co-requis

• Lectures and exercises.

References, bibliography, and recommended reading

Université Virtuelle (slides given by the teacher)

Course notes

• Université virtuelle

Contacts

efiliot@ulb.be

Campus

Plaine

Method(s) of evaluation

• Other

Other

Written exam.

 

Language(s) of evaluation

• french