# 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

- k-colorable graphs and SAT - deadline November 16 (extended from Nov. 9), in the evening, see linked zip for details.
- propositional logic - deadline is November 23 before the tutorials, see the linked pdf for questions
- 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) |