15. a 17.2.

Výroková logika, normální tvary formulí, predikátová logika, věty o úplnosti výrokové a predikátové logiky, prenexní tvary formulí, modely teorií 1. řádu. Meze formální metody, Gödelovy věty.
Jookyn
Matfyz(ák|ačka) level III
Příspěvky: 115
Registrován: 13. 9. 2008 21:42
Typ studia: Informatika Mgr.

15. a 17.2.

Příspěvek od Jookyn »

Nebyli jste někdo na zkoušce v těchto termínech? Mlček na stránkách aktualizoval počty o (ne)naplněnosti termínů, ale zadání zkoušek tam nedal, tak by mě zajímalo, jak to bylo obtížný a jestli se tam typově opakovaly nějaký příklady co už byly dřív...
Jitka42

Re: 15. a 17.2.

Příspěvek od Jitka42 »

Já byla 17.2 a přišlo mi to zhruba stejně náročné jako dřív. Byla jsem v liché skupině kde bylo vyhozeno cca jen pod třetinu lidí, když jsem tam byla, tak tam byla jedna dvojka a ostatní trojky, já jsem dostala spíše haluzí jedničku a to i přes to že jsem tam měla nějaké větší chyby (dva podbody příkladů špatně, skoro jsem zapoměla definici elementární podstruktury (mlček mi ji téměř nadiktoval) a rekurzivní kompletace), celkově mi přišel že je moc hodný a když se v tom člověk zhruba orientuje tak mu s hromadou detailů pomůže. Ze sudé skupiny pokud vím tak prošli k ústní 2 lidi z 14 takže dost hrůza. Opravoval to Glivický, ale po té co to rozdal tak ještě většinu lidí přesvědčil že to opravdu blbě mají. Tak nevím jestli byl problém v rozdílu náročnosti písemek nebo co.
Něco málo co si pamatuju:

1A Najděte počet neekvialentních teorií takových, že v nich platí non fi.
pokud l je počet proměných a m počet modelů fi tak je to 2^(2^l-m), protože v T platí non fi <=> M(T)nadmnozita M(non fi)<=> M(T) nadmnozina (M(prazdne)-M(fi)) a pak uz staci jen nakreslit obrazek

1B M(T)={(0,1),(1,0)} najdete fi v CNF takove ze je ekvivalenti teorii T
No musi mit stejne modely tak je to zjevne (p nebo q) a (non p nebo non q)

2 L = < <, c > a v tom teorie ostreho linearniho usporadani a dalsi axiom (existuje x) x < c.
nepamatuju si poradi ani rozhazeni mezi A a B a mozna si i pletu co tam bylo a co ne
1) m je mnozina modelu takove ze pocet prvku pred c je konstanti. Je m axiomatizovatelne?
NE, protoze pro kazne konecne n existuje model velikosti n a tedy kdyby mela axiomatiku tak podle nejake vety ma i nekonecny model, ale ten mit nemuze.
2) má T eliminaci kvantifikatoru?
NE, neni modelove kompletni vemte si temer libovolny model a uriznete to co je pred c, pak je to podstruktura ale neni to elementarni podstruktura
3) je model <Z - {-1,-2,-3},< > elementarni podstruktura < Z ,< >
NE, protoze treba (existuje x ) x je mezi y a z neplati pri ohodnoceni y=-4 z=0 v prvnim modelu, ale v druhem plati
4) pridame axiom existuje nekonecne mnoho prvku. Je kompletni?
NE, nezavisla formule je treba axiom hustoty
5) kdyz A je nekonecny model Tsjednoceno{existuje nejmensi prvek}, pak existuje B nekonecna podstruktura a tak ze B neni model A.
NE za A zvolim uzavreny interval <0,1> a c realizuju jako 1 pak kazda nekonecna podstruktura je model T.
6) neco na co se odpovedelo ano asi jestli je nejaka formule nezavisla

3 teorie jedne konstanty
1) je kombletni?
NE, nerozhodnutela formule napr 'existuje 42 prvku'
2) T ma spocetne kompletnich extenzi.
ANO jsou to 'existuje k prvku' a 'existuje nekonecne prvku' a jsou vsechny, potoze kdyby byla jina tak se podival na velikost jejiho modelu a najdu izomorfizmus s nejakou uz popsanou
3) kdyz pridam axiom nekonecna tak je otevrena
NE protoze ma podstrukturu ktera je konecna
4) kolik mnozin lze vygenerovat v <Z,1>?
4 je videt ze je f-homogeni a tak ma eliminaci kvantifikatoru. atomicke formu jsou x=x y=x x=c a ty vygeneruji nic,Z,1 no a bulovskymi upravami dostaneme jeste Z-1

jesti si jeste nekdo vzpomenete na dalsi zadani tak dodam reseni...
Odpovědět

Zpět na „AIL062 Výroková a predikátová logika“