Matfyz Wiki
byl trochu zmatek v zadavani, nekteri meli malo prikladu, takze bylo vice ruznych zadani, uvedu zde me, ktere bylo oznacene jako varianta A
1) definujte CNF a DNF tvar formule
a) jsou CNF a DNF tvary teze formule ekvivalentni? proc? (1 bod)
b) v jednom z techto tvaru lze definovat postacujici podminku, aby formule byla tautologii - v kterem tvaru? jak podminka bude vypadat? (4 body)
2) T a S vyrokove teorie, oznac MOD(T) jako mnozinu vsech modelu teorie T, analogicky pro S, dokazte:
a) T je podmnozinou S => MOD(S) je podmnozinou MOD(T) (2 body)
b) <= neplati (3 body)
3)
a) dokazte, ze kazda uplna vyrokova teorie ma jen jeden model (5 bodu)
b) sestrojte uzavrenou vyrokovou teorii, ktera neni uplna (asi take 5 bodu)
4)
a) definujte pojem uplne teorie (1 bod)
b) dokazte, ze libovolna bezesporna teorie T (jazyk L) a libovolny jeji model M - mnozina THM(M) = {A | A je uzavrena fle jazyka L pravdiva v M} je uplna teorie, ktera je rozsirenim T se stejnym jazykem (9 bodu)
5)
a) definujte pojem varianty formule (2 body)
b) dokazte, ze kazde 2 varianty dane formule A jsou ekvivalentni (8 bodu)
6) v Peanove aritmetice dokazte (axiomy byly vypsany)
a) 1 * 2 = 2 (3 body)
b) (Vx)(Vy)(S(y) * x = (x * y) + x) (7 bodu)