ZK. 30.6.

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) :shock:
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:)

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ů :twisted:

Vypíšu sem i ty otázky z té "praktické" části - jen typově, všechny ty výrazy si nepamatuji :wink: 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)), ....

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

gASK wrote: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)), ....

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 znamenat :-)

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í :wink: