Course - Logic and Proof MT24


This course covers topics in logic and proof from a computer science perspective. The start of the course covers some problems in propositional logic, such as compactness, proving that the $\mathsf{SAT}$ problem for some classes of formulas can be solved in polynomial time, and that simple resolution proofs can lead to exponentially long refutations. Then the course moves onto topics in first-order logic, such as Ehrenfeucht-Fraïssé games and looking at decidable theories. Then it finally covers the compactness of first-order logic and shows that the satisfiability and validity problem for first-order logic is actually undecidable.

Notes

Problem Sheets

To-do List

Previous course materials

The course was a bit different in previous years since there was no introductory [[Prelims]]U logic course.




Related posts