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.

Zkouška 2.2.2010

Příspěvekod mifeet » 2. 2. 2010 16:31

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
<br />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 
<br />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ů ;)
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.

Re: Zkouška 2.2.2010

Příspěvekod Acris » 2. 2. 2010 23:41

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í!
Acris
Matfyz(ák|ačka) level I
 
Příspěvky: 20
Registrován: 26. 1. 2010 14:28
Bydliště: Praha
Typ studia: Informatika Mgr.

Re: Zkouška 2.2.2010

Příspěvekod peterblack » 3. 2. 2010 16:55

nechcete napsat nektere ty ostatni lehke co si pamatujete? :)
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ěvekod Pukii » 10. 2. 2010 21:22

Ahoj,
byl jsem na teto zkousce, mel jsem otazku:
Mejme jazyk <c_0,c_1,c_2,c_3> a teorii T=\{c_i
<br />eq c_j\} pro i,j=0,1,2,3 kde i
<br />eq j.
a) Jake ma teorie T izomorfni spektrum?
b) Vyjmenujte vsechny jednoduche kompletni extenze teorie T.
c) Je T rozhodnutelna?
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ěvekod thoth » 12. 4. 2010 16:07

viete na to posledne niekto odpovedat?
thoth
Matfyz(ák|ačka) level I
 
Příspěvky: 8
Registrován: 4. 6. 2009 13:32
Typ studia: Informatika Bc.


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

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 3 návštevníků

cron