Zkouska 27. 1.

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.
Matfyz
Matfyz(ák|ačka) level I
Příspěvky: 22
Registrován: 7. 2. 2008 21:33
Typ studia: Informatika Bc.

Zkouska 27. 1.

Příspěvek od Matfyz »

Ahoj,

byla na vyber lehka a tezka otazka. Vzal jsem si tu lehkou:

T je jednoducha bezesporna extense Peanovy aritmetiky. Zduvodnete, jestli plati nasledujici tvrzeni:
1 - T ma silne nerozhodnutelny model.
2 - nepamatuju se
3 - A je modelem T. Potom Th(A) ma silne nerozhodnutelny model.

Doufam, ze jsem to napsal spravne. Myslim, ze todle byla jedna z mala veci, ktere jsem nevedel. Kolega mel priklad na teorii naslednika a dostal trojku. To bych nejspis taky dal. Dalsi kolega mel priklad na teorii grafu a ten mel ctyrku.
Matfyz
Matfyz(ák|ačka) level I
Příspěvky: 22
Registrován: 7. 2. 2008 21:33
Typ studia: Informatika Bc.

Re: Zkouska 27. 1.

Příspěvek od Matfyz »

K bodu 3 jsem vycetl z textu "Teorie a jejich analyza" (1.7.2), ze libovolny model A teorie T je silne nerozhodnutelna struktura a ze to plyne z vety o nerozhodnutelnosti. Nevite nekdo, jak to z vety o nerozhodnutelnosti plyne?
Acris
Matfyz(ák|ačka) level I
Příspěvky: 20
Registrován: 26. 1. 2010 14:28
Typ studia: Informatika Mgr.
Bydliště: Praha

Re: Zkouska 27. 1.

Příspěvek od Acris »

Matfyz píše:K bodu 3 jsem vycetl z textu "Teorie a jejich analyza" (1.7.2), ze libovolny model A teorie T je silne nerozhodnutelna struktura a ze to plyne z vety o nerozhodnutelnosti. Nevite nekdo, jak to z vety o nerozhodnutelnosti plyne?
Nevím, zda jsou mé úvahy správné, pokud to někdo zkontrolujete, bude to fajn...

Pokud T je bezesporná extenze Robinsonovy aritmetiky Q (což jednoduchá bezesporná extenze Peanovy aritmetiky je), tak platí dle věty 4.3.4 (O nerozhodnutelnosti), že je T nerozhodnutelná. Také platí, že \mathcal A \models Q. A teď ještě potřebujeme ukázat, že každá teorie T', která má A za model, je nerozhodnutelná. Nechť tedy \mathcal A \models T'. Pak T' \cup Q je jednoduché rozšíření T' o konečně axiomů. Tedy dle věty 4.3.6 je i T' nerozhodnutelná. Proto A je silně nerozhodnutelná.

A k příkladu ze zkoušky: Již víme, že A je silně nerozhodnutelná struktura. Dále platí, že \mathcal A \models Th(A). Proto jednak Th(A) je nerozhodnutelná a zřejmě má i silně nerozhodnutelný model - a to A.
Matfyz
Matfyz(ák|ačka) level I
Příspěvky: 22
Registrován: 7. 2. 2008 21:33
Typ studia: Informatika Bc.

Re: Zkouska 27. 1.

Příspěvek od Matfyz »

Nevím, zda jsou mé úvahy správné, pokud to někdo zkontrolujete, bude to fajn...
Ahoj, myslím, že je to správně. Moc díky :) !
Odpovědět

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