ŘEŠENÉ ZÁPOČTOVÉ TESTY Z VÝROKOVÉ A PREDIKÁTOVÉ LOGIKY

Poznámka: Tento materiál je souborem řešených zápočtových testů ze zimního semestru 2012/2013 k přednášce Výroková a predikátová logika na MFF UK v Praze. Nejedná se o oficiální materiál k přednášce, nebyl korigován, je proto možné, že obsahuje chyby. U některých úloh není uvedena odpověď a/nebo řešení; je to dáno snahou o co možná nejrychlejší poskytnutí materiálu studentům a tento nedostatek bude časem napraven.

ŘEŠENÉ ZÁPOČTOVÉ TESTY Z VÝROKOVÉ A PREDIKÁTOVÉ LOGIKY Petr Glivický1

Cvičení středa od 9:00 TEST VPL, cvičení 10.10.12

Jméno:

ÚLOHA 1 [Znění.] Definujte, pojem struktura pro jazyk L = hR, F i, kde R je unární relační symbol a F unární funkční symbol. Nekomentujte Řešení. Je to každá trojice A = hA, RA , F A i, kde RA ⊆ A a F A : A → A.

· takto: x − y = x ∧ (−y) a x − · y = ÚLOHA 2 [Příklad.] V Booleově algebře definujeme binární operace − a − · b = (a ∨ b) − (a ∧ b). (x − y) ∨ (y − x). Dokažte, že v Booleově algebře platí identita a − Řešení. · b = (a ∧ −b) ∨ (b ∧ −a) = (a ∨ b) ∧ (a ∨ −a) ∧ (−b ∨ b) ∧ (−b ∨ −a) = (a ∨ b) ∧ 1 ∧ 1 ∧ (−b ∨ −a) = (a ∨ b) − (a ∧ b). Je a −

Uveďte zdůvodnění. První rovnost plyne užitím definic, druhá z distributivního zákona. Třetí je zdůvodněna užitím axiomu komplementace a poslední plyne z neutrality 1 a aplikací de-Morganova pravidla na (−b ∨ −a).

ÚLOHA 3 [Příklad.] Navrhněte jazyk L a L-formuli ϕ vyjadřující „každý člověk zná sám sebe a existují dva různí lidé, kteří se neznají (tj. ani jeden z nich nezná druhého).ÿ Nezdůvodňujte. Řešení. L = hZi s rovností, kde Z je binární relační symbol, ϕ: (∀x)(Z(x, x)) & (∃y, z)(¬(y = z) & ¬Z(y, z) & ¬Z(z, y))

TEST VPL, cvičení 17.10.12

Jméno:

ÚLOHA 1 [Znění.] Definujte pojem model teorie T . Nekomentujte Řešení. Model teorie T v jazyce L je L-struktura A, ve které platí každý axiom teorie T .

ÚLOHA 2 [Příklad.] Buď L = h+, −, c, di jazyk, kde + je binární funkční symbol, − unární funkční symbol a c, d jsou konstantní symboly. Dále buď t term (x + c) + (−d) jazyka L. Vypočtěte hodnotu tA [e] termu t ve struktuře A při ohodnocení proměnných e, když a) A = hR, +, −, 0, 1i, kde +, − značí obvyklé sčítání a opačnou hodnotu v oboru reálných čísel, a e(x) = 2, b) A = hZ, ·, | |, 1, −2i, kde ·, | | značí obvyklé násobení a absolutní hodnotu v oboru celých čísel, a e(x) = −1. Řešení. a) 1 b) −2

Uveďte zdůvodnění. a) Je tA [e] = (2 + 0) + (−1) = 1. b) Je tA [e] = (−1 · 1) · | − 2| = −2.

ÚLOHA 3 [Příklad.] Nechť L = h+i je jazyk s rovností, kde + je binární funkční symbol. Platí v každé L-struktuře formule x + y = y + x? Řešení. Ne.

Uveďte zdůvodnění. Ve struktuře h{0, 1}, f i, kde f (a, b) = b pro každé a, b ∈ {0, 1}, zřejmě uvažovaná formule neplatí při ohodnocení proměnných e s e(x) = 0, e(y) = 1.


Jméno:

ÚLOHA 1 [Znění.] Definujte pojem kompletní teorie. Komentujte další pojmy, které uvedete. Řešení. Teorie je kompletní, je-li bezesporná a každá její sentence je v ní dokazatelná nebo vyvratitelná.

Uveďte komentář. Sentence je formule neobsahující žádný volný výskyt proměnné. Formule ϕ je dokazatelná v T , existuje-li její důkaz v T , je vyvratitelná, je-li dokazatelná ¬ϕ.

ÚLOHA 2 [Příklad.] Rozhodněte, zda je v následujících případech term t substituovatelný za proměnnou x do formule x = y & (∃y)(x = z) & (∃z)(∀x)(x = y): a) t je x, b) t je y, c) t je z. Řešení. a) Ano. b) Ne. c) Ano.

Uveďte zdůvodnění. a) V prvním a druhém konjunktu není výskyt x v podformuli tvaru (Qx)ψ, třetí konjunkt neobsahuje volný výskyt x. b) Ve druhém konjunktu má x volný výskyt v podformuli tvaru (∃y)ψ. c) V prvním a druhém konjunktu není výskyt x v podformuli tvaru (Qz)ψ, třetí konjunkt neobsahuje volný výskyt x.

ÚLOHA 3 [Příklad.] Rozhodněte, zda jsou izomorfní a) každé dvě (ne nutně stejně velké) struktury jazyka L bez mimologických symbolů (tj. L = ∅), b) každé dvě spočetné struktury jazyka L = hU i, kde U je unární relační symbol, c) každé dvě spočetné struktury jazyka L = hci, kde c je konstantní symbol, d) spočetné stuktury A = hA, U A i, B = hB, U B i pro jazyk L = hU i s unárním relačním symbolem U , pokud všechny množiny U A , A − U A , U B i B − U B jsou nekonečné. Velikostí struktury rozumíme velikost jejího univerza. Všechny uváděné jazyky jsou s rovností. Řešení. a) b) c) d)

Ne. Ne. Ano. Ano.

Uveďte zdůvodnění. a) Konečná a nekonečná L-struktura nejsou izomorfní, protože izomorfismus je bijekce. b) Struktury hN, ∅i a hN, Ni nejsou izomorfní. c) Izomorfismem struktur A, B je jakákoli bijekce h : A → B s h(cA ) = h(cB ); ta zřejmě existuje kdykoli jsou A a B stejně velké. d) Izomorfizmus h : A → B se sestrojí jako h = f ∪ g, kde f : U A → U B a g : A − U A → B − U B jsou bijekce.


Jméno:

ÚLOHA 1 [Znění.] Definujte pojem ω-kategorická teorie. Nekomentujte Řešení. Teorie je ω-kategorická, má-li právě jeden spočetný model až na izomorfismus.

ÚLOHA 2 [Příklad.] Rozhodněte, zda je v následujících případech formule ϕ0 variantou formule ϕ, kde ϕ je (∃x)(∀y)(x = y & y 6= z) → (∀x)(x = y) a a) ϕ0 je (∃z)(∀y)(z = y & y 6= z) → (∀x)(x = y), b) ϕ0 je (∃u)(∀v)(u = v & v 6= z) → (∀w)(w = y). Řešení. a) Ne. b) Ano.

Uveďte zdůvodnění. a) z má volný výskyt v (∀y)(x = y & y 6= z). b) Obě podmínky jsou ve všech případech splněny.

ÚLOHA 3 [Příklad.] Buď L = hU, ci, kde U je unární relační symbol a c je konstantní symbol. Buď ϕ formule U (x) → U (c). a) Najděte všechny L-struktury A = hA, U A , cA i takové, že A |= ϕ. b) Určete množinu D ⊆ Z definovanou formulí ϕ ve struktuře hZ, S, 1i, kde S je množina všech sudých celých čísel (tj. S je relace „být sudé celé čísloÿ). Řešení. a) Jsou to právě struktury splňující cA ∈ U A nebo U A = ∅. b) Je to množina L = Z − S lichých celých čísel.

Uveďte zdůvodnění. a) ϕ ∼ ¬U (x) ∨ U (c). b) ϕ ∼ ¬U (x) ∨ U (c), přitom S(1) neplatí.


Jméno:

ÚLOHA 1 [Znění.] Definujte, kdy je pro dvě struktury A, B (v témže jazyce L) A elementární podstruktura B, tj. A ≺ B? Nekomentujte Řešení. Právě když A ⊆ B a pro každou L-formuli ϕ(x) a l(x)-tici a ∈ A je A |= ϕ[a] ⇔ B |= ϕ[a].

ÚLOHA 2 [Příklad.] Buď L = hU i jazyk s unárním relačním symbolem U a buď A = hQ, P i, kde P je množina kladných racionálních čísel, L-struktura. Je každá podstruktura B ⊆ A s nekonečným univerzem B a) izomorfní s A? b) elementárně ekvivalentní s A? Řešení. a) Ne. b) Ne.

Uveďte zdůvodnění. a) Struktura B = hP, P i není elementárně ekvivalentní s A a tedy ani izomorfní s A. b) Struktura B = hP, P i není elementárně ekvivalentní s A.

ÚLOHA 3 [Příklad.] Buď L = h≤, c, di, kde ≤ je binární relační symbol a c, d jsou konstantní symboly. Pro každá m, n ∈ Z buďte Zm,n = hZ, ≤, m, ni a Qm,n = hQ, ≤, m, ni L-struktury, kde ≤ značí obvyklé uspořádání na Z resp. na Q. Charakterizujte, právě pro jaká m, n a m0 , n0 platí a) Zm,n ∼ = Zm0 ,n0 , b) Qm,n ∼ = Qm0 ,n0 . Řešení. a) Právě když m − n = m0 − n0 . b) Právě když m − n a m0 − n0 jsou obě kladná, obě nulová či obě záporná.

Uveďte zdůvodnění. a) Pro izomorfizmus h musí být h(m) = m0 , h(n) = n0 a pro i ∈ Z také h(n + i) = n0 + i. Odtud m0 − n0 = h(m) − n0 = h(n + (m − n)) − n0 = m − n. Naopak, je-li m − n = m0 − n0 , tak h(x) = x + n0 − n je izomorfismus. b) Pro izomorfizmus h musí být h(m) = m0 , h(n) = n0 a m < n ⇔ h(m) < h(n). Naopak, je-li kdykoli např. m < n a m0 < n0 , existují bijekce h1 : (−∞, m] → (−∞, m0 ], h2 : [m, n] → [m0 , n0 ] a h3 : [n, ∞) → [n0 , ∞) a h = h1 ∪ h2 ∪ h3 je izomorfizmus. Zbylé případy se zdůvodní podobně.


Jméno:

ÚLOHA 1 [Znění.] Definujte, kdy je pro dvě struktury A, B (v témže jazyce L) A elementárně ekvivalentní s B, tj. A ≡ B? Nekomentujte Řešení. Právě když v A a B platí tytéž sentence.

ÚLOHA 2 [Znění.] Definujte pojem modelově kompletní teorie. Nekomentujte Řešení. T je modelově kompletní, pokud pro každé dva její modely A, B je A ⊆ B ⇒ A ≺ B.

ÚLOHA 3 [Příklad.] Buď L = hU, ci jazyk s rovností, kde U je unární relační symbol a c je konstantní symbol. Buď dále T teorie s axiomy vyjadřujícími schémata „existuje nekonečně mnoho x s U (x)ÿ a „existuje nekonečně mnoho x s ¬U (x)ÿ. a) Kolik existuje až na izomorfismus spočetných modelů T ? b) Uveďte alespoň tři vzájemně neizomorfní modely T s univerzem R. Řešení. a) 2 b) hR, Z, 0i, hR, Z, 12 i, hR, R − Z, 0i, hR, R − Z, 21 i, hR, [0, ∞), 0i, hR, [0, ∞), −1i

Uveďte zdůvodnění. a) Jsou to modely A splňující cA ∈ U A a cA ∈ / U A. b) Zjevně nejsou žádné dva z uvedených modelů izomorfní.

ÚLOHA 4 [Příklad.] Uveďte počet různých podstruktur struktury A pro a) A = hZ, 0, +, −i, kde + a − jsou obvyklé operace sčítání a opačného prvku v oboru celých čísel, b) A = hZ, 0, 1, +, −i, kde + a − jsou obvyklé operace sčítání a opačného prvku v oboru celých čísel. Všechny nalezené podstruktury uveďte ve zdůvodnění. Řešení. a) ω b) 1

Uveďte zdůvodnění. a) Jsou to právě podstruktury s univerzy kZ s k ∈ N. b) Je to jen A.

ÚLOHA 5 [Příklad.] Nechť T je teorie v jazyce L = hSi s jediným unárním funkčním symbolem S a s axiomy S 2 (x) = x a „existuje nekonečně mnoho prvkůÿ. Rozhodněte, zda platí: a) T je kompletní teorie. b) T má právě ω spočetných modelů až na izomorfismus. Řešení. a) Ne. b) Ano.

Uveďte zdůvodnění. a) (∃x)(Sx = x) je sentence nezávislá v T . b) Jde o modely Am,n s m, n ≤ ω, m + n = ω, kde Am,n sestává z m S-cyklů délky 1 a n S-cyklů délky 2.

ÚLOHA 6 [Příklad.] Buď A = hZ, Si struktura, kde unární funkce S je dána vztahem S(z) = z + 1 pro z ∈ Z, a buď X = {0}. Je X definovatelná v A bez parametrů? Řešení. Ne.

Uveďte zdůvodnění. Zobrazení h : z 7→ z + 1 je automorfizmus A a h[X] 6= X. Tedy X není definovatelná bez parametrů dle kritéria nedefinovatelnosti.


Jméno:

ÚLOHA 1 [Znění.] Buď T teorie v jazyce L. Uvěďte jaké ze vztahů ⇒, ⇐ (případně též žádný či oba) lze v následujících případech dosadit na místo tak, abychom získali platné tvrzení: a) T má eliminaci kvantifikátorů T je modelově kompletní. b) T je kompletní T má jediný spočetný model až na izomorfismus. c) T je 1-koexistenční T je f-homogenní. d) Neexistuje sentence nezávislá v T každé dva modely T jsou elementárně ekvivalentní. Nekomentujte Řešení. a) b) c) d)

⇒, žádný, ⇐, oba.

ÚLOHA 2 [Znění.] Buď P = {p, q, r, s} množina všech prvovýroků. Pomocí ekvivalentních úprav nalezněte k výroku ϕ: ¬(p → q) & (r ∨ ¬s) výrok s ním ekvivalentní a navíc v disjunktivně normálním tvaru (DNF). Nekomentujte Řešení.

ÚLOHA 3 [Příklad.] Buď L = hU i, kde U je unární relační symbol. Buď dále T L-teorie s axiomy vyjadřujícími „existuje nekonečně mnoho x s ¬U (x)ÿ. a) Kolik má T spočetných modelů až na izomorfizmus? b) Je T kompletní teorie? Řešení. a) ω b) Ne.

Uveďte zdůvodnění.


Jméno:

ÚLOHA 1 [Znění.] Buď P neprázdná konečná množina prvovýroků, ϕ výrok nad P a MP (ϕ) množina modelů ϕ. Uveďte výrok v DNF ekvivalentní ϕ. Nekomentujte Řešení.

ÚLOHA 2 [Příklad.] Nechť P = {p, q, r} je množina všech prvovýroků a T = {¬p} je P-teorie. Zjistěte počet neekvivalentních výroků ϕ nad P takových, že T ` ϕ ∨ q. Řešení. 26 = 64

Uveďte zdůvodnění. Je T ` ϕ ∨ q ⇔ MP (T ) ⊆ MP (ϕ ∨ q) = MP (ϕ) ∪ MP (q). To nastává, právě když MP (ϕ) ⊇ MP (T ) − MP (q), tedy hledaný 3 P počet je počet nadmnožin množiny MP (T ) − MP (q) = MP (T, ¬q) v P 2, což je 22 −|M (T,¬q)| = 26 = 64.

ÚLOHA 3 [Příklad.] Nechť P je konečná množina všech prvovýroků s |P| = l a ϕ nějaký výrok nad P. Zjistěte počet neekvivalentních P-teorií T takových, že T ` ¬ϕ. Výsledek vyjádřete pomocí |MP (ϕ)| a l. Řešení. l

P

22 −|M

(ϕ)|

Uveďte zdůvodnění. Je T ` ¬ϕ ⇔ MP (T ) ⊆ MP (¬ϕ) = P 2 − MP (ϕ). Tedy takových teorií T je tolik, kolik je podmnožin P 2 − MP (ϕ), což je l P právě 22 −|M (ϕ)| .


Jméno:

ÚLOHA 1 [Znění.] a) Formulujte tvrzení o vztahu mezi eliminací kvantifikátorů a modelovou kompletností. b) Definujte, kdy je L(T )-struktura A algebraickým prvomodelem teorie T . Komentujte další pojmy, které uvedete. Řešení. a) Má-li teorie T eliminaci kvantifikátorů, je modelově kompletní. b) A je algebraický prvomodel T , lze-li A vnořit do každého modelu teorie T .

Uveďte komentář. a) T má eliminaci kvantifikátorů, je-li v T každá formule ϕ(x) s l(x) > 0 ekvivalentní nějaké otevřené formuli ψ(x). T je modelově kompletní, když každé vnoření mezi dvěma jejími modely je elementátní vnoření. b)

ÚLOHA 2 [Příklad.] Buď ϕ formule (∃x)U (x) → (∀x)V (x), kde U, V jsou unární relační symboly. Pomocí prenexních operací najděte formuli ψ v prenexním tvaru a ekvivalentní s ϕ. Řešení. (∀x)(∀y)(U (x) → V (y))

Uveďte zdůvodnění. Vytknutím ∃x získáme (∀x)(U (x) → (∀x)V (x)). Nahrazením (∀x)V (x) variantou (∀y)V (y) a vytknutím ∀y dostaneme (∀x)(∀y)(U (x) → V (y)), což je zjevně v prenexním tvaru.

ÚLOHA 3 [Příklad.] Nechť L = hc, di je jazyk s rovností, kde c, d jsou konstantní symboly. Buď dále S L-teorie s axiomy vyjadřujícími „existuje nekonečně mnoho prvkůÿ. Kolik má S jednoduchých kompletních extenzí (JKE) až na ekvivalenci teorií? Řádně zdůvodněte kompletnost uvedených JKE. Řešení. 2

Uveďte zdůvodnění. Jde právě o extenze S o axiom c = d resp. c 6= d. Obě jsou kompletní dle kategorického kritéria kompletnosti. Nemají totiž zjevně konečné modely a jsou κ-kategorické pro každé nekonečné κ.

Cvičení středa od 10:40 TEST VPL, cvičení 10.10.12

Jméno:

ÚLOHA 1 [Znění.] Nechť A = hA, RA , F A i a B = hB, RB , F B i jsou struktury pro jazyk L = hR, F i, kde R je unární relační symbol a F je unární funkční symbol. Definujte, kdy je h : A → B izomorfizmus struktur A a B. Nekomentujte. Řešení. Právě když h je prosté a na B a pro každé a ∈ A platí: RA (a) ⇔ RB (ha), h(F A (a)) = F B (ha).

· takto: x − y = x ∧ (−y) a x − · y = ÚLOHA 2 [Příklad.] V Booleově algebře definujeme binární operace − a − · b = (a ∨ b) − (a ∧ b). (x − y) ∨ (y − x). Dokažte, že v Booleově algebře platí identita a − Řešení. · b = (a ∧ −b) ∨ (b ∧ −a) = (a ∨ b) ∧ (a ∨ −a) ∧ (−b ∨ b) ∧ (−b ∨ −a) = (a ∨ b) ∧ 1 ∧ 1 ∧ (−b ∨ −a) = (a ∨ b) − (a ∧ b). Je a −

Uveďte zdůvodnění. První rovnost plyne užitím definic, druhá z distributivního zákona. Třetí je zdůvodněna užitím axiomu komplementace a poslední plyne z neutrality 1 a aplikací de-Morganova pravidla na (−b ∨ −a).

ÚLOHA 3 [Příklad.] Navrhněte jazyk L a L-formuli ϕ vyjadřující „žádný člověk nemá rád sám sebe a existuje člověk, kterého má rád každý jiný člověk.ÿ Nezdůvodňujte. Řešení. L = hRi s rovností, kde R je binární relační symbol, ϕ: (∀x)(¬R(x, x)) & (∃y)(∀z)(z 6= y → R(z, y))


Jméno:

ÚLOHA 1 [Znění.] Definujte pojem formule ϕ platí (je pravdivá) v teorii T . Nekomentujte Řešení. Formule ϕ jazyka L platí v L-teorii T , pokud platí v každém modelu T .

ÚLOHA 2 [Příklad.] Buď L = h·, −, c, di jazyk, kde · je binární funkční symbol, − unární funkční symbol a c, d jsou konstantní symboly. Dále buď t term (x · c)· (−d) jazyka L. Vypočtěte hodnotu tA [e] termu t ve struktuře A při ohodnocení proměnných e, když a) A = hR, ·, −, −2, 1i, kde ·, − značí obvyklé násobení a opačnou hodnotu v oboru reálných čísel, a e(x) = 2, b) A = hZ, +, ()2 , 0, −2i, kde +, ()2 značí obvyklé sčítání a druhou mocninu v oboru celých čísel, a e(x) = 1. Řešení. a) 4 b) 5

Uveďte zdůvodnění. a) Je tA [e] = (−2 · 2) · (−1) = 4. b) Je tA [e] = (1 + 0) + (−2)2 = 5.

ÚLOHA 3 [Příklad.] Nechť L = h≤i je jazyk s rovností, kde ≤ je binární relační symbol. Platí v každé L-struktuře formule x ≤ x? Řešení. Ne.

Uveďte zdůvodnění. Ve struktuře h{0}, ∅i zřejmě uvažovaná formule neplatí při žádném ohodnocení proměnných.


Jméno:

ÚLOHA 1 [Znění.] Definujte pojem bezesporná teorie. Komentujte další pojmy, které uvedete. Řešení. Teorie je bezesporná, není-li v ní dokazatelná každá její formule.

Uveďte komentář. Formule je dokazatelná v teorii T , existuje-li její důkaz v T .

ÚLOHA 2 [Příklad.] Rozhodněte, zda je v následujících případech term t substituovatelný za proměnnou x do formule x = y & (∃y)(x = z) & (∃z)(∀x)(x = y): a) t je z, b) t je y, c) t je x. Řešení. a) Ano. b) Ne. c) Ano.

Uveďte zdůvodnění. a) V prvním a druhém konjunktu není výskyt x v podformuli tvaru (Qz)ψ, třetí konjunkt neobsahuje volný výskyt x. b) Ve druhém konjunktu má x volný výskyt v podformuli tvaru (∃y)ψ. c) V prvním a druhém konjunktu není výskyt x v podformuli tvaru (Qx)ψ, třetí konjunkt neobsahuje volný výskyt x.

ÚLOHA 3 [Příklad.] Rozhodněte, zda jsou izomorfní a) každé dvě spočetné struktury jazyka L bez mimologických symbolů (tj. L = ∅) b) každé dvě spočetné struktury jazyka L = hc, di, kde c, d jsou konstantní symboly, c) každé dvě (ne nutně stejně velké) struktury jazyka L = hci, kde c je konstantní symbol, d) spočetné stuktury A = hA, U A i, B = hB, U B i pro jazyk L = hU i s unárním relačním symbolem U , pokud všechny množiny U A , A − U A , U B i B − U B jsou nekonečné. Velikostí struktury rozumíme velikost jejího univerza. Všechny uváděné jazyky jsou s rovností. Řešení. a) b) c) d)

Ano. Ne. Ne. Ano.

Uveďte zdůvodnění. a) b) c) d)

Jakákoli bijekce mezi univerzy L-struktur je jejich izomorfismem. Struktury hN, 0, 1i a hN, 0, 0i nejsou izomorfní. Konečná a nekonečná L-struktura nemohou být izomorfní. Izomorfizmus h : A → B se sestrojí jako h = f ∪ g, kde f : U A → U B a g : A − U A → B − U B jsou bijekce.


Jméno:

ÚLOHA 1 [Znění.] Definujte pojem ω-kategorická teorie. Nekomentujte Řešení. Teorie je ω-kategorická, má-li právě jeden spočetný model až na izomorfismus.

ÚLOHA 2 [Příklad.] Rozhodněte, zda je v následujících případech formule ϕ0 variantou formule ϕ, kde ϕ je (∀z)(∀y)(x = y & y 6= z) → (∀x)(x = y) a a) ϕ0 je (∀x)(∀y)(x = y & y 6= x) → (∀x)(x = y), b) ϕ0 je (∀u)(∀v)(x = v & v 6= u) → (∀w)(w = y). Řešení. a) Ne. b) Ano.

Uveďte zdůvodnění. a) x má volný výskyt v (∀y)(x = y & y 6= z). b) Obě podmínky jsou ve všech případech splněny.

ÚLOHA 3 [Příklad.] Buď L = hU, ci, kde U je unární relační symbol a c je konstantní symbol. Buď ϕ formule U (c) → U (x). a) Najděte všechny L-struktury A = hA, U A , cA i takové, že A |= ϕ. b) Určete množinu D ⊆ Z definovanou formulí ϕ ve struktuře hZ, S, 0i, kde S je množina všech sudých celých čísel (tj. S je relace „být sudé celé čísloÿ). Řešení. a) Jsou to právě struktury splňující cA ∈ / U A nebo U A = A. b) Je to množina S sudých celých čísel.

Uveďte zdůvodnění. a) ϕ ∼ ¬U (c) ∨ U (x). b) ϕ ∼ ¬U (c) ∨ U (x), přitom S(0) platí.


Jméno:

ÚLOHA 1 [Znění.] Definujte, kdy je pro dvě struktury A, B (v témže jazyce L) A elementární podstruktura B, tj. A ≺ B? Nekomentujte Řešení. Právě když A ⊆ B a pro každou L-formuli ϕ(x) a l(x)-tici a ∈ A je A |= ϕ[a] ⇔ B |= ϕ[a].

ÚLOHA 2 [Příklad.] Buď L = hU i jazyk s unárním relačním symbolem U a buď A = hQ, P i, kde P je množina kladných racionálních čísel, L-struktura. Je každá podstruktura B ⊆ A s nekonečným univerzem B a) izomorfní s A? b) elementárně ekvivalentní s A? Řešení. a) Ne. b) Ne.

Uveďte zdůvodnění. a) Struktura B = hP, P i není elementárně ekvivalentní s A a tedy ani izomorfní s A. b) Struktura B = hP, P i není elementárně ekvivalentní s A.

ÚLOHA 3 [Příklad.] Buď L = h≤, c, di, kde ≤ je binární relační symbol a c, d jsou konstantní symboly. Pro každá m, n ∈ Z buďte Zm,n = hZ, ≤, m, ni a Qm,n = hQ, ≤, m, ni L-struktury, kde ≤ značí obvyklé uspořádání na Z resp. na Q. Charakterizujte, právě pro jaká m, n a m0 , n0 platí a) Zm,n ∼ = Zm0 ,n0 , b) Qm,n ∼ = Qm0 ,n0 . Řešení. a) Právě když m − n = m0 − n0 . b) Právě když m − n a m0 − n0 jsou obě kladná, obě nulová či obě záporná.

Uveďte zdůvodnění. a) Pro izomorfizmus h musí být h(m) = m0 , h(n) = n0 a pro i ∈ Z také h(n + i) = n0 + i. Odtud m0 − n0 = h(m) − n0 = h(n + (m − n)) − n0 = m − n. Naopak, je-li m − n = m0 − n0 , tak h(x) = x + n0 − n je izomorfismus. b) Pro izomorfizmus h musí být h(m) = m0 , h(n) = n0 a m < n ⇔ h(m) < h(n). Naopak, je-li kdykoli např. m < n a m0 < n0 , existují bijekce h1 : (−∞, m] → (−∞, m0 ], h2 : [m, n] → [m0 , n0 ] a h3 : [n, ∞) → [n0 , ∞) a h = h1 ∪ h2 ∪ h3 je izomorfizmus. Zbylé případy se zdůvodní podobně.


Jméno:

ÚLOHA 1 [Znění.] Definujte, kdy je pro dvě struktury A, B (v témže jazyce L) A elementárně ekvivalentní s B, tj. A ≡ B? Nekomentujte Řešení. Právě když v A a B platí tytéž sentence.

ÚLOHA 2 [Znění.] Definujte pojem modelově kompletní teorie. Nekomentujte Řešení. T je modelově kompletní, pokud pro každé dva její modely A, B je A ⊆ B ⇒ A ≺ B.

ÚLOHA 3 [Příklad.] Buď L = hU, ci jazyk s rovností, kde U je unární relační symbol a c je konstantní symbol. Buď dále T teorie s axiomy vyjadřujícími schémata „existuje nekonečně mnoho x s U (x)ÿ a „existuje nekonečně mnoho x s ¬U (x)ÿ. a) Kolik existuje až na izomorfismus spočetných modelů T ? b) Uveďte tři vzájemně neizomorfní modely T s univerzem R. Řešení.


ÚLOHA 4 [Příklad.] Uveďte počet různých podstruktur struktury A pro a) A = hZ, 0, +, −i, kde + a − jsou obvyklé operace sčítání a opačného prvku v oboru celých čísel, b) A = hZ, 0, 1, +, −i, kde + a − jsou obvyklé operace sčítání a opačného prvku v oboru celých čísel. Všechny nalezené podstruktury uveďte ve zdůvodnění. Řešení.


ÚLOHA 5 [Příklad.] Nechť T je teorie v jazyce L = hSi s jediným unárním funkčním symbolem S a s axiomy S 2 (x) = x a „existuje nekonečně mnoho prvkůÿ. Rozhodněte, zda platí: a) T je kompletní teorie. b) T má právě ω spočetných modelů až na izomorfismus. Řešení. a) Ne. b) Ano.

Uveďte zdůvodnění. a) (∃x)(Sx = x) je sentence nezávislá v T . b) Jde o modely Am,n s m, n ≤ ω, m + n = ω, kde Am,n sestává z m S-cyklů délky 1 a n S-cyklů délky 2.

ÚLOHA 6 [Příklad.] Buď A = hZ, Si struktura, kde unární funkce S je dána vztahem S(z) = z + 1 pro z ∈ Z, a buď X = {0}. Je X definovatelná v A bez parametrů? Řešení. Ne.

Uveďte zdůvodnění. Zobrazení h : z 7→ z + 1 je automorfizmus A a h[X] 6= X. Tedy X není definovatelná bez parametrů dle kritéria nedefinovatelnosti.


Jméno:

ÚLOHA 1 [Znění.] Buď T teorie v jazyce L. Uvěďte jaké ze vztahů ⇒, ⇐ (případně též žádný či oba) lze v následujících případech dosadit na místo tak, abychom získali platné tvrzení: a) T má eliminaci kvantifikátorů T je 1-koexistenční. b) T je kompletní T je κ-kategorická pro každé κ ≥ ω. c) T je f-homogenní T je modelově kompletní. d) T má prvomodel T je kompletní. Nekomentujte Řešení. a) b) c) d)

oba, žádný, ⇒, ⇒.

ÚLOHA 2 [Znění.] Buď P = {p, q, r, s} množina všech prvovýroků. Pomocí ekvivalentních úprav nalezněte k výroku ϕ: (p → q) & ¬(¬r & s) výrok s ním ekvivalentní a navíc v konjunktivně normálním tvaru (CNF). Nekomentujte Řešení.

ÚLOHA 3 [Příklad.] Buď L = hU i, kde U je unární relační symbol. Buď dále T L-teorie s axiomy vyjadřujícími „existuje nekonečně mnoho x s U (x)ÿ. a) Jsou každé dvě podstruktury L-struktury hN, Ni elementárně ekvivalentní? b) Je T otevřeně axiomatizovatelná teorie? Řešení. a) Ne. b) Ne.



Jméno:

ÚLOHA 1 [Znění.] Buď P neprázdná konečná množina prvovýroků, ϕ výrok nad P a MP (ϕ) množina modelů ϕ. Uveďte výrok v CNF ekvivalentní ϕ. Nekomentujte Řešení.

ÚLOHA 2 [Příklad.] Nechť P = {p, q, r} je množina všech prvovýroků a ϕ je P-formule p → ¬q. Zjistěte počet neekvivalentních P-teorií T takových, že T, ϕ je sporná teorie. Vyjádřete numericky. Řešení. 22 = 4

Uveďte zdůvodnění. P

Platí: T, ϕ je sporná ⇔ T ` ¬ϕ dle tvrzení o důkazu sporem. Tedy počet hledaných T je 2|M

(¬ϕ)|

= 22 = 4.

ÚLOHA 3 [Příklad.] Nechť P je konečná množina všech prvovýroků s |P| = l a T nějaká teorie nad P. Zjistěte počet neekvivalentních P-výroků ϕ takových, že T ` ¬ϕ. Výsledek vyjádřete pomocí |MP (T )| a l. Řešení.



Jméno:

ÚLOHA 1 [Znění.] a) Formulujte tvrzení o vztahu mezi eliminací kvantifikátorů a f-homogenitou. b) Definujte, kdy je L(T )-struktura A prvomodelem teorie T . Komentujte další pojmy, které uvedete. Řešení. a) Je-li T f-homogenní, má eliminaci kvantifikátorů. b) A je prvomodel T , lze-li A elementárně vnořit do každého modelu teorie T .

Uveďte komentář.

ÚLOHA 2 [Příklad.] Nechť T je výroková teorie {p ∨ ¬q, q ∨ ¬r}. a) Najděte množinovou reprezentaci ◦ T teorie T . b) Určete rezoluční uzávěr Rcl(◦ T ) množiny ◦ T . Řešení. a) ◦ T = {{p, ¬q}, {q, ¬r}} b) Rcl(◦ T ) = ◦ T ∪ {{p, ¬r}}

Uveďte zdůvodnění. b) Zřejmě je R({p, ¬q}, {q, ¬r}, ¬q) = {p, ¬r} a rezoluční podmínka je splněna. Žádná další dvojice množinových reprezentací klauzulí rezoluční podmínku nesplňuje.

ÚLOHA 3 [Příklad.] Nechť L = hU, ci je jazyk s rovností, kde U je unární relační symbol a c je konstantní symbol. Buď dále S L-teorie s axiomy vyjadřujícími „existuje nekonečně mnoho prvků x, takových že U (x), a nekonečně mnoho y, takových že ¬U (y)ÿ. Kolik má S jednoduchých kompletních extenzí (JKE) až na ekvivalenci teorií? Řádně zdůvodněte kompletnost uvedených JKE. Řešení. 2

Uveďte zdůvodnění. Jde právě o extenze S o axiom U (c) resp. ¬U (c). Obě jsou kompletní dle kategorického kritéria kompletnosti. Nemají totiž zjevně konečné modely a jsou ω-kategorické.

Náhradní a bonusové testy TEST VPL, cvičení 14.1.13 — náhradní test bonusový

Jméno:

ÚLOHA 1 [Znění.] Formulujte větu o kompaktnosti predikátové logiky. Nekomentujte Řešení. Teorie má model, právě když každá její konečná podteorie má model.

ÚLOHA 2 [Příklad.] Buď P nekonečná množina prvovýroků, v ∈ P 2 model nad P a K = {v}. a) Je K axiomatizovatelná? b) Je K konečně axiomatizovatelná? Řešení. a) Ano. b) Ne.

Uveďte zdůvodnění. a) Teorie T = {pv(p) ; p ∈ P} axiomatizuje K. Přitom p1 značí p a p0 značí ¬p. b) Předpokládejme, že K je konečně axiomatizovatelná, tj. že K = MP (ϕ) pro nějakou formuli ϕ. Díky nekonečnosti P existuje p ∈ P nevyskytující se ve ϕ. Buď w ∈ P 2 model, který se shoduje s v všude kromě p a w(p) 6= v(p). Protože platnost formule ϕ v modelu v 0 zjevně závisí jen na hodnotách v 0 (q) prvovýroků q vyskytujících se ve ϕ, je w |= ϕ. Tedy w ∈ K = {v} a w 6= v — spor.

ÚLOHA 3 [Příklad.] SC0 je teorie v jazyce LS,0 = hS, 0i, kde S je unární funkční symbol, 0 je konstantní symbol, s axiomy (Q1) 0 6= Sx, (Q2) Sx = Sy → x = y, (Q7) x 6= 0 → (∃y)(Sy = x) a (SC-schema) x 6= S n x pro 0 < n ∈ N. Je SC0 otevřeně axiomatizovatelná teorie? Řešení. Ne.

Uveďte zdůvodnění. Pro model A = J1 (0) |= SC0 a jeho prvek a = h1, mi pro nějaké m ∈ Z volme B podstrukturu A generovanou prvkem a. Pak B ⊆ A, ale B 6|= SC0 (neboť a ∈ B je v B nenulový prvek, který nemá bezprostředního předchůdce, tj. B 6|=(Q7)). Tedy SC0 není otevřeně axiomatizovatelná podle kritéria otevřené axiomatizovatelnosti.

TEST VPL, cvičení 14.1.13 — náhradní test 1

Jméno:

ÚLOHA 1 [Znění.] Formulujte kategorické kritérium kompletnosti. Komentujte další pojmy, které uvedete. Řešení. Nechť teorie T nemá konečné modely a je κ-kategorická pro nějaké κ ≥ kL(T )k. Pak T je kompletní.

Uveďte komentář. T je kompletní, je-li bezesporná a každá její sentence je v ní dokazatelná nebo vyvratitelná. T je κ-kategorická, má-li až na izomorfizmus jediný model velikosti κ.

ÚLOHA 2 [Příklad.] Buďte p, q, r, s prvovýroky a ϕ výrok ((p ∨ q) → r) & s. Převeďte ϕ do konjunktivně normálního tvaru (CNF). Řešení. (¬p ∨ r) & (¬q ∨ r) & s

Uveďte zdůvodnění. Máme postupně ϕ ∼ (¬(p ∨ q) ∨ r) & s ∼ ((¬p & ¬q) ∨ r) & s ∼ (¬p ∨ r) & (¬q ∨ r) & s.

ÚLOHA 3 [Příklad.] Buď A = hR, ≤i, kde ≤ je obvyklé uspořádání reálných čísel, a X = [1, 3] uzavřený interval reálných čísel. Rozhodněte, zda je množina X definovatelná v A a) bez parametrů, b) s parametry. Řešení. a) Ne. b) Ano.

Uveďte zdůvodnění. a) Zobrazení h : r 7→ r + 1 je automorfizmus A a h[X] 6= X. Tedy X není definovatelná bez parametrů podle kritéria nedefinovatelnosti. b) X je definována formulí ϕ(x, y0 , y1 ) P (y0 ≤ x & x ≤ y1 ) z parametrů 1, 3.


Jméno:

ÚLOHA 1 [Znění.] Nechť T je teorie a χ(x, y) její formule taková, že v T je dokazatelné (∀x)(∃y)χ(x, y) a také (χ(x, y) & χ(x, y 0 )) → y = y 0 . Dále nechť F je l(x)-ární funkční symbol nevyskytující se v L(T ). Definujte extenzi teorie T o formulí χ definovaný funkční symbol F . Nekomentujte Řešení. Je to L(T ) ∪ hF i-teorie T ∪ {F (x) = y ↔ χ(x, y)}.

ÚLOHA 2 [Příklad.] Buď P konečná množina všech prvovýroků, |P| = l. Nechť dále S je P-teorie. Právě kolik je neekvivalentních teorií T takových, že T ∪ S je sporná teorie. Vyjádřete pomocí l a |MP (S)|. Řešení. l

P

22 −|M

(S)|

Uveďte zdůvodnění. Je T ∪ S sporná ⇔ MP (T ∪ S) = ∅. Užitím MP (T ∪ S) = MP (T ) ∩ MP (S) je poslední vztah dále ekvivalentní s MP (T ) ⊆ l P P 2 − MP (S). Tedy počet hledaných T je roven počtu podmnožin množiny P 2 − MP (S), což je právě 22 −|M (S)| .

ÚLOHA 3 [Příklad.] Buď A = h[1, ∞), ≤i a B = h[0, ∞), ≤i, kde [0, ∞) resp. [1, ∞) jsou polouzavřené intervaly reálných čísel a ≤ značí obvyklé uspořádání na [0, ∞) resp. [1, ∞). a) Je A elementární podstruktura B? b) Platí A ∼ = B? Řešení. a) Ne. b) Ano.

Uveďte zdůvodnění. a) Buď ϕ(x) formule „x je nejmenší prvekÿ. Pak A |= ϕ[1], avšak B 6|= ϕ[1]. b) Zobrazení x 7→ x − 1 je izomorfizmus A a B.


Jméno:

ÚLOHA 1 [Znění.] Formulujte větu o kompletnosti predikátové logiky. Komentujte další pojmy, které uvedete. Řešení. Pro teorii T a její formuli ϕ platí T |= ϕ ⇔ T ` ϕ.

Uveďte komentář. T |= ϕ, pokud A |= ϕ pro každý model A teorie T . T ` ϕ, existuje-li důkaz ϕ v T , tj. posloupnost ϕ0 , . . . , ϕn L(T )-formulí taková, že ϕ P ϕi pro nějaké i a každá ϕi je buďto logický axiom, mimologický axiom teorie T nebo je odvozeno pomocí odvozovacího pravidla modus ponens resp. generalizace z nějakých ϕj , ϕk resp. ϕj s j, k < i.

ÚLOHA 2 [Příklad.] Nechť T = {p ∨ ¬r, ¬p ∨ q, r} je teorie v jazyce obsahujícím prvovýroky p, q, r. Najděte: a) množinovou reprezentaci ◦ T teorie T , b) rezoluční uzávěr Rcl(◦ T ) množiny ◦ T . Zdůvodněte jen b). Řešení. a) ◦ T = {{p, ¬r}, {¬p, q}, {r}} b) Rcl(◦ T ) = ◦ T ∪ {{p}, {q}, {q, ¬r}}

Uveďte zdůvodnění. Zřejmě je každá z množin {p}, {q, ¬r} výsledkem aplikace rezoluční operace R(K, K 0 , λ) na nějaké K, K 0 ∈ ◦ T a literál λ. Dále {q} vzikne opět rezoluční operací z K = {p}, K 0 = {¬p, q} a λ P p. Žádné jiné korektní užití rezoluční operace nedává výsledek nepatřící do ◦ T ∪ {{p}, {q}, {q, ¬r}}.

ÚLOHA 3 [Příklad.] Buď A = hN, Si, kde S značí obvyklou operaci následníka v přirozených číslech, tj. S(n) = n + 1 pro n ∈ N. a) Kolik existuje různých podstruktur A? b) Kolik existuje vzájemně neizomorfních podstruktur A? Řešení. a) ω b) 1

Uveďte zdůvodnění. a) Podstruktury A jsou právě tvaru A N − n pro n ∈ N, tedy jich je ω. b) Jsou-li A N − n a A N − m dvě podstruktury A a n ≤ m, je zobrazení f : N − n → N − m dané vztahem f : x 7→ x + (m − n) izomorfizmem A N − n a A N − m.

ŘEŠENÉ ZÁPOČTOVÉ TESTY Z VÝROKOVÉ A PREDIKÁTOVÉ LOGIKY

Recommend Documents