# 15. a 17.2.

<{ForumPost(poster="Jookyn", timestamp=2011-02-18 00:40:42)}>
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...
<{/ForumPost}>

<{ForumPost(poster="Jitka42", timestamp=2011-02-18 13:16:40)}>
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...
<{/ForumPost}>