10. ledna 2020 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 predikátové logiky, jeho formule ϕ, realizace M a teorie T.
O každém z následujících vztahů rozhodněte, zda má smysl, a pokud ano,
definujte jej: M |= ϕ, M |= T, M ϕ, M T, T |= ϕ, T ϕ.
(Nemusíte uvádět definici důkazu ani Tarského definici sémantiky.)
Příklad 2
10 bodů
Do slova A → A → ¬A → A doplňte závorky tak, aby vznikla formule výrokové
logiky s co nejkratší vytvořující posloupností. Uveďte dotyčnou vytvořující
posloupnost.
Příklad 3
10 bodů
Nechť značí operátor NOR, tj. ψ ξ ≈ ¬(ψ ∨ ξ). Dejte příklad formule ϕ
systému L( ) výrokové logiky, která je ekvivalentní formuli A → B.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
10. ledna 2020 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
30 bodů
Je dán jazyk L = {·, P} s rovností, kde · je binární funkční symbol a P je unární
predikátový symbol.
Realizaci M jazyka L nazveme pěknou, právě když splňuje obě následující podmínky:
nosičem je množina {a, b}∗ všech (konečných) slov nad abecedou {a, b};
· se realizuje jako zřetězení.
Zadejte uzavřenou formuli ϕ jazyka L takovou, že pro každou pěknou realizaci M platí
M |= ϕ, právě když P se realizuje jako „je palindrom , tj. PM = {u ∈ {a, b}∗: u = uR}.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
10. ledna 2020 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
30 bodů
Je dán jazyk L = {P, Q, R, f, c} bez rovnosti; mimologické symboly popisuje
tabulka:
symbol typ arita
P, Q, R predikátový 1
f funkční 1
c funkční 0
Uvažme následující teorii nad jazykem L:
T = {P(c), P(x) → Q(f(x)), Q(x) → R(f(x)), R(x) → P(f(x)), P(x) → (P(f(x)) ∨ R(f(x)))}
Popište kanonickou strukturu M teorie T. Dokažte, že do PM nepatří nic víc, než tvrdíte.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
10. ledna 2020 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 = {f} s rovností, kde f je unární funkční symbol. Rozhodněte a
dokažte, zda existuje teorie T jazyka L, jejíž modely jsou právě ty realizace M
jazyka L, kde:
a) právě tři individua mají nekonečně mnoho vzorů v fM;
b) nekonečně mnoho individuí má právě tři vzory v fM.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
10. ledna 2020 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 7
30 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.
Uvažme jeho realizaci M, kde nosičem je množina M = {0, 1, . . . , 11}, PM = {0, 4, 6, 8, 9} a fM je
permutace (0 1 2 3)(4 5 6 7)(8 9 10 11), tj. fM(n) = 4 n/4 + ((n + 1) mod 4) pro lib. n ∈ M.
Definice. Řekneme, že formule ϕ(x) jazyka L je rozpoznávající formule pro individuum n ∈ M,
právě když pro každé ohodnocení e platí M |= ϕ [e] ⇔ e(x) = n.
Rozhodněte a dokažte, pro která individua n ∈ M existuje jejich rozpoznávající formule.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.