8. ledna 2019 MA007 Matematická logika 1. 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ů
Je dán jazyk L = {P} s rovností, kde P je unární predikátový symbol.
Definujte, co je realizace M jazyka L.
Definujte, co je ohodnocení e v realizaci M.
Definujte sémantiku formulí ϕ jazyka L, tj. kdy platí M |= ϕ [e].
Příklad 2
10 bodů
Víme, že P je predikátový symbol a f, g jsou funkční symboly. O každém z následujících
výrazů rozhodněte, zda se může jednat o term, a pokud ano, napište
pro něj nějakou vytvořující posloupnost:
a) x;
b) f(f(x), x);
c) P(f(x), x);
d) g(f(f(x)), y, f(x)).
Příklad 3
12 bodů
Nechť značí operátor NOR, tj. ψ ξ ≈ ¬(ψ ∨ ξ). Dejte příklad formule ϕ
systému L( ) výrokové logiky, která je ekvivalentní formuli (A ↔ B). Určete
délku vaší formule ϕ.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
8. ledna 2019 MA007 Matematická logika 1. 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
42 bodů
Je dán jazyk L = {+, ·, f} s rovností, kde všechny symboly jsou funkční s aritami
po řadě 2, 2, 1. Uvažme jeho realizaci R, kde nosičem je množina R všech reálných
čísel, + se realizuje jako sčítání, · jako násobení a f jako sinus.
Zadejte formuli ϕ(x) jazyka L takovou, že pro každé ohodnocení e platí
R |= ϕ [e], právě když e(x) = π.
Dokažte, že každá formule s touto vlastností musí obsahovat symbol ·.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
8. ledna 2019 MA007 Matematická logika 1. 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
36 bodů
Je dán jazyk L = {P, f, a, b, c} s rovností; mimologické symboly popisuje tabulka:
symbol typ arita
P predikátový 1
f funkční 1
a, b, c funkční 0
Uvažme teorii T = {P(a) ∨ P(b), P(x) → P(f(x)), f(f(x)) = c} nad jazykem L.
Popište kanonickou strukturu M teorie T. Dokažte, že do PM nepatří nic víc, než tvrdíte.
Dále rozhodněte a dokažte, zda teorie T má model s nekonečným nosičem.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
8. ledna 2019 MA007 Matematická logika 1. 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
30 bodů
Je dán jazyk L = {Q} s rovností, kde Q je binární predikátový symbol. Rozhodněte
a dokažte, zda existuje teorie T jazyka L, jejíž modely jsou právě ty realizace
M jazyka L, kde QM je relace ekvivalence na nosiči M, která má:
a) právě dvě nekonečné třídy rozkladu;
b) právě dvě třídy rozkladu a obě jsou nekonečné.
Příklad 7
10 bodů
Nechť T je soubor formulí výrokové logiky a ϕ, ψ jsou libovolné formule. Rozhodněte
a dokažte, zda nutně platí následující tvrzení:
a) Pokud T |= ϕ ∧ ψ, pak T |= ϕ a T |= ψ.
b) Pokud T |= ϕ ∨ ψ, pak T |= ϕ nebo T |= ψ.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.