Zkouška 2.2.2010

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.
Uživatelský avatar
mifeet
Matfyz(ák|ačka) level I
Příspěvky: 14
Registrován: 27. 1. 2010 14:37
Typ studia: Informatika Ph.D.

Zkouška 2.2.2010

Příspěvek od mifeet »

Ahoj,
na dnešní zkoušce byla jako obvykle na výběr lehká a těžká otázka. Pokud vím, tak jsme tam byli dva ze šesti, kdo si vybral těžkou.
Vypadá to, že těžká otázka je obvykla analýza nějaké teorie. Na (možná řečnickou) otázku pana doc. Mlčka, jakou teorii bych měl dostat, jsem odpověděl, že nějakou pěknou jednoduchou - a dostal jsem skutečně tu nejjednodušší, tedy PE (teorie prázdného jazyka s rovností bez axiomů).

Pana Mlčka zajímala
- kompletnost - PE není kompletní, kompletace jsou právě extenze o axiomy "existuje právě n prvků" a "existuje nekonečně prvků"
- rozhodnutelnost - je rozhodnutelná, protože podle předchozího má \Sigma_1 kompletaci
- modelová kompletnost - není modelově kompletní (to mi trochu napověděl), snadno se najde protipříklad - pro struktury A={0}, B={0,1} plati, že obě jsou modelem PE, A je podstruktura B, ale formule (\exists x, y) x
eq y v B platí, ale v A ne, tedy A není elementární podstruktura B
- eliminace kvantifikátorů - nemá (plyne z předchozího)
- izomorfní spektrum - I(k, PE) = 1 pro každé k

Potom se ještě ptal jakými axiomy vyjádřím "existuje nekonečně prvků" (pro každné n přidám \exists x_1,\ldots, x_n (\textstyle{\bigwedge_{0<i<j\leq n}} x_i 
eq x_j)), jaká je definice 1-koexistence, co se změní, když se do PE přidá jeden konstantní symbol (nic, je to konzervativní extenze) a jestli je f-homogenita silnější než 1-koexistence (tipnul jsem si, že jo, snažil se tvářit dostatečně sebevědomě, aby se neptal proč a vyšlo to :) ).
Tohle stačilo na jedničku. U ostatních lidí byla myslím jedna dvojka, jedna čtyřka, zbytek trojky a jeden dělal zkoušku ještě po mně, takže nevím, jak dopadl.

Pokud trochu rozumíte tomu textu o analýze teorií, možná se vyplatí zkusit těžkou otázku. Některé "lehké" otázky mi připadaly těžší. Na druhou stranu jeden kamarád si na rovinu řekl o nějakou jednoduchou otázku z výrokové logiky, opravdu dostal jednoduchý příklad na počet pravdivých a nezávislých formulí dané teorie a stačilo to na trojku.

Tak hodně štěstí u dalších termínů ;)
Acris
Matfyz(ák|ačka) level I
Příspěvky: 20
Registrován: 26. 1. 2010 14:28
Typ studia: Informatika Mgr.
Bydliště: Praha

Re: Zkouška 2.2.2010

Příspěvek od Acris »

V druhé fázi dnešních termínů jsme byli 3 a všichni jsme uspěli. Já jsem nakonec dostala také těžkou otázku, nicméně jsem si nebyla vůbec jistá svými znalostmi a pan Doc. Mlček mi dal (v podstatě též po projevení přání o nepříliš těžkou těžkou otázku) též teorii čisté rovnosti.

Jen doplním dvě drobnosti, jinak jsou mé zkušenosti z dnešní zkoušky v podstatě obdobné, jako psal Honza.
- rozhodnutelnost - je rozhodnutelná, protože podle předchozího má \Sigma_1 kompletaci
Ještě je potřeba, že je \Sigma_1-axiomatizovaná, což je nicméně triviální, když nemá žádné axiomy.
jestli je f-homogenita silnější než 1-koexistence
Tímto myslel podle mně větu 5.2.5.2) (Eliminační kriterium), resp. Poslední poznámku z 5.2.4. Když pro každé \mathcal A \models T, \mathcal B \models T lze každé neprázdné konečné parciální vnoření f modelu A do B bezprostředně prodloužit, je T 1-koexistenční. Tedy f-homogenita implikuje 1-koexistenci. (Která je již ekvivalentní s eliminací kvantifikátorů, ze které zase plyne modelová kompletnost, jak již zde bylo řečeno.)
A pozor na to, pojem f-homogenita není v textu k přednášce definován. Je až na konci textu o analýzách teorií na str. 25 (a to až v tom nejnovějším, kterého jsem si třeba já ke zkoušce nevšimla, že byl updatován).

Pozitivní bylo, že když se na něco pan Doc. Mlček ptal (v rámci doplňujících otázek), mohl si to člověk vždy rozmyslet nejdříve v klidu na papír (i když se jednalo ve výsledku o docela zřejmý fakt) a nebyl to problém (když to pak člověk vymyslel).

Tedy jsme nakonec ještě přispěli Mlčkovi do sbírky jednou jedničkou z těžké, jednou dvojkou a jednou trojkou z lehkých otázek (které ale obsahovaly i části z nerozhodnutelnosti, eliminace kvantifikátorů i analýz teorií). Přeji všem hodně štěstí!
peterblack
Matfyz(ák|ačka) level III
Příspěvky: 153
Registrován: 10. 12. 2006 19:26

Re: Zkouška 2.2.2010

Příspěvek od peterblack »

nechcete napsat nektere ty ostatni lehke co si pamatujete? :)
Pukii
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 10. 2. 2010 20:29
Typ studia: Informatika Bc.

Re: Zkouška 2.2.2010

Příspěvek od Pukii »

Ahoj,
byl jsem na teto zkousce, mel jsem otazku:
Mejme jazyk <c_0,c_1,c_2,c_3> a teorii T=\{c_i
eq c_j\} pro i,j=0,1,2,3 kde i
eq j.
a) Jake ma teorie T izomorfni spektrum?
b) Vyjmenujte vsechny jednoduche kompletni extenze teorie T.
c) Je T rozhodnutelna?
thoth
Matfyz(ák|ačka) level I
Příspěvky: 8
Registrován: 4. 6. 2009 14:32
Typ studia: Informatika Bc.

Re: Zkouška 2.2.2010

Příspěvek od thoth »

viete na to posledne niekto odpovedat?
Odpovědět

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