[zkouska] Mlcek 10. 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.
peci1
Matfyz(ák|ačka) level II
Příspěvky: 86
Registrován: 21. 1. 2009 20:08
Typ studia: Informatika Bc.

[zkouska] Mlcek 10. 2.

Příspěvek od peci1 »

Ahoj, vzal jsem si tezkou otazku (co meli ostatni za otazky, to netusim).
Dostal jsem zkoumat teorii T=Th\left(\langle(0,1) \subset \mathbb{R}, \leq^\mathbb{R} \rangle \right)
Po chvili premysleni jsem dospel k zaveru, ze tahle teorie bude ekvivalentni s DeLO. (A taky pry opravdu je, ale to se mi nepovedlo dokazat - nicmene to nevadilo).
Tedy zbytek "vyzkumu" uz bylo obycejne DeLO (bez koncu, protoze (0,1) je otevreny interval).
Myslim, ze kdybych mel zkoumani teorie v poradku, tak by se me snad uz ani na nic dalsiho neptal a odesel bych s jednickou.
Bohuzel jsem mu "dokazal", ze T nema elim.kv., i kdyz spravne je, ze ji ma. To Mlcka moc nepotesilo, a tak mi dal dokazat, ze z elim.kv. plyne modelova kompletnost. Jak tady uz zaznelo, clovek si muze jit sednout a promyslet to, ale po nekolika minutach se asi nudil, a tak mi rekl, at uz mu to jdu predvest. Dukaz jsem mel skoro cely, chybel jeden krok - navrhnul mi dvojku.
Rikal jsem si, proc to nezkusit rovnou na 1 (krom toho, ze jsem byl mega stastnej, ze to vubec mam :) ).
Tak se me zeptal na jeden silne nerozhodnutelny a jeden rozhodnutelny model teorie teles. Ten silne nerozhodnutelny je zcela urcite standardni \mathbf{Q}, a rozhodnutelny je nejaky model teorie uzavrenych teles (to uz jsem ale nevymyslel, takze jsem odesel s dvojkou).

Co jsem tak videl, tak dva lidi prede mnou meli za 3, jeden za 2 (sel jsem v druhe pulce od jedenacti). Z prvni pulky si toho moc nepamatuju, ale ctyrek tam moc nebylo ;)
vidlak
Matfyz(ák|ačka) level I
Příspěvky: 20
Registrován: 10. 1. 2008 23:19
Typ studia: Informatika Bc.

Re: [zkouska] Mlcek 10. 2.

Příspěvek od vidlak »

Ahoj, na dnešním termínu sem měl vážně štěstí. Dostal sem množinu prvovýroků P={p,q,r} a teorii T={q, p v r}. Otázky:
a) počet neekvivalentních jednoduchých extenzí teorie T (= počet podmnožin M(T), protože extenze má model vždy podmožinu M(T))
b) počet neekvivalentních nezávislých výroků teorie T (= počet všech neekvivalentních výroků - počet neekvivalentních pravdivých - počet neekvivalentních lživých = 2^(2^l) - 2^(2^l - |M(T)|) - 2^(2^l - |M(T)|) = 2^(2^l) - 2*2^(2^l - |M(T)|) = (2^|M(T)| - 2) * 2^(2^l - |M(T)|) )

Prosil sem o něco jednoduchého, a nic jednoduššího tam asi vážně nebylo. Díky p. Pajasovi za tu otázku. Pak se mě ještě zeptal na něco z teorie, že by mi dal dvojku. Mě to stačilo za 3, takže sem na další otázky neodpovídal

Další kolega si vybral jednoduchou otázku a měl o několika teroiích říct, jestli jsou otevřené (a proč). Dostal za 4. Myslím si, že naše otázky byly co do obtížnosti naprosto neporovnatelné. Holt to chce štěstí na otázku.
Pukii
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 10. 2. 2010 20:29
Typ studia: Informatika Bc.

Re: [zkouska] Mlcek 10. 2.

Příspěvek od Pukii »

Ahoj, dneska na zkousce jsem mel otazku:
Predikatova logika. Predpokladame jazyk s rovnosti.
Urcete, zda-li jsou uvedene teorie ekvivalentni nejake otevrene teorii:
a) DiLO
b) teorie grup <+,-,0>
c) teorie následníka SC
d) T=\{\exists x,y R(x,y)\}, kde R je binarni relacni symbol.

Vyuzil jsem vetu: Pokud \mathcal{A} je model otevřené teorie T, potom i každá podstruktura \mathcal{B} struktury \mathcal{A} je modelem T.
DiLO, nema ekvivalentni otevrenou teorii, protoze pro model <\mathbb{Z},\leq> podstruktura <\mathbb{N},\leq> neni modelem DiLO (nula nema predchudce).
Teorie grup je sama otevrena. Teorii naslednika jsem nevedel, pan Mlcek mi prozradil ze by se pouzila vyse zminena veta. Posledni teorie nema ekv. otevrenou teorii, opet se vyuzije vyse zminena veta, staci vzit libovolny model teorie a pro tento model muzeme vzit podstrukturu, ktera po zuzeni bude mit R=\emptyset, potom nebude modelem T.
Dale se me pan Mlcek zeptal na definici vety o uplnosti v predikatove logice. Nakonec jsem prosel :wink: a jsem velice rad ze to mam za sebou.
Navstevnik

Re: [zkouska] Mlcek 10. 2.

Příspěvek od Navstevnik »

K poslednimu prispevku, mel jsem podobnou otazku, bohuzel jsem to nedal, nebot jsem neznal vyse zminenou vetu, tudis jsem nemel ani paru jak na to... jenom k ty vete bych se chtel zeptat, je z kapitoly o eliminaci kvantifikatoru?(tu uz jsem moc nestihnul). Nebo nejak vyplyva z te stranky kde je definovana otevrena teorie a Skolemova varianta.
Pukii
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 10. 2. 2010 20:29
Typ studia: Informatika Bc.

Re: [zkouska] Mlcek 10. 2.

Příspěvek od Pukii »

No ja si tuto vetu pamatuju z nejake stranky z textu -teorie a jejich aplikace- (aspon mam ten dojem). Ta veta je na te strance se Skolemovou variantou (tj. str. 42) a je to konkretne tvrzeni 3.1.52. 3)
Naposledy upravil(a) Pukii dne 10. 2. 2010 22:47, celkem upraveno 1 x.
Tooomy
Matfyz(ák|ačka) level I
Příspěvky: 10
Registrován: 16. 10. 2008 00:36
Typ studia: Informatika Mgr.
Bydliště: kolej 17.listopadu

Re: [zkouska] Mlcek 10. 2.

Příspěvek od Tooomy »

Já na to dneska taky až od 11. Bylo nás málo a bylo to celkem v klidu...

Šel jsem do lehký otázky a dostal jsem:
a) k-kategoričnost a w-kategoričnost
b) rozhodnutelnost a kompletnost
c) prvomodel a algebraický prvomodel (pokud existují)

A to u těchto teorií:
1) SC (následník)
2) Vektorové prostory nad R
3) DeLO

Řekl jsem mu ve směs všechno správně...Jen mě zarazil, když jsem tvrdil, že z k-kategoričnosti plyne kompletnost (což platí) i rozhodnutelnost (to už ne...) Pak chtěl ode mě příklad nějaký teorie, která je právě kompletní a není rozhodnutelná, což jsem naštěstí vymyslel (vzpomněl jsem si na N, která je silně nerozhodnutelná :-D)

Takže jsem odcházel s 3 po necelých 15 minutách od začátku jako druhý úspěšný a to jsme to ani neprobrali všechno...

Jinak Mlček působil naprosto v klidu a během těch 5 minut zkoušení prohodil snad nejmíň 3 vtipy (Nejlepší bylo, když jsem si sedl a ptám se: "Můžu začít ?" A Mlček: "Můžete všechno, jen ne heilovat..." To mě dostalo úplně nejvíc...:D)

Tak hodně štěstí všem ostatním...:-D
Jebi
Matfyz(ák|ačka) level I
Příspěvky: 4
Registrován: 19. 1. 2009 12:40
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Re: [zkouska] Mlcek 10. 2.

Příspěvek od Jebi »

No já musim říct, že to fakt bylo o otázkách. Osobně jsem totiž uměl sotva základy výrokové a ještě základnější základy predikátové logiky. Od nerozhodnutelnosti dál už jsem nevěděl doopravdy nic. Ale dostal jsem jednoduchou otázku z výrokovky, zodpověděl ji a spokojeně odešel s trojkou. Zkuste tedy na Pajase prostě koukat co nejzoufaleji, jako jsem to udělal já a třeba dostanete také něco podobně lehkého =D

P množina prvovýroků velikosti l, p je prvovýrok z P:
a) určete počet neekvivalentních teorií T takových, že T |- p (v T je dokazatelné p)
b) určete počet neekvivalentních teorií T takových, že T sjednoceno s {p} je sporná teorie

Tu druhou otázku jsem ještě maličko zblbnul, ale opravil jsem to před nim. Pak se mě ještě zkoušel ptát na nějakou teorii, ale neměl šanci.. =D

Snad jen kdyby někdo nevěděl, tak oba výsledky jsou 2^(2^(l-1))

Jinak přeji všem podobně jednoduché otázky, ta logika je fakt zlo..
Odpovědět

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