Výroková a predikátová logika

V tomto semestru učím pouze anglickou verzi cvičení. Informace zde byly naposledy relevantní v roce 2022/2023.

Cvičení probíhají ve čtvrtek v 9:00 v S6 a ve čtvrtek ve 12:20 v S11. Obě cvičení se budu snažit držet přibližně synchronizovaná.

Požadavky na zápočet

Zápočet bude udělen za získání 120 bodů za semestr. Body lze získat třemi způsoby:

Co to znamená býti aktivní? Hlavním cílem je vás motivovat k tomu, abyste se ptali nebo odpovídali na mé otázky, aktivita je tedy definována celkem široce, např. vyřešení příkladu, odpověď na otázku (nezávisle na správnosti, pokud se snažíte správně odpovědět), nebo i položení otázky týkající se probírané látky (na cvičení, nebo i mimo cvičení mailem/zprávou na MS Teams, apod.).

Domácí úkoly

  1. k-obarvitelnost a SAT - termín 31. října 2022 večer, detaily jsou v přiloženém zipu
  2. Výroková logika - termín 10. listopadu 2022 před cvičením, detaily v pdf
  3. Predikátová logika - termín 22. prosince 2022 před cvičením, detaily jsou v přiloženém pdf

Příklady ze cvičení

Na cvičení budeme používat především příklady z webů cvičení Petra Gregora a Jakuba Bulína. Odkazy na příklady níže se týkají právě jich, pro cvičení Petra Gregora používám zkratku PG, pro Jakuba Bulína JB.

Datum Téma
29. 9. 2022 Úvod, syntaxe vs sémantika, výrokové formule, vyjadřování formulemi (příklady 1.cv PG - 1, 2a, 3a, 6)
6. 10. 2022 Vyjadřování v logice, splnitelnost, modely, univerzálnost spojek (příklady 0.cv JB - 1, 2; 1. cv JB - 7; vytvoření CNF a DNF z tabulky)
13. 10. 2022 Převody do CNF/DNF, sémantické pojmy ve výrokové logice ( příklady 2. cv JB - 1, 2, 3)
20. 10. 2022 Počítání počtu prvovýroků až na ekvivalenci, problém SAT, solver glucose (příklady 3. cv JB - 1, ukázka SAT solveru ze zadání úkolu)
27. 10. 2022 2-SAT, HornSAT, DPLL, tablo metoda ve výrokové logice (příklady 3. cv. JB - 2,3,4, + 5. cv. JB - 1ac)
3. 11. 2022 Tablo metoda ve výrokové logice (příklady 5. cv. JB - 1,2,3,4,5)
10. 11. 2022 Rezoluce ve výrokové logice (příklady 6. cv. JB - 1,2,3)
24. 11. 2022 1. test - Výroková logika, Syntaxe predikátové logiky (příklady 7. cv. JB - 1-3)
1. 12. 2022 Sémantika predikátové logiky (příklady 7. cv. JB - 4,5,8 + 8. cv. JB - 1)
8. 12. 2022 Struktury a podstruktury, extenze teorií (příklady 8. cv. JB - 2,3,4)