Zadanie

Zadanie - 20 bodov

Zadanie pozostáva z viacerých kreatívnych úloh zameraných na overenie celkového pochopenia danej problematiky. Zadanie je možné rozdeliť do 3 tematických okruhov:

• Výroková logika.
• Predikátová logika.
• Ďalšie logické systémy.

Výroková logika

Vašou úlohou v rámci tejto časti zadania, bude vymyslieť vetu (alebo sylogizmus) v prirodzenom jazyku, ktorú prepíšete do formuly jazyka výrokovej logiky.

• Formula musí byť tautológia a bude obsahovať minimálne 4 výrokové premenné (elementárne výroky) a minimálne 5 logických spojok (z toho aspoň 4 binárne) a následne:
• Zostrojte strom abstraktnej syntaxe formuly.
• Vypočítajte veľkosť formuly.
• Vypočítajte množinu všetkých podformúl formuly.
• Pomocou tabuľky pravdivostných hodnôt overte, že formula je tautológia.
• Dokážte formulu pomocou naturálnej dedukcie.
• Dokážte formulu pomocou sekventového kalkulu.
• Dokážte formulu pomocou rezolučnej metódy.

Upravte navrhnutú vetu (sylogizmus) v prirodzenom jazyku tak aby bola splniteľná a zároveň nebola tautológia.

• Preložte upravenú vetu do jazyka výrokovej logiky.
• Pomocou tabuľky pravdivostných hodnôt zistite, či upravená formula je splniteľná a zároveň:
• Zostrojte strom abstraktnej syntaxe formuly.
• Vypočítajte veľkosť formuly.
• Vypočítajte množinu všetkých podformúl formuly.
• Nájdite konjunktívny normálny tvar prostredníctvom naivného prepisu.
• Nájdite disjunktívny normálny tvar prostredníctvom naivného prepisu.
• Nájdite úplný konjunktívny normálny tvar.
• Nájdite úplný disjunktívny normálny tvar.
• Nájdite aspoň jeden minimálny konjunktívny normálny tvar.
• Nájdite aspoň jeden minimálny disjunktívny normálny tvar.
• Nájdite konjunktívny normálny tvar formuly pomocou Tseitinovej transformácie.
• Výsledné tvary formuly v konjunktívnom normálnom tvare prepíšte do množinovej notácie (všetky 4).
• Aplikujte algoritmus DPLL na množiny klauzúl (všetky 4) z predchádzajúceho bodu a nájdite model formuly.

Predikátová logika

Navrhnutú vetu v prirodzenom jazyku rozšírte o vlastnosti, ktoré je možné opísať predikátmi, funkčnými symbolmi a kvantifikátormi (resp. navrhnite novú).

• Formulujte univerzum (doménu, svet) v ktorom bude platiť Vami navrhnutá formula a definujte jeho sémantiku príslušným modelom.
• Prepíšte túto vetu do formuly jazyka predikátovej logiky. Vetu modifikujte tak, aby výsledná formula obsahovala aspoň 3 predikátové symboly (z toho min. jeden binárny), 2 funkčné symboly, 4 konštanty.
• Ukážte, že formula je platná Vašom modeli.
• Definujte ďalšie formuly predikátovej logiky pre Váš model (aspoň 4) a ukážte ich (ne)platnosť.

Upravte formulu výrokovej logiky (z prvej časti zadania) na formulu predikátovej logiky (pridaním predikátov, funkčných symbolov a kvantifikátorov), tak aby vzniknutá formula predikátovej logiky bola taktiež tautológia.

• Dokážte formulu prirodzenou dedukciou.
• Dokážte formulu sekventovým kalkulom.
• Dokážte formulu rezolučnou metódou.

Napíšte program logickej paradigmy tak, že bude obsahovať:

• 10 faktov,
• 5 pravidiel.

Formulujte 5 cieľov a dokážte ich platnosť/neplatnosť prostredníctvom SLD-rezolúcie.

Neklasické logické systémy

V tejto časti zadania bude Vašou úlohou použiť, resp. modifikovať Vami navrhnutú vetu, resp. formulu z prvej časti zadania pre preberané neklasické logické systémy.

Intuicionistická logika

• Vymyslite Kripkeho model v intuicionistickej logike a ukážte platnosť Vašej formuly z prvej časti zadania (min. 4 svety a 3 relácie dosiahnuteľnosti).
• Pokúste sa formulu dokázať prirodzenou dedukciou.
• Pokúste sa formulu dokázať sekventovým kalkulom.
• Bonusová úloha – previesť formulu intuicionistickej logiky do termu λ-kalkulu (Curry-Howardov izomorfizmus).

Lineárna logika

• Prepíšte formulu do formuly lineárnej logiky a pokúste sa ju dokázať pomocou sekventového kalkulu.

Modálne logiky

• Prepíšte formulu do jednej z modálnych logík (pridajte do formuly aspoň dve modálne operátory).

• Vymyslite Kripkeho model v príslušnej modálnej logike a ukážte platnosť formuly (min. 4 svety a 3 relácie dosiahnuteľnosti).

Forma odovzdania

Vypracované zadania vás poprosím odovzdať do konca 12. týždňa semestra v systéme moodle v kurze LPI.

Zadanie je možné vypracovať dvoma spôsobmi:

• Využitím typografického systému LaTeX (max. 20 bodov).
• Ručne s možnosťou získania max. 13 bodov.

Zadanie v úvodnej časti bude obsahovať:

• titulnú stranu,
• súhrn rozsahu vyriešených úloh (obsah).

Forma odovzdania:

• V prípade zvolenia 1. možnosti poprosím odovzdanie vypracovaného zadania spolu so zdrojovými kódmi. Spôsob vypracovania je voľný, t.j. môžete použiť ľubovoľné balíky typografického systému LaTeX pre vizualizáciu jednotlivých úloh.
• V prípade voľby 2. možnosti Vás poprosím o odovzdanie zadania vo forme jedného pdf súboru.

Obhajoba zadania bude prebiehať v 13. týždni.