[home]

Výroková a predikátová logika (2023/2024)

Cvičení k přednášce Výroková a predikátová logika

Organizace

K získání zápočtu je třeba získat celkem 120 bodů. V průběhu semestru budou dva zápočtové testy, každý na 45 minut. První (zhruba v polovině semestru) bude pokrývat část přednášky "Výroková logika", druhý (ke konci semestru) část přednášky "Predikátová logika". Za každý z testů lze získat maximálně 100 bodů. Kromě toho lze získat maximálně 20 bodů za aktivitu na cvičeních (tj. úspěšné vyřešení nebo rozumný pokus o vyřešení nějakého příkladu).

Na konci semestru bude možnost opravit si výsledek *horšího z těchto dvou testů* napsáním opravného testu. Termín by měl být v prvních dvou týdnech zkouškového období. Žádné další opravné možnosti nebudou. Pokud student zamešká některý z řádných testů ze zdravotních důvodů, může si tento také nahradit napsáním opravného testu.

Účast na cvičeních není povinná, nicméně je velice doporučovaná, protože se na cvičeních většinou dozvíte užitečné rady, které vám usnadní řešení zápočtových písemek.

Co bylo probráno

Zde bude krátké shrnutí každé hodiny včetně PDF se zadáním příkladů.

04.10.

• Pozor! První cvičení odpadá.

11.10.

• Úvod. Vyjadřování různých vlastností ve výrokové a predikátové logice.
• Příklady
• Matematické pojmy vhodné k zopakování.

18.10.

• Sémantika výrokové logiky (Booleovské operátory, pravdivostní tabulka, tautologie, modely, důsledky). Univerzálnost logických spojek.
• Příklady

25.10.

• CNF, DNF, počítání výroků až na ekvivalenci, 2-SAT, Horn-SAT, algoritmus DPLL, kódování problémů do SAT.
• Příklady
• Ukázka SAT solveru pro barvení grafu

01.11.

• Návrat k DPLL, tablo metoda
• Příklady

08.11.

• Opakování probraných témat.
• Příklady

15.11.

• Rezoluce ve výrokové logice. Aplikace věty o kompaktnosti. Hilbertův kalkulus.
• Příklady

22.11.

• 1. test na 45 minut. Maximální možný počet bodů je 100.
• Příklady - zbytek z minulého cvičení.

29.11.

• Řešení příkladů z testu. Syntaxe a sémantika predikátové logiky.
• Příklady

6.12.

• Struktury a podstruktury. Extenze teorií. Tablo metoda v PL.
• Příklady

13.12.

• Tablo metoda v PL.
• Příklady

20.12.

• Převod do PNF. Skolemizace.
• Příklady

3.1.

• Unifikace. Rezoluce v PL.
• Příklady

10.1.

• 2. test na 45 minut. Maximální možný počet bodů je 100.