27. ledna 2020 MA007 Matematická logika 3. termín list učo body Oblast strojově snímatelných informací. Své UČO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. Příklad 1 20 bodů Uvažujme Lukasiewiczův odvozovací systém z přednášky. Uveďte odvozovací pravidlo modus ponens. Definujte, co je důkaz formule (nemusíte uvádět, jak vypadají schémata axiomů). Definujte, kdy je odvozovací systém korektní. Definujte, kdy je odvozovací systém úplný. Je Lukasiewiczův odvozovací systém korektní? Je úplný? Příklad 2 10 bodů Je dán jazyk L = {P, f} s rovností, kde P je unární predikátový symbol a f je unární funkční symbol. Napište nějakou vytvořující posloupnost pro formuli (∀x ¬P(f(f(x))) → f(y) = x) i pro všechny termy, které se v ní vyskytují. Příklad 3 10 bodů Dejte příklad formulí ϕ, ψ systému L(→) výrokové logiky tak, aby formule A → ϕ a B → ψ byly ekvivalentní, ale nebyly tautologie. Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu. 27. ledna 2020 MA007 Matematická logika 3. termín list učo body Oblast strojově snímatelných informací. Své UČO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. Příklad 4 40 bodů Je dán jazyk L = {Q} bez rovnosti, kde Q je ternární predikátový symbol. Uvažme jeho realizaci M, kde nosičem je množina N = {0, 1, 2 . . . } všech přirozených čísel a QM = {(a, b, c) ∈ N3: b je aritmetický průměr čísel a, c}. Zadejte formuli ϕ(x, y) jazyka L takovou, že pro každé ohodnocení e platí M |= ϕ [e], právě když: a) e(x) = e(y); b) e(x) = 0; c) e(x) je liché číslo; d) e(x) je násobek tří; e) e(x) = 42. Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu. 27. ledna 2020 MA007 Matematická logika 3. termín list učo body Oblast strojově snímatelných informací. Své UČO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. Příklad 5 54 bodů Je dán jazyk L = {P, f} s rovností, kde P je unární predikátový symbol a f je unární funkční symbol. a) Pro každé n ∈ N+ dejte příklad formule ϕn jazyka L takové, že pro každou realizaci M jazyka L platí M |= ϕn, právě když nosič realizace M je právě n-prvkový. b) Uvažme teorii T = {ϕ6, P(f(x)), 2 i=1 fi(x) = x, P(y) → 3 i=1 fi(x) = y} nad jazykem L. Dokažte, že teorie T není úplná. c) Dejte příklad konečné teorie S jazyka {P} s rovností tak, aby teorie T byla jejím konzervativním rozšířením. Dokažte správnost své odpovědi. d) Existuje uzavřená formule ψ jazyka L taková, že obě teorie T1 = T ∪ {ψ}, T2 = T ∪ {¬ψ} jsou neúplné a jsou nekonzervativními rozšířeními teorie T? Svou odpověď zdůvodněte. Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu. 27. ledna 2020 MA007 Matematická logika 3. termín list učo body Oblast strojově snímatelných informací. Své UČO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. Příklad 6 26 bodů Definice. Nechť M je realizace jazyka L. Individuum a ∈ M nazveme popsatelné, právě když je hodnotou nějakého uzavřeného termu, tj. existuje uzavřený term t jazyka L takový, že tM = a. Realizaci M nazveme pěknou, právě když každé její individuum je popsatelné. Dejte příklad konečného jazyka L s rovností, pro nějž a) existuje; b) neexistuje teorie T, jejíž modely jsou právě pěkné realizace jazyka L. Dokažte správnost své odpovědi. Ve svém řešení se neodvolávejte na Löwenheimovu-Skolemovu větu (nebo ji dokažte). Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.