3.2.2011 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.
paulie
Matfyz(ák|ačka) level I
Příspěvky: 18
Registrován: 4. 1. 2010 23:33
Typ studia: Informatika Mgr.

3.2.2011 Mlček

Příspěvek od paulie »

Dneska byla zkouška docela hustá. Šel jsem na ústní jako poslední, cca 8 lidí bylo předtím vyhozeno (což Mlček vtipně komentoval, že se asi moc neučili; asi 5 z nich rovnou z písemky), 2 lidé měli za jedna (sic!!! ale zřejmě to byli ti s bonifikací, kteří nepsali, minimálně jeden určitě), myslím, že za 2 měl jen jeden. No a zbytek 3, včetně mě :).

Otázky si moc nepamatuji, snad se objeví s řešením na Mlčkových stránkách:

Úloha 1 -- výroková logika
Logika s prvovýroky P. Byla dána X jako podmnožina prvovýroků a K třída modelů; K = {v; v(p) = 1 pro všechna p z X}
A) Je K axiomatizovatelná?
B) Právě kdy je množina -K (komplement K) axiomatizovatelná?

Úloha 2 -- predikátová logika
A) byla dána teorie T v jazyce s <= (menší nebo rovno) a jediným axiomem x <= x. Měli jsme vybrat pravdivé výroky z následujících možností:
a) T |- x <= y & y <= x -> x = y
b) něco jako, jestli existuje otevřená formule fi, pro které je T navíc s fi kompletní a má alespoň dvouprvkový model
c) podobná b), ale formule nemusela být otevřená
B) Určete počet podmnožin reálného intervalu (-1, 1) definovatelných bez parametrů v modelu <(-1, 1), '<=' > (myslím, že v té otázce ještě něco bylo...)

Úloha 3 -- analýza teorií
A) Opět výběr z možností, už si je nepamatuji, vyskytla se tam však Peanova aritmetika, SC0, elementární ekvivalence...
B) I(w, SC0) -- tedy počet neizomorfních spočetných modelů SC0

Řešení (to, co alespoň trochu vím; měl jsem správně jen 1), ostatní jen trochu a doháněl jsem je v ústní části):
1)
A) ano, axiomatika jest následující {p; p náleží do X}
B) právě když X je konečná (X konečná <=> T = {p; p náleží do X} konečná <=> K konečně axiomatizovatelná (M(T) = K) <=> K i -K axiomatizovatelné

2)
B) 2 -- jsou to (-1, 1) a prázdná množina. Náznak důkazu (probíral jsem to trochu z Mlčkem na ústní): je to v teorii DeLO, která má eliminaci kvantifikátorů, tudíž není třeba uvažovat kvantifikované formule. Uvažují se jen formule s jednou proměnnou (nevím proč... že by kvůli substituci?) Atomické formule jsou jen 2: "x <= x" a "x = x", obě definují (-1, 1), jejich negace definují prázdnou množinu. Zbytek se dokáže indukcí dle složitosti formule: v indukční kroku stačí ukázat, že booleovské operace (v, &, negace) odpovídají průniku, sjednocení a doplňku a tudíž nelze vytvořit jinou množinu než (-1, 1) a prázdnou.

3)
B) w (spočetně mnoho). Modelem SC0 je <N, S, 0>, za něj lze přidat libovolně mnoho (konečně nebo spočetně mnoho) struktur celých čísel, tedy struktur <Z, S>. Podle počtu přidaných struktur <Z,S> se rozlišují neizomorfní modely SC0. Že jich více není, se dokáže takto: definuje se ekvivalence mezi prvky x, y, když se z jednoho lze dostat do druhé pomocí konečně mnoha použití S (tedy x = S...Sy nebo y = S...Sx pro konečně mnoho S). Třídy ekvivalence jsou struktury <Z,S> nebo struktura <N,S,0>

Ještě rada: Mlček se u ústní zkoušky ptá hlavně na otázky z písemky, co jste neměli dobře (určitě, stačí-li vám trojka), takže je dobré si mezitím, než na vás přijde řada, najít/zjistit/(zeptat se křišťálové koule) na správně odpovědi otázek v písemce včetně zdůvodnění. Tudíž i opsat si zadání na pomocný papír, který k písemce dostanete a který se neodevzdává.
Odpovědět

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