# Propositional and Predicate Logic

This year, my logic tutorials take place on Thursdays at 14:00 in the room S6.

### Credit requirements

You need to get 120 points during the semester to get the credit. There are three ways how to get the credit:

• homework assignments - there will be three assignments for 5 points each
• tests - we will write two tests, you can get up to 100 points for each of them
• activity - you can get up to 5 points for activity in the classes - if you are active in two different lessons, you will get a point

What does it mean to be active? The main goal is to motivate you to ask questions and answer my questions. Activity is thus defined quite broadly, e.g. solving and exercise, answering a question (regardless of the correctness of the answer, if you at least try to answer correctly, i.e. you are not just trolling), or even asking a question related to the discussed matter.

### Homeworks

1. k-colorable graphs and SAT - deadline November 16 (extended from Nov. 9), in the evening, see linked zip for details.
2. propositional logic - deadline is November 23 before the tutorials, see the linked pdf for questions
3. predicate logic - deadline is January 4, before the tutorials, see the linked pdf for questions

### Exercises from the seminar

We will mostly use the exercises from Petr Gregor’s seminar.

Date Topic
October 5, 2023 Introduction, syntax vs. semantics, propositional formulas vs first-order and higher-order formulas (PG seminar 1 exercise 1-2, 6)
October 12, 2023 First-order logic formulas, semantics, CNF, DNF (PG seminar 1, ex. 3, seminar 2, ex. 1a), 2)
October 19, 2023 Semantics, 2-SAT (PG seminar 2, ex. 1, 3, 4)
October 26, 2023 Semantic proofs (PG seminar 3, ex. 2)
November 9, 2023 Counting non-equivalent propositions, tableau method (PG seminar 4 ex. 4, PG seminar 5, ex. 1, 2)
November 16, 2023 Extensions of theories, resolution method in propositional logic (PG seminar 4, ex. 5, PG seminar 6, ex. 2,3,5)
November 23, 2023 Tutorials cancelled (dean’s sporsts day)
November 30, 2023 First test (propositional logic), introduction to semantics of predicate logic (PG seminar 7, ex. 4)
December 7, 2023 Semantics of predicate logic (PG seminar 7, ex. 4-6, seminar 8 ex. 1-2)
December 14, 2023 Theories, substructures, elemenary equivalence (PG seminar 9, ex. 3-5)