du01

Domáca úloha 1

Domácu úlohu odovzdávajte do Štvrtku 27.3. 9:55 (t.j. najneskôr na začiatku prednášky).

Úlohu odovzdávajte buď fyzicky na papier formátu A4 (čitateľne označenom a podpísanom) na prednáške alebo na cvičeniach, alebo elektronicky vo formáte PDF (ako súbor du01.pdf) alebo ako obyčjaný textový súbor (du01.txt) do vetvy du01. Môžete odovzdať aj oskenované/odfotené papierové verzie ako súbor du01.jpg alebo du01.png, ak sú dostatočne čitateľné (dostatočné rozlíšenie, kontrast, v oskenovanej verzii sa škaredé písmo trochu ťažšie lúšti,...). Nezabudnite vyrobiť pull request.

Bohužiaľ cez webové rozhranie sa na github dajú súbory len priamo písať alebo copy-paste-ovať, binárne súbory treba nahrať pomocou GIT-u (msysgit alebo čistý git) alebo github programu pre windows respektíve pre Mac.

Github pre windows/mac je vcelku jednoduchý: stačí nainštalovať, zadať meno a heslo, naklonovať svoj repozitár, prepnúť správnu vetvu, nahrať do správnych adresárov súbory, commit-núť a nahrať na server (v tomto programe to volaju "sync/synchronize branch"). Samozrejme potom treba ešte (cez webová rozhranie) vyrobiť pull request.

1.1 (1b)

Shefferova spojka (NAND) , značka: ↑, je binárna logická spojka s nasledovným významom:

• A ↑ B je pravdivé vtt keď aspoň jedno z A alebo B je nepravdivé.

Vybudujte teóriu výrokovel logiky používajúcej iba túto spojku: zadefinujte pojem formuly, vytvárajúcej postupnosti a stromu pre formulu, boolovského ohodnotenia.

1.2 (1b)

Hovríme, že binárna logická spojka ◊ je definovateľná zo spojok α, β... ak existuje formula, obsahujúca iba spojky α, β,... a premenné a a b, ekvivalentná formule (a ◊ b).

Hovríme, že unárna logická spojka ◊ je definovateľná zo spojok α, β... ak existuje formula, obsahujúca iba spojky α, β,... a premennú a, ekvivalentná formule ◊ a.

Napríklad → je definovateľná z ¬ a ∨ pretože (a→b) je ekvivalentná s (¬a∨b) (samozrejme ekvivalenciu tých dvoch formúl by bolo treba ešte dokázať).

Dokážte, že

• ↑ je definovateľná zo spojok ¬, ∧ a ∨;
• ¬, ∧, ∨, → sú definovateľné z ↑.

1.3 (1b)

Uvažujme naslednovnú definíciu:

Formula X je symetrická v a a b, kde a a b sú premenné, vtt keď pre každé boolovské ohodnotenie v platí: nech v' je boolovské ohodnotenie také, že * v'(a) = v(b); * v'(b) = v(a); * v'(x) = v(x) pre ostatné premenné rôzne od a a b, potom v(X) = v'(X).

Dokážte, že:

• ak X neobsahuje ani a ani b, tak je symetrická v a a b
• ak X je symetrická v a a b, tak je symetrická v b a a
• ak X nie je symetrická v a a b, tak X nie je tautológia