Propositional and Predicate Logic,
at the College of Mathematics and Physics, discussion sessions to Petr Stepanek's course
for students of Theoretical Computer Science
Cvičení
jsou většinou vzata z knihy Švejdar nebo
z učebního textu Hájek-Švejdar.
Ukázkové písemky z minulých let:
p99a.pdf,
p99b.pdf,
p01a.pdf,
p07a.pdf,
p07b.pdf.
Poslední písemka:
p08aX.pdf,
p08bX.pdf.
- 7. října 2008
- Pravdivostní hodnoty a pravdivostní ohodnocení, tautologie
a splnitelné formule, vyplývání čili (tautologický) důsledek,
ekvivalentní formule, konjunktivní a disjunktivní normální tvar.
D. cv.: (1) Zdůvodněte, že B vyplývá z Δ,A, právě když implikace
A→B vyplývá z Δ,
(2) zdůvodněte, že A vyplývá z Δ,
právě když Δ,¬A je nesplnitelná,
(3) zdůvodněte, že úloha HORNSAT
je polynomiálně rozhodnutelná. Viz kniha str. 116-117.
- 14. října 2008
- Rezoluční algoritmus pro úlohu SAT. Podúlohy úlohy SAT, které
jsou polynomiálně rozhodnutelné: HORNSAT a 2SAT. Hilbertovský kalkulus pro
klasickou výrokovou logiku, první kroky.
D. cv.: Rozmyslete si, že úloha CNFSAT je převeditelná na úlohu 3SAT.
Návod je v knize str. 135 cv. 16.
- 21. října 2008
- Dokazování dokazatelnosti formulí v hilbertovském kalkulu s užitím
věty o dedukci. Souvislosti mezi (silnou) korektností, úplností,
silnou úplností a kompaktností.
D. cv.: Zdůvodněte dokazatelnost formule (B→A)→((¬B→A)→A).
- 4. listopadu 2008
- Alternativní důkaz věty o úplnosti pro výrokový kalkulus.
Tříhodnotová sémantika.
D. cv.: Zdůvodněte pomocí tříhodnotové sémantiky, že kdybychom schéma A3 nahradili schématem
(A→B)→(¬B→¬A), pro výsledný kalkulus by neplatila
věta o úplnosti vůči klasické dvouhodnotové sémantice, protože původní schéma A3
by nebylo dokazatelné.
- 11. listopadu 2008 (suplování)
-
Základy sémantiky predikátové logiky. Tarského definice.
- 25. listopadu 2008
-
Opakování Tarského definice. Splněnost formule ve struktuře určitým ohodnocením.
Pravdivost formule ve struktuře, logicky platné formule.
D. cv.: Cvičení 2 str. 135 v knize.
- 2. prosince 2008
- Příklady na logicky platné formule. Korektnost pravidel generalizace. Definice vyplývání.
- 9. prosince 2008
- Příklady na vyplývání. Dokazatelnost v predikátovém hilbertovském kalkulu.
- 16. prosince 2008
- Dokazatelnost v predikátovém hilbertovském kalkulu. Příklady na sémantiku
výrokové logiky vzaté ze starších písemek.
- 18. prosince 2008, zápočtová písemka
- Hodnocení příkladů a zapisování zápočtů
Za každý ze čtyř příkladů v písemce bylo možno získat 3 body,
k úspěchu stačilo 7 bodů.
Zápočet získaný na základě písemky
si dosud nevyzvedl:
Pavol Bellák.
Další postup
Kdo z mých (!) studentů nepsal písemku nebo u ní neuspěl, může zápočet získat
na základě domácího úkolu, který spočívá v bezchybném
vyřešení všech úloh z obou letošních i loňských písemek, tj. ze souborů
p07a, p07b, p08aX a p08bX.
Domácí úkol si prosím připravte tak, abyste mi
mohli bez váhání vysvětlit (tj. nikoliv předložit)
řešení některých namátkou z něj vybraných úloh.
V případě neúspěchu
má každý nárok na jeden (!) opravný termín.
Domácími úkoly a udělováním zápočtů se budu zabývat pouze v předem
vyhlášených termínech, tj. v konzultačních hodinách, avšak již udělené zápočty
zapisuji kdykoliv (podle časových možností).
Konzultační hodina Čt 14:00 platí i ve zkouškovém období.
- 6. ledna 2009
- Věta o úplnosti. Vlastnosti axiomatických teorií: bezespornost a úplnost.
- 13. ledna 2009
- Dokazatelnost v Peanově a v Robinsonově aritmetice.
|