Pamatuje si nekdo otazky teoreticke casti? Jak moc se podobaly te minule apod..
Ja jsem vypadl v prvnim kole, bylo to vesele - overovani platnosti nejakych modelu (pamatujete si to nekdo presneji s tim lichym cislem a x > y?, byly tam snad 4 spravne odpovedi, to jsem moc nepochytil)
a krome jiz zmineneho prevazne dokazatelnost u predikatove logiky (sachy s kvantifikatory, prenexni formule), splnitelnost a vzpominam si na sadu otazek k "y=y <-> x=x" - u toho same krizky:)
ZK. 30.6.
-
- Admin(ka) level I
- Příspěvky: 635
- Registrován: 9. 6. 2005 12:33
- Typ studia: Informatika Mgr.
- Login do SIS: BUREJ3BM
- Bydliště: Konečně Vinohrady:)
- Kontaktovat uživatele:
Moje teoretické otázky skupiny B (bez bodů, ty si nepamatuji):
Edituji to jak si průbežně vzpomínám...
1. Dokažte (A<->B)->[(C<->D)->((AvC)<->(BvD))].
2. Rozepsat zkratky AvB, A&B, A<->B pomocí implikácí a negací a ukázat že to tak je.
3. Dokažte (A & B) v (A & C) <-> (A & (B v C) ).
4. Napište pravidla pro převod do prenexního tvaru a jedno z nich dokažte (resp. ukažte že je to ekvivalentí úprava).
5. Dokažte reflexivitu u rovnosti.
6. ???
7. Máme T a její rozšíření T', mají jazyky L a L' a modely M a M'. Co je to redukce a expanze modelu? Co platí pro jazyky? Napište pomocí modelů nutnou podmínku pro to, aby T' bylo konzervativním rošířením T.
8. Dá se každá teorie rozšířit do úplné teorie? Kdy je toto rozšíření konzervativní?
9. Dokažte, že má-li teorie v PL model, je bezesporná.
10. Napište axiomy Peanovy aritemtiky prvního řádu a dokažte ( x != 0 ) -> ( (Ey) x = S(y) ).
Jinak ta první část byla trochu jinak než píšeš a ačkoliv jsem po jejím dopsání byl trochu v šoku, zvládl jsem ji. Pokud jsi to celé četl a rozumíš tomu, není to zas tak takový problém, váhal jsem jen u pár bodíků
Vypíšu sem i ty otázky z té "praktické" části - jen typově, všechny ty výrazy si nepamatuji Varianta D.
1)
A(x, A(x,y)) |= A(x,x) -> A(x,y)
Je formule VL,je formule PL, obsahuje formuli s implikací, jsou dvě formule oddělené znaménkem sémantického důsledku, obsahují symbol dokazatelnosti.
2)
Spousta formulí, vždy jedna v prenexním a jedna v neprenexním tvaru a říci, jedná-li se o prenexní tvar dané formule.
3)
Spousta jednoduchých impikací a ekvivalencí stylu (Ex)A(x) <-> A(x), (Ex)(Vx)A(x) -> (Vx)(Ex)A(x) a určit zda platí v PL či ne.
4)( ( A -> D) -> non B ) -> ( B -> ( A -> D ) )
Je to axiom, věta, splnitelné, tautologie, dokazatelné z {D}.
5)x=x -> y=y
Je axiom rovnosti, je axiom identity, je už-nevím-co, je ekvivalentní fomuli non(x=y)&(y=x)...
6) Platí v PL: T|-A->(Vx)A, Je-li T|-(Ex)A, pak i T|-A a podobné formule které měly prověřit vaši znalost axiomů PL.
7) Je dán model standartní aritmetiky s predikáty A(x) = x je liché a B(x,y) = x < y. Je toto model následujících teorií?
A pod tím něco jako:
(Vx)(A(x)->(Ey)B(x,y)), ....
Edituji to jak si průbežně vzpomínám...
1. Dokažte (A<->B)->[(C<->D)->((AvC)<->(BvD))].
2. Rozepsat zkratky AvB, A&B, A<->B pomocí implikácí a negací a ukázat že to tak je.
3. Dokažte (A & B) v (A & C) <-> (A & (B v C) ).
4. Napište pravidla pro převod do prenexního tvaru a jedno z nich dokažte (resp. ukažte že je to ekvivalentí úprava).
5. Dokažte reflexivitu u rovnosti.
6. ???
7. Máme T a její rozšíření T', mají jazyky L a L' a modely M a M'. Co je to redukce a expanze modelu? Co platí pro jazyky? Napište pomocí modelů nutnou podmínku pro to, aby T' bylo konzervativním rošířením T.
8. Dá se každá teorie rozšířit do úplné teorie? Kdy je toto rozšíření konzervativní?
9. Dokažte, že má-li teorie v PL model, je bezesporná.
10. Napište axiomy Peanovy aritemtiky prvního řádu a dokažte ( x != 0 ) -> ( (Ey) x = S(y) ).
Jinak ta první část byla trochu jinak než píšeš a ačkoliv jsem po jejím dopsání byl trochu v šoku, zvládl jsem ji. Pokud jsi to celé četl a rozumíš tomu, není to zas tak takový problém, váhal jsem jen u pár bodíků
Vypíšu sem i ty otázky z té "praktické" části - jen typově, všechny ty výrazy si nepamatuji Varianta D.
1)
A(x, A(x,y)) |= A(x,x) -> A(x,y)
Je formule VL,je formule PL, obsahuje formuli s implikací, jsou dvě formule oddělené znaménkem sémantického důsledku, obsahují symbol dokazatelnosti.
2)
Spousta formulí, vždy jedna v prenexním a jedna v neprenexním tvaru a říci, jedná-li se o prenexní tvar dané formule.
3)
Spousta jednoduchých impikací a ekvivalencí stylu (Ex)A(x) <-> A(x), (Ex)(Vx)A(x) -> (Vx)(Ex)A(x) a určit zda platí v PL či ne.
4)( ( A -> D) -> non B ) -> ( B -> ( A -> D ) )
Je to axiom, věta, splnitelné, tautologie, dokazatelné z {D}.
5)x=x -> y=y
Je axiom rovnosti, je axiom identity, je už-nevím-co, je ekvivalentní fomuli non(x=y)&(y=x)...
6) Platí v PL: T|-A->(Vx)A, Je-li T|-(Ex)A, pak i T|-A a podobné formule které měly prověřit vaši znalost axiomů PL.
7) Je dán model standartní aritmetiky s predikáty A(x) = x je liché a B(x,y) = x < y. Je toto model následujících teorií?
A pod tím něco jako:
(Vx)(A(x)->(Ey)B(x,y)), ....
Naposledy upravil(a) gASK dne 1. 7. 2006 08:57, celkem upraveno 1 x.
- Hugo
- Donátor
- Příspěvky: 233
- Registrován: 2. 6. 2005 13:31
- Typ studia: Informatika Mgr.
- Bydliště: treti kontejner zleva
- Kontaktovat uživatele:
dik,
nektere veci, jsem pravda rychle vypustli z hlavy, za nepresnosti se omlouvam.
mne hlavne prekvapilo, ze u te posledni casti 1. casti ..bylo tolik spravnych odpovedi (x je liche,x<y) .. Tam byly teorie typu (Vx)(Ey)... -> A(x) ...a urcite tam nebylo napsano neco, z ceho by plynulo, ze pro vsechna prirozena cisla plati, ze jsou licha. Asi mi v tom neco nedochazi, nevim
nektere veci, jsem pravda rychle vypustli z hlavy, za nepresnosti se omlouvam.
mne hlavne prekvapilo, ze u te posledni casti 1. casti ..bylo tolik spravnych odpovedi (x je liche,x<y) .. Tam byly teorie typu (Vx)(Ey)... -> A(x) ...a urcite tam nebylo napsano neco, z ceho by plynulo, ze pro vsechna prirozena cisla plati, ze jsou licha. Asi mi v tom neco nedochazi, nevim
- Dolda
- Matfyz(ák|ačka) level I
- Příspěvky: 37
- Registrován: 2. 2. 2006 14:22
- Typ studia: Informatika Mgr.
- Bydliště: Bohnice
Bylo tam ovšem eště napsaný, že to je model standartní aritmetiky s konstantou 7. Tak to jsem vůbec nepochopil co mělo znamenatgASK píše:6) Je dán model standartní aritmetiky s predikáty A(x) = x je liché a B(x,y) = x < y. Je toto model následujících teorií?
A pod tím něco jako:
(Vx)(A(x)->(Ey)B(x,y)), ....
Born 2 die in Enemy Territory
- Dolda
- Matfyz(ák|ačka) level I
- Příspěvky: 37
- Registrován: 2. 2. 2006 14:22
- Typ studia: Informatika Mgr.
- Bydliště: Bohnice
Moje otázky v 2. části:
- dokažte |- A, pak |- B -> (B -> A) (5b)
- vyslovte a dokažte větu o uzávěru (5b)
- dokažte A<->B B<->C |- A<->C (5b)
- vyslovte a dokažte větu o konstantách (+ k čemu se používá při důkazu pomocí VD) (10b)
- napište a dokažte větu o ekvivalenci (10b)
- napište axiomy Peanovy aritmetiky. Je rozhodnutelná? (10b)
- Zadefinujte konzervativní rozšíření teorie T a dokažte, že pokud T' je konzervativní rozšíření T, pak T je bezesporná <-> T' je bezesporná (10b)
- nějaká sračka s Th(m) - vůbec sem se nechytal (dokázat že něco je úplným rozšířením něčeho či co) (10b)
- Napište a dokažte větu o korektnosti PL (15b)
- Nechť S je maximální bezesporná množina uzavřených flí a A je uavřená fle. Ukažte, že pokud S |- A, pak A [náleží do] S (15b)
Snad jsem se nesplet, přibližně by mělo sedět i bodový ohodnocení
- dokažte |- A, pak |- B -> (B -> A) (5b)
- vyslovte a dokažte větu o uzávěru (5b)
- dokažte A<->B B<->C |- A<->C (5b)
- vyslovte a dokažte větu o konstantách (+ k čemu se používá při důkazu pomocí VD) (10b)
- napište a dokažte větu o ekvivalenci (10b)
- napište axiomy Peanovy aritmetiky. Je rozhodnutelná? (10b)
- Zadefinujte konzervativní rozšíření teorie T a dokažte, že pokud T' je konzervativní rozšíření T, pak T je bezesporná <-> T' je bezesporná (10b)
- nějaká sračka s Th(m) - vůbec sem se nechytal (dokázat že něco je úplným rozšířením něčeho či co) (10b)
- Napište a dokažte větu o korektnosti PL (15b)
- Nechť S je maximální bezesporná množina uzavřených flí a A je uavřená fle. Ukažte, že pokud S |- A, pak A [náleží do] S (15b)
Snad jsem se nesplet, přibližně by mělo sedět i bodový ohodnocení
Born 2 die in Enemy Territory