Deciding logical properties of statements and its complexity (2023/24)

The page of the course in USOSweb is here (in Polish) or here (in English).

Course notes

• lecture 1: introduction with amendment starting from page 8
• lecture 2: semantics
• lecture 3: tiling puzzles
• lecture 4: classical propositional logic
• lecture 5: intuitionistic propositional logic
• lecture 6: finite satisfiability in FOL
• lecture 7: satisfiability in FOL
• lecture 8: provability in intuitionistic FOL
• lecture 9: decidable satisfiability - monadic cases of FOL
• lecture 10: decidable satisfiability - fragments starting with existential quantifier (1)
• lecture 11: decidable satisfiability - fragments starting with existential quantifier (2)
• lecture 12: decidability of the logic with one monadic function symbol and equality

Homework

Here is the homework.

Here are additional exercises (PSPACE complexity).

Here are additional exercises (undecidability).

Exam

Here are the exam assignments together with the solutions.

Grading

To get a grade one has to do homework (30%) and exam (70%). PhD students: research homework 50%, exam 50%.

Evaluation of the classes

Please take a while and fill out the survey.