Výroková a predikátová logika
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:
- domácí úkoly - budou zadány celkem tři úkoly po 5 bodech
- testy - budeme psát dva testy, za každý bude možné získat 100 bodů
- aktivita - můžete získat až 5 bodů za aktivitu - pokud budete aktivní na dvou různých cvičeních, dostanete 1 bod
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
- k-obarvitelnost a SAT - termín 31. října 2022 večer, detaily jsou v přiloženém zipu
- Výroková logika - termín 10. listopadu 2022 před cvičením, detaily v pdf
- 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) |