27.1.2010 - Mlček

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.

27.1.2010 - Mlček

Příspěvek od Jookyn »

Bylo pravděpodobně několik verzí, které se mírně lišily. Požadavek opět na vyřešení 2 příkladů. Úplně si to nepamatuju, takže zadání jen zhruba.

1) množina prvovýroků P velikosti l, teorie T
a) Počet neekvivalentních teorií, pro které platí T |- p
b) Počet neekvivalentních teorií, pro které platí T u {p} je sporná

2) <R> unární relační symbol, teorie T s axiomatikou <R(x)>, A byl model T
a) zjistit jestli platí (existují x,y)(R(x) & R(y) & x != y)
b) T0 je extenze T o axiom x = y, T1 je extenze o axiom (pro všechna x,y)(x = y) (nebo tam byla nerovnost? už nevim...)
- Je T0 ekvivalentní T1?
- Platí T |- x = y <=> T |- (pro všechna x,y)(x = y)?
c) fi = (existuje y)(R(y) & x != y). Měli jsme určit fi(x)(A) - byl tam předpis jak ta množina vypadá, ale už si nevzpomenu

3) Určit u následujících teorií, jestli jsou kompletní
a)
- Robinsonova aritmetika rozšířená o lineární uspořádání a existenci prvočísla (možná bylo to prvočíslo ještě nějak specifikovaný)
- DeLO rozšířená o unární relační symbol
- Teorie čisté rovnosti rozšířená o axiom "existuje nekonečně prvků"
- (už nevim)

b)
- (už nevim)


Přišel s vyhodnocením prvních 8mi písemek, 4 lidi poslal domů rovnou, 4 jsme šli na ústní. Nevim, jestli bylo maximum bodů (2,2,2) nebo (2,3,2), já měl (2,1.5,0) a ještě mi těsně pustil na ústní. Na ústním mi vůbec neukazoval písemku, zadával mi prvnímu a dostal jsem nerozhodnutelnost, tak jsem mu řikal, že nevim, tak se slitoval a dal mi eliminaci kvantifikátorů. Jelikož jsem skripta od str. 60 dál ani nečetl, tak jsem ani tady skoro nic nedal dohromady, tak jsem byl odejit.

Jednomu nabídnul rovnou trojku na základě dobrý písemky, kolega vedle mě dostal tu nerozhodnutelnost, řekl k tomu snad všechno (docela dlouhá diskuze, kdy se Mlček pořád vyptával a snad na všechno dostal odpověď) a dostal výslednou za 2, dalšímu co měl pokud vim taky 3.5 bodu jako já dal extenze - co je jednoduchá, kompletní atd. a ten věděl a dostal za 3. Pak ještě vim, že kolega, co měl 4 body dostal něco docela těžkýho, neřekl nic, ale dostal za 3.

Takže písemka je fakt hodně důležitá.
marion
Matfyz(ák|ačka) level II
Příspěvky: 69
Registrován: 4. 10. 2008 11:05
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: 27.1.2010 - Mlček

Příspěvek od marion »

Tak já též ještě přispěju svými postřehy a dojmy. Písemka měla 2 varianty, ta druhá vypadala pokud si vzpomínám přibližně následovně:

1. Teorie T nad množinou prvovýroků P, zadané axiomy a všechny prvovýroky.
a) Kolik je neekvivalentních dokazatelných výroků teorie T
b) Kolik existuje neekvivalentních P-Teorií S, t.ž. S má právě 2 jednoduché kompletní extenze.

2. Mějme jazyk L = < 0,+,< >, a formuli fi: x<0 -> x<y
a) Je formule fi dokazatelná?
b1) Existuje nějaká varianta fi, která je dokazatelná
b2) máme variantu fi'(y/z). Je fi' ekvivalentni fi ?
c) Máme N^2, hledáme takovou množinu dvojic <a,b>, že |= fi[a,b]

3. Rozhodnout, zda následující teorie jsou kompletní
a1) DeLO bez konců navíc s axiomem c<d & c!=d
a2) Teorie vektorových prostorů nad nekonečným tělesem
a3) Peanova aritmetika
a4) Teorie s rovností rozšířená o axiom "existuje alespon n prvků"

b) Je teorie DiLO ekvivalentní nějaké otevřené teorii?

====================================================
Vždy bylo třeba napsat výsledek a pod to zdůvodnění. Na začátku nám Mlček pověděl, že je třeba mít kompletně 2 příklady, přičemž kompletnost posuzuje on :) Písemka mi nepřišla nijak nezvládnutelná, v zásadě očekávatelné věci. Navíc jsem byla vděčná, že se tam neobjevilo učivo z konce skript. Několik nás tam zatvrdlo hodně dlouho, než jsme byli opraveni. Pak zase někoho poslal domů a někoho pozval na zkoušení. Měla jsem 2, 1.5 a 1 bod. Prý by to mohla být dvojka. Chtěla jsem si nechat zapsat trojku, ale to zcela ignoroval a začal nás zkoušet z eliminace kvantifikátorů. Byla jsem dost mimo a každý něco málo řekl, rozhodně to ale nebylo nic slavného. Tak nám dal všem trojky, s radostí jsme poděkovali a šli.
Jookyn
Matfyz(ák|ačka) level III
Příspěvky: 115
Registrován: 13. 9. 2008 21:42
Typ studia: Informatika Mgr.

Re: 27.1.2010 - Mlček

Příspěvek od Jookyn »

Jinak na Mlčkovo stránkách je dnešní zadání i s vzorovym řešením. Pár věcí co jsem napsal níže jsem si pamatoval nepřesně...
Návštěvník

Re: 27.1.2010 - Mlček

Příspěvek od Návštěvník »

Možná hloupej dotaz, ale dá se to udělat úplně bez důkazů (pokud člověk průměrně napíše písemku..)?
Jookyn
Matfyz(ák|ačka) level III
Příspěvky: 115
Registrován: 13. 9. 2008 21:42
Typ studia: Informatika Mgr.

Re: 27.1.2010 - Mlček

Příspěvek od Jookyn »

Návštěvník píše:Možná hloupej dotaz, ale dá se to udělat úplně bez důkazů (pokud člověk průměrně napíše písemku..)?
Řekl bych, že naprosto v pohodě. Pokud napíšeš nadprůměrně písemku (tak 75% a víc bych řekl), tak ti nabídne trojku rovnou a pokud alespoň tak na těch 60%, tak se tě sice na něco ptá (co jsem tak slyšel od ostatních, tak chce spíš říct, co nějaká ta věc znamená, nějaký souvislosti atd, aby bylo hlavně vědět, že víš co to je a rozumíš tomu a případně to dokážeš použít, ale že by chtěl důkaz jsem ještě nikdy neslyšel), ale podle mě tě skoro nikdy nevyhodí... Když ale projdeš písemkou jen tak tak (jako já), tak mu něco říct musíš, ale podle mě se to stejnak obejde bez důkazů...
Odpovědět

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