Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Rozhodnutelnost

Definice (Rekurzivní funkce a množina)

Rekurzivní funkce jsou všechny funkce popsatelné jako , kde , tedy všechny algoritmicky vyčíslitelné funkce. Množina přirozených čísel je rekurzivní množina (rozhodnutelná množina), pokud je rekurzivní její charakteristická funkce (to je funkce, která určí, které prvky do množiny patří).

Definice (Spočetný jazyk, kód formule)

Spočetný jazyk je jazyk, který má nejvýš spočetně mnoho speciálních symbolů. Pro spočetný jazyk, kde lze efektivně (rekurzivní funkcí) očíslovat jeho speciální symboly, lze každé jeho formuli přiřadit její kód formule - přir. číslo .

Věta (Churchova o nerozhodnutelnosti predikátové logiky)

Pokud spočetný jazyk prvního řádu obsahuje alespoň jednu konstantu, alespoň jeden funkční symbol arity a pro každé přirozené číslo spočetně mnoho predikátových symbolů, potom množina je uzavřená formule a není rozhodnutelná.

Věta (o nerozhodnosti predikátové logiky)

Nechť je jazyk prvního řádu bez rovnosti a obsahuje alespoň 2 binární predikáty. Potom je predikátová logika (jako teorie) s jazykem nerozhodnutelná.

Definice (Tři popisy aritmetiky)

Je dán jazyk .

- Robinsonova aritmetika - "" s jazykem L má 8 násl. axiomů:

  Poznámka: Někdy, pokud není potřeba definovat uspořádání, se poslední axiom spolu se symbolem &le#leq; vypouští.

- Peanova aritmetika - "" má všechny axiomy Robinsonovy kromě třetího, navíc má Schéma(axiomů) indukce - pro formuli a proměnnou platí: .
- Úplná aritmetika má za axiomy všechny uzavřené formule pravdivé v , je-li standardní model aritmetiky - pravdivá aritmetika. Teorie modelu je množina je uzavřená formule a .

Platí: . má konečně mnoho axiomů, je tedy rekurzivně axiomatizovatelná. má spočetně mnoho axiomů, kódy axiomů schématu indukce tvoří rekurzivní množinu. není rekurzivně axiomatizovatelná.

Definice (Množina kódů vět teorie)

Pro teorii s jazykem aritmetiky definujeme množinu kódů vět teorie jako je uzavřená formule a .

Definice (Rozhodnutelná teorie)

Teorie s jazykem aritmetiky je rozhodnutelná, pokud je množina rekurzivní. V opačném případě je nerozhodnutelná.

Věta (Churchova o nerozhodnutelnosti aritmetiky)

Každé bezesporné rozšíření Robinsonovy aritmetiky je nerozhodnutelná teorie.

Věta (Gödel-Rosserova o neúplnosti aritmetiky)

Žádné bezesporné a rekurzivně axiomatizovatelné rozšíření Robinsonovy aritmetiky není úplná teorie.