16. ledna 2020 MA007 Matematická logika 2. 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ů
Definujte, co je jazyk L predikátové logiky (bez rovnosti).
Definujte, co je realizace M jazyka L.
Definujte, co je ohodnocení e v realizaci M.
Příklad 2
10 bodů
Je dán jazyk L = {P, Q} bez rovnosti, kde oba symboly jsou unární predikátové.
O každé z následujících formulí ϕ jazyka L rozhodněte, zda je to tautologie.
Pokud není, dejte příklad realizace M jazyka L takové, že M |= ϕ.
a) ϕ ≡ (∀x P(x) ∨ ∀x Q(x)) → ∀x(P(x) ∨ Q(x));
b) ϕ ≡ ∀x(P(x) ∨ Q(x)) → (∀x P(x) ∨ ∀x Q(x));
c) ϕ ≡ (∀x P(x) ∧ ∀x Q(x)) → ∀x(P(x) ∧ Q(x));
d) ϕ ≡ ∀x(P(x) ∧ Q(x)) → (∀x P(x) ∧ ∀x Q(x)).
Příklad 3
10 bodů
Dejte příklad formule ϕ, která je v konjunktivní normální formě a která je ekvivalentní
formuli (A → B) ↔ C.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
16. ledna 2020 MA007 Matematická logika 2. 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
26 bodů
Je dán jazyk L = {·} s rovností, kde · je binární funkční symbol. Uvažme jeho
realizaci M, kde nosičem je množina D4 všech symetrií čtverce a · se realizuje
jako skládání. (Připomeňme, že D4 sestává z identity, tří rotací a čtyř osových
symetrií.)
Zadejte formuli ϕ(x, y) jazyka L takovou, že pro každé ohodnocení e platí
M |= ϕ [e], právě když:
a) e(x) je identita;
b) e(x) je rotace o 90 ◦ (libovolným směrem);
c) e(x) je osová symetrie;
d) e(x) a e(y) jsou osové symetrie podle navzájem kolmých přímek.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
16. ledna 2020 MA007 Matematická logika 2. 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
48 bodů
Je dán jazyk L = {P, f, c} s rovností; mimologické symboly popisuje tabulka:
symbol typ arita
P predikátový 1
f funkční 1
c funkční 0
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 nejvýš n-prvkový.
b) Uvažme teorii T = {ϕ≤3, P(c), f(c) = c, f(x) = f(y) → x = y} nad jazykem L. Popište
kanonickou strukturu M teorie T. Dokažte, že do PM nepatří nic víc, než tvrdíte.
c) Dejte příklad formule ψ jazyka L tak, aby teorie T = T ∪ {ψ} byla nekonzervativním rozšířením
teorie T a přitom pro kanonickou strukturu M teorie T platilo M = M. Platí při vaší volbě
formule ψ, že teorie T je konzervativním rozšířením teorie T zúžené na jazyk {f, c} (s rovností)?
Lze zvolit formuli ψ i tak, aby odpověď na předchozí otázku byla opačná? Své odpovědi zdůvodněte.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
16. ledna 2020 MA007 Matematická logika 2. 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
20 bodů
Nechť z(ϕ) značí počet závorek ve formuli ϕ. Najděte co nejmenší r ∈ R takové,
že pro každou formuli ϕ systému L(¬, →) výrokové logiky platí z(ϕ) ≤ r · |ϕ|,
a dokažte, že tomu tak skutečně je.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
16. ledna 2020 MA007 Matematická logika 2. 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
26 bodů
Nechť L je jazyk aritmetiky. Z přednášky známe teorii jazyka L zvanou Peanova
aritmetika. Připomeňme, že PA = T ∪ T , kde
T = {s(x) = s(y) → x = y, s(x) = 0, x + 0 = x, x + s(y) = s(x + y), x · 0 = 0, x · s(y) = (x · y) + x}
a T = {(ϕ(0)∧∀x(ϕ(x) → ϕ(s(x)))) → ∀x ϕ(x) | ϕ(x) je formule jazyka L}. Další zajímavou teorií
jazyka L je tzv. Robinsonova aritmetika RA = T ∪ {∀x(x = 0 → ∃y(s(y) = x))}.
Dokažte, že Peanova aritmetika je nekonzervativním rozšířením Robinsonovy aritmetiky.
Nápověda: uvažte realizaci M jazyka L, kde nosičem je množina všech polynomů s celočíselnými
koeficienty, jejichž vedoucí koeficient je kladný, společně s nulovým polynomem (funkční symboly
jsou realizovány obvyklým způsobem).
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.