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.

27.1.2010 - Mlček

Příspěvekod Jookyn » 27. 1. 2011 14:34

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á.
Jookyn
Matfyz(ák|ačka) level III
 
Příspěvky: 115
Registrován: 13. 9. 2008 20:42
Typ studia: Informatika Mgr.
Login do SIS: 80320124

Re: 27.1.2010 - Mlček

Příspěvekod marion » 27. 1. 2011 17:24

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.
marion
Matfyz(ák|ačka) level II
 
Příspěvky: 69
Registrován: 4. 10. 2008 10:05
Typ studia: Informatika Mgr.
Login do SIS: 36138549

Re: 27.1.2010 - Mlček

Příspěvekod Jookyn » 27. 1. 2011 18:47

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ě...
Jookyn
Matfyz(ák|ačka) level III
 
Příspěvky: 115
Registrován: 13. 9. 2008 20:42
Typ studia: Informatika Mgr.
Login do SIS: 80320124

Re: 27.1.2010 - Mlček

Příspěvekod Návštěvník » 29. 1. 2011 20:57

Možná hloupej dotaz, ale dá se to udělat úplně bez důkazů (pokud člověk průměrně napíše písemku..)?
Návštěvník
 

Re: 27.1.2010 - Mlček

Příspěvekod Jookyn » 29. 1. 2011 21:34

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ů...
Jookyn
Matfyz(ák|ačka) level III
 
Příspěvky: 115
Registrován: 13. 9. 2008 20:42
Typ studia: Informatika Mgr.
Login do SIS: 80320124


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 1 návštěvník

cron