Zkouška 4.1.2013 (předtermín)

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.
LordG
Matfyz(ák|ačka) level I
Příspěvky: 15
Registrován: 11. 1. 2012 13:08
Typ studia: Informatika Bc.

Zkouška 4.1.2013 (předtermín)

Příspěvek od LordG »

Zadání:

1. (VL)
A) P = {p, q, r} P-teorie T má axiomatiku {p, q->r}.
a) Napište formuli v DNF axiomatizující T
b) Napište JKE teorie T

B) P je nekonečná množina prvovýroků. T je teorie s axiomy {not(p) nebo not(q); p, q jsou různé prvovýroky }
a) Jak vypadají modely?
b) Je T konečně axiomatizovatelná?
c) Je množina K P-modelů, v nichž alespoň dva výroky mají pravdivé ohodnocení, konečně axiomatizovatelná?

2. (PL)
A) Jazyk L = <F>.
Struktura A = <{0, 1, 2, 3}, +>; + je sčítání modullo 4. T je L-teorie s axiomem (existuje y)(pro každé x)(F(x, y) =/= x)
a) Platí A |= T?
b) Počet různých automorfismů na A
c) Lze bezparametricky definovat množinu {2}?
d) Velikost množiny Df1(0, A)
e)

B)
a) je T otevřeně axiomatizovatelná?
b) Jazyk L' = L u {c}, T* je L'-teorie s axiomatikou {F(x,c) =/= c}. Je T* otevřená konzervativní extenze T?
c) Možná, že jsem do b) omylem napsal zadání b) a c). Nepamatuji se.

3. (PL)
A)
T teorie ostrého lineárního uspořádání, navíc s rozšířením jazyka o konstanty c0 a c1 a axiomy
chi0: c0 =/= c1
chi1: c0 <= x <= c1
a) I(n, T) pro 2 <= n € N
b)
i) má T algebraický prvomodel?
ii) má T prvomodel?
c) Je T kompletní?
d) Je T otevřeně axiomatizovatelná
e) [NESOUVISÍ S PŘEDCHOZÍM] interval [-2, 2], na něm {1 +- (1/(2^n)), n€N} u {-1 +- (1/(2^n)), n€N} (polopaticky, vezme se 1 / 2^n, a to se přičte a odečte od 1 a -1 a vzniknou dvě množiny bodů, které zleva a zprava konvergují k 1 a -1).
Má se rozhodnout, jestli je {0} množina definovatelná bezparametrickou formulí ve struktuře A = <[VÝŠE POPSANÁ MNOŽINA], <= >, kde <= je obvyklé uspořádání čísel.

B)
a) Je T rozhodnutelná?
b) Kolik má T rozhodnutelných jednoduchých extenzí?

-- možná se někde pletu, 2 A e a 2 B c si nepamatuji --
Řešení:
1 A
a) (p & non q & non r) nebo (p & non q & r) nebo (p & q & r); plyne bezprostředně z množiny modelů, obecně v je model T, jestliže v(p) = 1 a v(q) <= v(r)
b) Teorie jsou ty, které mají jako axiomatiku jednoprvkovou množinu jednoho z disjunktů formule z a). To je proto, že extenze T musí být její podmnožina a kompletní teorie má jediný model.

1B
a) Modely mají nejvýše jeden prvovýrok ohodnocen pravdou. To se dokáže snadno: má-li nějaké v pro p =/= q v(p) = v(q) = 1, potom neplatí axiom (not p nebo not q) a tudíž takové v není modelem T.
b) NE. Dokazatelné sporem: pokud je konečně axiomatizovatelné, pak se v konečné axiomatice vyskytuje konečně mnoho prvovýroků. Tedy tam jistě některé nebudou a taková axiomatika o jejich hodnocení nebude nic říkat.
c) NE. Množina K je komplement M(T). Kritérium říká, že K i -K jsou axiomatizovatelné <=> K je konečně axiomatizovatelné. V b) je dokázáno, že M(T) není. Takže vezmeme K := M(T), -K := naše množina K a hotovo.

2A
a) ANO. Stačí uspokojit ten jediný axiom. Stačí za x dosadit cokoliv kromě 0 a vyjde to (.. a pokud nevyjde, tak jsem tu axiomatiku napsal špatně :D )
b) 2. Jde o to, že 1 a 3 se chovají "stejně" (1+0 = 1, 3+0 = 3, 1+2 = 3, 3+2 = 1, 1+3 = 3+1 = 0, 1+1 = 2, 3+3 = 2), takže izomorfismy buď prohodí nebo neprohodí 1 a 3
c) ANO. Formule x+x = 0 a (pro každé y) y+x =/= y. (První konjunkt dá {0, 2}, druhý vyloučí nulu).
d) 8 (=23). Mohu definovat "atomické" množiny {0}, {2}, {1,3} (jak, to naznačuje c) ). Booleovskými úpravami pak i kombinace těchto tří.

2B
a) NE. Podle kritéria T je ot. axiomatizovalná <=> (A podmnožina B |= T => A |= T). Stačí za B vzít naše A a za A vzít strukturu < {0}, +>. Ta není modelem teorie T.
b) ANO. Jde o Skolemovu variantu toho jediného axiomu. Ta je s ním podle nějaké věty ekvivalentní. A je otevřená, tzn ta T* je otevřená.

3A
a) 1. Mezi c0 a c1 je v modelu o n prvcích vždy n-2 prvků, což máme zařízeno axiomy, a o uspořádání ostatních prvků axiomy nic jiného neříkají. Takže jsou modely stejné velikosti izomorfní.
b), c), d) Řešil jsem trochu jiné zadání, což mi bylo u zkoušky odpuštěno, ale řešení proto nevím.
e) NE. Poslouží to slavné kritérium o definovatelnosti množiny.

3B
a) ANO. Má rekurzivní kompletaci.
b) omega. Že jich je alespoň omega dokazuje to, že každá teorie Tn, rozšiřující T axiomem "existuje právě n prvků", spolu navíc s Tnekonečno ("existuje nekonečno prvků") je kompletní a má rekurzivní axiomatiku, tedy je rozhodnutelná. Že jich není víc, to nechám na chytřejších, aby vysvětlili.
LordG
Matfyz(ák|ačka) level I
Příspěvky: 15
Registrován: 11. 1. 2012 13:08
Typ studia: Informatika Bc.

Re: Zkouška 4.1.2013 (předtermín)

Příspěvek od LordG »

..dále k průběhu: tato písemka byla na hodinu, potom se doc. Mlček s panem Glivickým vrhli na nás a postupně to s námi s jedním za druhým konzultovali. Dlužno podotknout, že p. Glivický byl velice shovívavý, jak je z mého výše popsaného řešení patrné :) . Celá zkouška zabrala necelou hodinu a půl.
Locky
Matfyz(ák|ačka) level I
Příspěvky: 2
Registrován: 13. 1. 2012 11:44
Typ studia: Informatika Bc.

Re: Zkouška 4.1.2013 (předtermín)

Příspěvek od Locky »

Koukám, že test už má i na stránkách:
http://ktiml.mff.cuni.cz/~mlcek/ET-1_12.pdf
Přílohy
ET-1_12.pdf
(59.42 KiB) Staženo 247 x
Odpovědět

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