Zkoušky z předmětu MA007
Matematická logika
Obsah
Podzim 2017
1. termín 3
2. termín 8
3. termín 13
4. termín 18
Podzim 2016
1. termín 23
2. termín 28
3. termín 33
4. termín 37
Podzim 2015
1. termín 41
2. termín 46
3. termín 50
4. termín 55
Podzim 2014
1. termín 60
2. termín 65
3. termín 70
4. termín 75
11. ledna 2018 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ů
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
14 bodů
Jsou dány jazyky L = {Q} a L = {Q, f, c} bez rovnosti; mimologické symboly
popisuje tabulka:
symbol typ arita
Q predikátový 4
f funkční 2
c funkční 0
Zadejte nějakou konečnou teorii T jazyka L tak, aby teorie T = {Q(x, c, f(x, x), f(x, c))} jazyka L
byla jejím konzervativním rozšířením.
Příklad 3
10 bodů
Najděte co nejkratší formuli ϕ systému L(¬, ∧, ∨, →, ↔) výrokové logiky, která
je ekvivalentní formuli ¬ ((A ∨ B) → C) ∨ ¬A ∨ (¬A ∧ C) .
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
11. ledna 2018 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
40 bodů
Je dán jazyk L = {D, f} bez rovnosti, kde D je binární predikátový symbol a
f je unární funkční symbol. Realizaci M jazyka L nazveme pěknou, právě když
splňuje obě následující podmínky:
nosičem je množina N = {0, 1, 2, . . . } všech přirozených čísel;
D se realizuje jako dělitelnost, tj. DM = {(n, nk) | n, k ∈ N}.
Zadejte uzavřenou formuli ϕ jazyka L takovou, že pro každou pěknou realizaci M platí
M |= ϕ, právě když pro každé n ∈ N platí fM(n) = n2.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
11. ledna 2018 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
34 bodů
Uvažme jazyky L1 = {f} a L2 = {f, g} s rovností, kde oba symboly jsou unární
funkční. Dále uvažme teorii
T = {∃x∃y∃z(x = y ∧ x = z ∧ y = z ∧ ∀u(u = x ∨ u = y ∨ u = z)), f(x) = f(y) → x = y}.
a) Intuitivně vysvětlete význam obou formulí.
b) Dokažte, že teorie T není úplná nad jazykem L1.
c) Dejte příklad formule ψ jazyka L1 tak, aby teorie U = T ∪{ψ} byla úplná nad jazykem L1. Platí
při vaší volbě formule ψ, že teorie U ∪ Uf/g je úplná nad jazykem L2? Lze zvolit formuli ψ i tak,
aby odpověď na předchozí otázku byla opačná? Své odpovědi zdůvodněte.
(Značením Uf/g rozumíme teorii, která vznikne z teorie U nahrazením všech výskytů symbolu f
symbolem g ve všech jejích formulích.)
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
11. ledna 2018 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
20 bodů
Je dán jazyk L = {f, g} s rovností, kde oba symboly jsou funkční s aritami po
řadě 1 a 3. Nechť pro term t jazyka L značí |t| jeho délku (tj. celkový počet
znaků) a dále nechť #f (t), resp. #g(t) značí počet symbolů f, resp. g v termu t.
Zformulujte všeobecně platnou závislost |t| na #f (t) a #g(t) (tj. exaktně řečeno: najděte funkci
h: N2 → N takovou, že pro každý term t jazyka L platí |t| = h(#f (t), #g(t))). Dokažte tuto závislost
strukturální indukcí.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
11. ledna 2018 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
22 bodů
Nechť T je bezesporná teorie jazyka L bez rovnosti, který obsahuje unární predikátový
symbol P a nulární funkční symbol (tj. konstantu) c. Dále nechť M značí
kanonickou strukturu teorie T. Rozhodněte a dokažte, zda nutně platí, že
a) T |= P(c) ⇒ M |= P(c);
b) M |= P(c) ⇒ T |= P(c);
c) T |= P(x) ⇒ M |= P(x);
d) M |= P(x) ⇒ T |= P(x).
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
18. ledna 2018 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ů
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ů
Nechť t je term, který je substituovatelný za proměnnou x ve formuli ϕ, a u
je term, který je substituovatelný za proměnnou y ve formuli ϕ. Rozhodněte a
dokažte, zda nutně platí, že term u je substituovatelný za proměnnou y ve formuli
ϕ(x/t).
Příklad 3
10 bodů
Definice. Řekneme, že valuace v je pěkná, právě když v(X) = 0 pro každou
výrokovou proměnnou X různou od A, B, C. (Existuje tedy právě 8 pěkných
valuací.)
Dejte příklad co nejkratší formule ϕ systému L(¬, ∧, →) výrokové logiky, která je pravdivá při právě
5 pěkných valuacích.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
18. ledna 2018 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
44 bodů
Je dán jazyk L = {+, ·} s rovností, kde oba symboly jsou binární funkční. Uvažme
jeho realizaci M, kde nosičem je množina Z6 všech zbytkových tříd modulo 6,
+ se realizuje jako sčítání a · jako násobení.
Definice. Řekneme, že formule ϕ(x) jazyka L je rozpoznávající formule pro individuum a ∈ Z6,
právě když pro každé ohodnocení e platí M |= ϕ [e] ⇔ e(x) = a.
a) Pro každé a ∈ Z6 dejte příklad jeho rozpoznávající formule.
b) Rozhodněte a dokažte, pro která a ∈ Z6 existuje rozpoznávající formule neobsahující symbol +.
c) Rozhodněte a dokažte, pro která a ∈ Z6 existuje rozpoznávající formule neobsahující symbol ·.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
18. ledna 2018 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
34 bodů
Je dán jazyk L = {∼, f, c} s rovností; mimologické symboly popisuje tabulka:
symbol typ arita
∼ predikátový 2
f funkční 1
c funkční 0
Uvažme teorii T = {f11(c) = f(c), x ∼ f6(x), (x ∼ y ∧ y ∼ z) → x ∼ z} nad jazykem L.
Popište kanonickou strukturu M teorie T. Dokažte, že do ∼M nepatří nic víc, než tvrdíte.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
18. ledna 2018 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
24 bodů
Je dán jazyk L = {Q} bez rovnosti, kde Q je predikátový symbol arity 5. Nechť
k(ϕ), i(ϕ) a p(ϕ) značí po řadě počet kvantifikátorů, počet implikací a celkový
počet výskytů proměnných ve formuli ϕ jazyka L. Zformulujte všeobecně platnou
závislost p na k a i (tj. exaktně řečeno: najděte funkci h: N2 → N takovou, že pro každou formuli ϕ
jazyka L platí p(ϕ) = h(k(ϕ), i(ϕ))). Dokažte tuto závislost strukturální indukcí.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
18. ledna 2018 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
18 bodů
Nechť S je libovolný neprázdný soubor formulí výrokové logiky a ϕ formule taková,
že S |= ϕ. Rozhodněte a dokažte, zda nutně existuje soubor T ⊆ S takový,
že T |= ϕ, a navíc:
a) T je konečný;
b) T je jednoprvkový.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
29. ledna 2018 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ů
Dejte příklad plnohodnotného systému L spojek výrokové logiky.
Definujte abecedu výrokové logiky pro systém L.
Definujte, co je formule systému L výrokové logiky.
Příklad 2
12 bodů
Je dán jazyk L = {P, f} bez rovnosti, kde P je unární predikátový a f unární
funkční symbol. Dále víme, že ϕ je formule jazyka L. Vyberte pravdivá tvrzení:
a) Ve formuli ϕ se musí / může a nemusí / nemůže vyskytovat symbol P.
b) Ve formuli ϕ se musí / může a nemusí / nemůže vyskytovat symbol f.
c) Ve formuli ϕ se musí / může a nemusí / nemůže vyskytovat symbol ∀.
d) Ve formuli ϕ se musí / může a nemusí / nemůže vyskytovat symbol →.
e) Ve formuli ϕ se musí / může a nemusí / nemůže vyskytovat symbol ⇒.
f) Ve formuli ϕ se musí / může a nemusí / nemůže vyskytovat symbol pro proměnnou
predikátové logiky.
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.
29. ledna 2018 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
30 bodů
Je dán jazyk L = {s, P} s rovností, kde s je unární funkční symbol a P je unární
predikátový symbol.
Realizaci M jazyka L nazveme pěknou, právě když platí obě následující podmínky:
nosičem je množina N = {0, 1, 2, . . . } všech přirozených čísel;
s se realizuje jako následník (tj. přičtení jedničky).
Zadejte uzavřenou formuli ϕ jazyka L takovou, že pro každou pěknou realizaci M platí
M |= ϕ, právě když PM = {n ∈ N: 5 | n2 − 1} = {1, 4, 6, 9, 11, 14, 16, 19, . . . }.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
29. ledna 2018 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
44 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
Pro libovolné n ∈ N+ uvažme teorii Tn = {P(c), P(fn(c)), (P(x) ↔ P(y)) → x = y} nad jazykem L.
Označme Mn kanonickou strukturu teorie Tn. Rozhodněte a dokažte, pro která n ∈ N+ platí:
a) Mn |= P(x);
b) Tn |= P(x).
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
29. ledna 2018 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
24 bodů
Nechť T, U jsou teorie jazyka L predikátové logiky takové, že T ⊂ U. Rozhodněte
a dokažte, zda nutně platí, že:
a) teorie T je rozšířením teorie U;
b) teorie U je rozšířením teorie T;
c) teorie T není rozšířením teorie U.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
29. ledna 2018 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 7
20 bodů
Nechť L = {0, s, +, ·} je jazyk aritmetiky (s rovností) a N je jeho standardní
realizace (tj. nosič je N, symbol 0 se realizuje jako číslo 0, s jako následník, +
jako sčítání a · jako násobení). Z přednášky známe teorii jazyka L zvanou Peanova
aritmetika (PA). Připomeňme, že lze psát PA = T1 ∪ T2 ∪ T3 ∪ T4, kde T1 vynucuje chování s (je
injektivní a nula nemá vzor), T2 induktivně vynucuje chování +, T3 induktivně vynucuje chování ·
a T4 hovoří o principu matematické indukce.
a) Uveďte explicitně teorii T4.
b) Zformulujte první Gödelovu větu o neúplnosti.
c) Rozhodněte a dokažte, zda pro každou formuli ϕ jazyka L platí N |= ϕ ⇒ PA ϕ.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
7. února 2018 MA007 Matematická logika 4. 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
16 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
Dále víme, že t je term jazyka L a u je uzavřený term jazyka L. Vyberte pravdivá tvrzení:
a) V termu t se musí / může a nemusí / nemůže vyskytovat symbol P.
b) V termu t se musí / může a nemusí / nemůže vyskytovat symbol f.
c) V termu t se musí / může a nemusí / nemůže vyskytovat symbol c.
d) V termu t se musí / může a nemusí / nemůže vyskytovat symbol pro proměnnou
predikátové logiky.
e) V termu u se musí / může a nemusí / nemůže vyskytovat symbol =.
f) V termu u se musí / může a nemusí / nemůže vyskytovat symbol f.
g) V termu u se musí / může a nemusí / nemůže vyskytovat symbol c.
h) V termu u se musí / může a nemusí / nemůže vyskytovat symbol pro proměnnou
predikátové logiky.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
7. února 2018 MA007 Matematická logika 4. 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 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.
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ž platí obě následující podmínky:
nosičem je množina N = {0, 1, 2, . . . } všech přirozených čísel;
+ se realizuje jako sčítání.
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 mocnina dvojky , tj. PM = {2k | k ∈ N}.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
7. února 2018 MA007 Matematická logika 4. 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
40 bodů
Jsou dány funkční symboly ·, f, c s aritami po řadě 2, 1, 0 a jazyky L = {·},
L = {·, f, c} s rovností. Dále uvažme formule
ϕ ≡ ∀x∀y(x · y = y · x),
ψ1 ≡ ∀x∃y(x · y = x),
ψ2 ≡ ∃y∀x(x · y = x),
ψ3 ≡ ∀x(x · c = x),
ψ4 ≡ ∀x(x · f(x) = x),
teorie T1 = {ϕ, ψ1}, T2 = {ϕ, ψ2} jazyka L a teorie T3 = {ϕ, ψ3}, T4 = {ϕ, ψ4} jazyka L .
Pro každé (i, j) ∈ {1, 2, 3, 4}2 rozhodněte, zda teorie Ti
je konzervativním rozšířením / je nekonzervativním rozšířením / není rozšířením
teorie Tj. Pro (i, j) = (3, 1) a (i, j) = (3, 4) své odpovědi dokažte.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
7. února 2018 MA007 Matematická logika 4. 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
28 bodů
Uvažme systémy A = L(∧, ∨) a B = L(¬, ↔) výrokové logiky.
Definice. Řekneme, že formule ϕ je A-vyjádřitelná (resp. B-vyjádřitelná),
právě když existuje formule ψ systému A (resp. B) taková, že ϕ ≈ ψ.
Dejte příklad formule ϕ (obsahující libovolné spojky výrokové logiky), která:
a) je A-vyjádřitelná i B-vyjádřitelná;
b) je A-vyjádřitelná, ale není B-vyjádřitelná;
c) není A-vyjádřitelná, ale je B-vyjádřitelná.
Dokažte správnost svých odpovědí.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
7. února 2018 MA007 Matematická logika 4. 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
16 bodů
Definice. Teorie T, T jazyka L se nazývají sémanticky ekvivalentní (resp.
sémanticky komplementární), právě když pro každou realizaci M jazyka L platí
M |= T ⇔ M |= T (resp. M |= T ⇔ M |= T ).
Nechť T, T jsou sémanticky komplementární teorie jazyka L. Rozhodněte a dokažte, zda nutně
platí, že existují konečné teorie U, U jazyka L takové, že U je sémanticky ekvivalentní s T a
U je sémanticky ekvivalentní s T .
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
6. ledna 2017 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, f, c} s rovností; mimologické symboly popisuje tabulka:
symbol typ arita
P predikátový 1
f funkční 3
c funkční 0
Definujte, co je term jazyka L.
Definujte realizaci tM[e] termu t při ohodnocení e v realizaci M jazyka L.
Dejte příklad 3 uzavřených termů jazyka L.
Příklad 2
12 bodů
Uveďte nějakou nejkratší vytvořující posloupnost formule ((A → B) ∨ (A ∧ ¬A)).
Kolik nejkratších vytvořujících posloupností má tato formule?
Příklad 3
10 bodů
Dejte příklad formule ϕ tak, aby formule (A → B) → ϕ a A → (B → ϕ)
a) byly ekvivalentní;
b) nebyly ekvivalentní.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
6. ledna 2017 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
50 bodů
Je dán jazyk L = {·, c} s rovností, kde oba symboly jsou funkční s aritami po
řadě 2 a 0. Uvažme jeho realizaci M, kde nosičem je množina N+ všech kladných
celých čísel, · se realizuje jako násobení a
a) cM = 2; b) cM = 64; c) cM = 100; d) cM = 2500.
Rozhodněte a dokažte, zda existuje formule ϕ(x) jazyka L taková, že pro každé ohodnocení e platí
M |= ϕ [e], právě když e(x) je mocninou dvojky.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
6. ledna 2017 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
24 bodů
Je dán jazyk L = { } s rovností, kde je binární predikátový symbol. Dále
uvažme formule
ϕ1 ≡ x x,
ϕ2 ≡ (x y ∧ y x) → x = y,
ϕ3 ≡ (x y ∧ y z) → x z,
ϕ4 ≡ ∃x∀y(y x),
ϕ5a ≡ ∃x∀y(x y),
ϕ5b ≡ ∃x∀y(y x → x = y)
a teorie A = {ϕ1, ϕ2, ϕ3, ϕ4, ϕ5a}, B = {ϕ1, ϕ2, ϕ3, ϕ4, ϕ5b} jazyka L.
a) Intuitivně vysvětlete význam jednotlivých formulí.
b) Dokažte, že teorie B není rozšířením teorie A.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
6. ledna 2017 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
24 bodů
Definice. Nechť M je libovolná množina a g: M → M. Prvek a ∈ M nazveme
cyklickým vzhledem ke g, právě když a ∈ {gn(a) | n ∈ N+}.
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) každé individuum je cyklické vzhledem k fM;
b) žádné individuum není cyklické vzhledem k fM.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
6. ledna 2017 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
20 bodů
Nechť T je bezesporná teorie jazyka L bez rovnosti, který obsahuje unární predikátový
symbol P a nulární funkční symbol (tj. konstantu) c. Nechť M je
kanonická struktura teorie T a označme M její nosič. Dále uvažme množinu
A = {t ∈ M: T ¬P(t)}. Rozhodněte a dokažte, zda nutně platí, že
a) A ⊆ PM;
b) A ⊇ PM.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
18. ledna 2017 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ů
Je dán jazyk L = {P} bez rovnosti, kde P je unární predikátový symbol.
Definujte, co je formule ϕ jazyka L.
Definujte indukcí vzhledem ke struktuře formule ϕ množinu FV (ϕ) všech volných proměnných ve
formuli ϕ.
Příklad 2
10 bodů
O každém z následujících systémů spojek výrokové logiky rozhodněte, zda je
plnohodnotný:
a) L(¬, →);
b) L(¬, ↔);
c) L(¬, ∧);
d) L(∧, ∨, →);
e) L(∧, ∨, →, ↔).
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
18. ledna 2017 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 3
10 bodů
Definice. Řekneme, že formule ϕ závisí na proměnné X, právě když existují
valuace v, v takové, že v(Y ) = v (Y ) pro všechny proměnnné Y různé od X,
ale v(ϕ) = v (ϕ). Nechť Z(ϕ) značí množinu právě těch proměnných, na kterých
formule ϕ závisí.
Dejte příklad formulí ϕ, ψ, ξ takových, že Z(ϕ) = {A, B}, Z(ψ) = {A, C}, Z(ξ) = {B, C} a
Z((ϕ ∧ ψ) → ξ) = {B, C}.
Příklad 4
30 bodů
Je dán jazyk L = {·} s rovností, kde · je binární funkční symbol. Uvažme jeho
realizaci S, kde nosičem je množina S4 všech permutací čtyřprvkové množiny
a · se realizuje jako skládání. (Připomeňme, že S4 sestává z identity, šesti 4-cyklů,
osmi 3-cyklů, šesti 2-cyklů (transpozic) a tří 2-2-cyklů.)
Zadejte formuli ϕ(x) jazyka L takovou, že pro každé ohodnocení e platí
S |= ϕ [e], právě když:
a) e(x) je identita;
b) e(x) je 3-cyklus;
c) e(x) je 4-cyklus;
d) e(x) je 2-2-cyklus.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
18. ledna 2017 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
40 bodů
Je dán jazyk L = {P, f} s rovností, kde P je unární predikátový symbol a f je
binární funkční symbol. Dále uvažme teorii T = {ϕ1, ϕ2, ϕ3} jazyka L, kde:
ϕ1 ≡ ∃x∃y∃z(x = y ∧ x = z ∧ y = z ∧ ∀u(u = x ∨ u = y ∨ u = z)),
ϕ2 ≡ ∀x∃y∀z(f(y, z) = x),
ϕ3 ≡ ∀x∀y((P(x) ∧ P(y)) → x = y).
a) Pro každé i ∈ {1, 2, 3} dejte příklad realizace Mi jazyka L takové, že Mi |= T, ale Mi |= T −{ϕi}.
b) Dokažte, že teorie T není úplná.
c) Dejte příklad formule ψ jazyka L tak, aby teorie T ∪ {ψ} byla úplná.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
18. ledna 2017 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ů
Jsou dány teorie T1, T2 a formule ϕ. Označme U1 = T1 ∪ {ϕ}, U2 = T2 ∪ {ϕ};
přitom formuli ϕ i teorie T1, T2, U1, U2 uvažujeme nad stejným jazykem. Uvažme
dále následující tvrzení:
Teorie T1 je rozšířením teorie T2. (1)
Teorie U1 je rozšířením teorie U2. (2)
Rozhodněte a dokažte, zda nutně platí, že:
a) (1) ⇒ (2);
b) (2) ⇒ (1).
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
18. ledna 2017 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
16 bodů
Je dán jazyk L = {P} bez rovnosti, kde P je unární predikátový symbol. Najděte
až na ekvivalenci všechny teorie jazyka L. (Tedy exaktně řečeno: najděte n ∈ N
a teorie T1, T2, . . . , Tn jazyka L takové, že každá teorie jazyka L je ekvivalentní
právě jedné z teorií T1, T2, . . . , Tn.)
Příklad 8
14 bodů
Nechť T je henkinovská teorie jazyka s rovností, která má aspoň jeden model
s nekonečným nosičem. Dokažte, že T musí být nekonečná.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
27. ledna 2017 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ů
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
14 bodů
Jsou dány jazyky L = {Q} a L = {Q, f, c} bez rovnosti; mimologické symboly
popisuje tabulka:
symbol typ arita
Q predikátový 4
f funkční 1
c funkční 0
Zadejte nějakou konečnou teorii T jazyka L tak, aby teorie T = {Q(x, f(x), c, f(c))} jazyka L byla
jejím konzervativním rozšířením.
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.
27. ledna 2017 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
44 bodů
Je dán jazyk L = {+, ·, f} s rovností, kde všechny symboly jsou funkční s aritami
po řadě 2, 2, 1. Realizaci M jazyka L nazveme pěknou, právě když platí všechny
následující podmínky:
nosičem je množina N = {0, 1, 2, . . . } všech přirozených čísel;
+ se realizuje jako sčítání;
· se realizuje jako násobení.
a) Zadejte uzavřenou formuli ϕ jazyka L takovou, že pro každou pěknou realizaci M platí
M |= ϕ, právě když f se realizuje jako Fibonacciho posloupnost, tj.
fM = {(0, 0), (1, 1), (2, 1), (3, 2), (4, 3), (5, 5), (6, 8), (7, 13), (8, 21), (9, 34), . . . }.
b) Jako v a), navíc ϕ nesmí obsahovat symbol ·.
c) Formulujte tvrzení o existenci a vlastnostech formule zvané Gödelův predikát β.
d) Zadejte formuli ϕ(x, y) jazyka L takovou, že pro každou pěknou realizaci M a každé ohodnocení
e platí
M |= ϕ [e], právě když e(x)-té Fibonacciho číslo je e(y).
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
27. ledna 2017 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
36 bodů
Je dán jazyk L = {P, f, c, d} s rovností; mimologické symboly popisuje tabulka:
symbol typ arita
P predikátový 1
f funkční 1
c funkční 0
d funkční 0
Uvažme teorii T = {f2(c) = c ∨ f3(d) = d, f4(c) = f5(d), P(f6(c))} nad jazykem L.
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.
27. ledna 2017 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
20 bodů
Uvažujme výrokovou logiku se spojkami ¬, → a Lukasiewiczovým odvozovacím
systémem z přednášky. Nechť S označuje soubor všech formulí, které mají vytvořující
posloupnost délky 3, ale nemají žádnou kratší. Rozhodněte a dokažte,
zda:
a) S (A → B);
b) S |= ¬A.
Příklad 7
16 bodů
Nechť P, Q jsou unární predikátové symboly. Dejte příklad úplné teorie T1 nad
jazykem {P} bez rovnosti a úplné teorie T2 nad jazykem {Q} bez rovnosti. Platí
při vaší volbě teorií T1 a T2, že teorie T = T1 ∪ T2 je úplná nad jazykem {P, Q}
bez rovnosti? Lze zvolit teorie T1 a T2 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.
8. února 2017 MA007 Matematická logika 4. 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ů
Dejte příklad plnohodnotného systému L spojek výrokové logiky.
Definujte abecedu výrokové logiky pro systém L.
Definujte, co je formule systému L výrokové logiky.
Příklad 2
12 bodů
Je dán jazyk L = {P} bez rovnosti, kde P je binární predikátový symbol. O každém
z následujících předpisů rozhodněte, zda korektně zadává teorii jazyka L.
Pokud ne, vysvětlete, v čem je problém.
a) {∃x0∃x1 . . . ∃xn
n
i=1
P(xi−1, xi) | n ∈ {1, 2, 3, 4, 5}};
b) {∃n∃x0∃x1 . . . ∃xn
n
i=1
P(xi−1, xi)};
c) {∃x0∃x1 . . . ∃xn
n
i=1
P(xi−1, xi) | n ∈ N+
};
d) {∃x0∃x1 · · ·
i∈N+
P(xi−1, xi)}.
Příklad 3
10 bodů
Definice. Řekneme, že valuace v je pěkná, právě když v(X) = 0 pro každou
výrokovou proměnnou X různou od A, B, C. (Existuje tedy právě 8 pěkných
valuací.)
Dejte příklad formule ϕ systému L(∧, →) výrokové logiky, která je pravdivá při právě 3 pěkných
valuacích.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
8. února 2017 MA007 Matematická logika 4. 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
36 bodů
Je dán jazyk L = {+, ·} s rovností, kde oba symboly jsou binární funkční. Uvažme
jeho realizaci M, kde nosičem je množina Z4 všech zbytkových tříd modulo 4,
+ se realizuje jako sčítání a · jako násobení.
Definice. Řekneme, že formule ϕ(x) jazyka L je rozpoznávající formule pro individuum a ∈ Z4,
právě když pro každé ohodnocení e platí M |= ϕ [e] ⇔ e(x) = a.
a) Pro každé a ∈ Z4 dejte příklad jeho rozpoznávající formule.
b) Rozhodněte a dokažte, pro která a ∈ Z4 existuje rozpoznávající formule neobsahující symbol +.
c) Rozhodněte a dokažte, pro která a ∈ Z4 existuje rozpoznávající formule neobsahující symbol ·.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
8. února 2017 MA007 Matematická logika 4. 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ů
Nechť T1 a T2 jsou teorie nad stejným jazykem, přičemž T1 je úplná a T2 je jejím
rozšířením. Rozhodněte a dokažte, zda nutně platí, že teorie T2
a) je bezesporná;
b) není úplná;
c) je sporná nebo úplná.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
8. února 2017 MA007 Matematická logika 4. 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
52 bodů
Je dán jazyk L = {∼, f, g, c} s rovností; mimologické symboly popisuje tabulka:
symbol typ arita
∼ predikátový 2
f funkční 1
g funkční 1
c funkční 0
Uvažme teorii T = {x ∼ f(x), f(g(x)) = x, g(f(x)) = x} nad jazykem L.
a) Dejte příklad modelu M teorie T takového, že M |= f(c) = c.
b) Pro každý uzavřený term t jazyka L určete jeho realizaci tM ve zvoleném modelu M.
c) Jak se realizuje symbol ∼ v kanonické struktuře teorie T?
Dokažte správnost svých odpovědí.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
5. ledna 2016 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ů
Uvažme systém L(¬, ∨) výrokové logiky, obsahující jen negaci a disjunkci.
Definujte, co je formule systému L.
Definujte, co je valuace (výrokových proměnných).
Definujte rozšíření valuace z výrokových proměnných na všechny formule systému L.
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) P(x, f(x));
c) f(x, f(x));
d) g(x, f(x), f(f(x))).
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
5. ledna 2016 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 3
10 bodů
Najděte co nejkratší formuli ϕ systému L(¬, ∧, ∨, →) výrokové logiky, která je
ekvivalentní formuli ((¬B → ¬A) ∧ C) ∨ ¬((A ∧ ¬B) ∨ C) .
Příklad 4
30 bodů
Nechť N = {0, 1, 2, . . . } označuje množinu všech přirozených čísel. Je dán jazyk
L = {⊕, t} s rovností, kde ⊕ je binární funkční a t unární funkční symbol. Uvažme
jeho realizaci M, kde nosičem je množina NN všech (nekonečných) posloupností
přirozených čísel, ⊕ se realizuje jako sčítání po složkách (tj. (a0, a1, a2, . . . ) ⊕M (b0, b1, b2, . . . ) =
(a0 + b0, a1 + b1, a2 + b2, . . . )) a t se realizuje jako tail (tj. tM((a0, a1, a2, . . . )) = (a1, a2, a3, . . . )).
Zadejte formuli ϕ(x) jazyka L takovou, že pro každé ohodnocení e platí
M |= ϕ [e], právě když:
a) e(x) je neklesající;
b) e(x) = (1, 0, 0, 0, . . . );
c) e(x) je rostoucí.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
5. ledna 2016 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
40 bodů
Je dán jazyk L = {P} s rovností, kde P je unární predikátový symbol. Rozhodněte
a dokažte, zda existuje teorie T jazyka L, jejíž modely jsou právě realizace
M jazyka L, kde množina PM:
a) má méně než 10 prvků;
b) má méně než 10 prvků nebo je nekonečná;
c) má více než 10 prvků, ale konečně mnoho;
d) má více než 10 prvků.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
5. ledna 2016 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 = {P, f, c} s rovností; mimologické symboly popisuje tabulka:
symbol typ arita
P predikátový 1
f funkční 1
c funkční 0
Uvažme teorii
T = {f4
(c) = c, ¬P(c),
3
i=1
P(fi
(c)), ∀x P(f(x)) → P(x) ∨ P(f(f(x))) }
nad jazykem L. 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.
5. ledna 2016 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
20 bodů
Je dán jazyk L = {f} s rovností, kde f je unární funkční symbol. Uvažme jeho
realizaci M, kde nosičem je množina Z všech celých čísel, fM(n) = n + 1 pro
každé nezáporné n ∈ Z a fM(n) = n + 2 pro každé záporné n ∈ Z. Rozhodněte
a dokažte, pro která n ∈ Z existuje formule ϕ(x) jazyka L taková, že pro každé ohodnocení e platí
M |= ϕ [e], právě když e(x) = n.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
15. ledna 2016 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ů
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ů
Jsou dány jazyky L = {Q} a L = {Q, f, c} bez rovnosti; mimologické symboly
popisuje tabulka:
symbol typ arita
Q predikátový 3
f funkční 1
c funkční 0
Zadejte nějakou konečnou teorii T jazyka L tak, aby teorie T = {Q(x, f(x), c)} jazyka L byla jejím
konzervativním rozšířením.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
15. ledna 2016 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 3
10 bodů
Dejte příklad formule ϕ tak, aby formule (ϕ → A) → B a ϕ → (A → B)
a) byly ekvivalentní;
b) nebyly ekvivalentní.
Příklad 4
40 bodů
Je dán jazyk L = {·, s, f} s rovností, kde všechny symboly jsou funkční s aritami
po řadě 2, 1, 1.
Realizaci M jazyka L nazveme pěknou, právě když platí všechny následující podmínky:
nosičem je množina N+ všech kladných celých čísel;
· se realizuje jako násobení;
s se realizuje jako následník (tj. přičtení jedničky).
Zadejte uzavřenou formuli ϕ jazyka L takovou, že pro každou pěknou realizaci M platí
M |= ϕ, právě když pro každé n ∈ N+ je fM(n) rovno počtu dělitelů čísla n.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
15. ledna 2016 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
40 bodů
Jsou dány jazyky L = {P, f} a 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
Dále uvažme formule
ϕ1 ≡ ∃x1∃x2∃x3∃x4


4
i=1
4
j=i+1
xi = xj ∧ ∀y
4
i=1
y = xi

 ,
ϕ2 ≡ ∀x∃y(f(y) = x),
ϕ3 ≡ ∃x(f6(x) = x),
ϕ4 ≡ ∃x∃y x = y ∧ ∀z(P(z) ↔ (z = x ∨ z = y))
a teorii T = {ϕ1, ϕ2, ϕ3, ϕ4} nad jazykem L.
a) Intuitivně vysvětlete význam jednotlivých formulí.
b) Dokažte, že teorie T není úplná.
c) Najděte formuli ψ jazyka L tak, aby teorie T ∪ {ψ} nad jazykem L byla úplná. Platí při vaší
volbě formule ψ, že teorie T ∪ {ψ, P(c)} nad jazykem L je úplná? 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.
15. ledna 2016 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
30 bodů
Je dán jazyk L = {∼, X, Y, f, c} bez rovnosti; mimologické symboly popisuje
tabulka:
symbol typ arita
∼ predikátový 2
X predikátový 0
Y predikátový 0
f funkční 1
c funkční 0
Uvažme teorii T = {X ∨ Y, X ↔ c ∼ x, Y ↔ x ∼ c} jazyka L. Popište kanonickou strukturu M
teorie T. O každé uzavřené atomické formuli jazyka L, která je podle vás pravdivá v M, dokažte,
že tomu tak skutečně je.
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 |= ϕ nebo T |= ψ, pak T |= ϕ ∨ ψ.
b) Pokud T |= ϕ ∨ ψ, pak T |= ϕ nebo T |= ψ.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
25. ledna 2016 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ů
Nechť P je binární predikátový symbol a f je unární funkční symbol. O každé
z následujících formulí rozhodněte, zda je v ní term f(y) substituovatelný za
proměnnou x, a pokud ano, uveďte výslednou formuli po substituci:
a) P(x, y);
b) ∀y P(x, y);
c) ∀x∀y P(x, y).
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
25. ledna 2016 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 3
10 bodů
Dejte příklad formule ϕ, která je v disjunktivní normální formě a která je ekvivalentní
formuli (A ↔ B) → C.
Příklad 4
30 bodů
Je dán jazyk L = {+, ·} s rovností, kde oba symboly jsou binární funkční. Uvažme
jeho realizaci C, kde nosičem je množina C všech komplexních čísel, + se realizuje
jako sčítání a · jako násobení.
Zadejte formuli ϕ(x1, x2, x3, x4) jazyka L takovou, že pro každé ohodnocení e platí
C |= ϕ [e], právě když obrazy čísel e(x1), e(x2), e(x3), e(x4)
v Gaussově rovině leží ve vrcholech čtverce.
(Nápověda: můžete nejprve vynutit {e(x1), e(x2), e(x3), e(x4)} = {1, i, −1, −i}.)
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
25. ledna 2016 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
30 bodů
Jsou dány jazyky L = {P} a L = {P, c} bez rovnosti, kde P je binární predikátový
symbol a c je nulární funkční symbol (konstanta).
Dále uvažme teorii T1 = {∀x∃y P(x, y)} nad jazykem L, teorii T2 = {∃y∀x P(x, y)} nad jazykem L
a teorii T3 = {∀x P(x, c)} nad jazykem L . Pro každé (i, j) ∈ {1, 2, 3}2 rozhodněte, zda teorie Ti
je konzervativním rozšířením / je nekonzervativním rozšířením / není rozšířením
teorie Tj. Pro (i, j) = (2, 1) svou odpověď dokažte.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
25. ledna 2016 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
20 bodů
Je dán jazyk L = {∼, f, c} s rovností; mimologické symboly popisuje tabulka:
symbol typ arita
∼ predikátový 2
f funkční 1
c funkční 0
a) Dejte příklad realizace M jazyka L takové, že platí obě následující podmínky:
pro nekonečně mnoho uzavřených termů t jazyka L platí M |= t ∼ f(t);
pro nekonečně mnoho uzavřených termů t jazyka L platí M |= t ∼ f(t).
b) Rozhodněte a dokažte, zda taková realizace M může splňovat M |= x = y ↔ x ∼ y.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
25. ledna 2016 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 7
16 bodů
Nechť A, B jsou unární predikátové symboly. V níže uvedených formulích nahraďte
každý výskyt písmene Q všeobecným nebo existenčním kvantifikátorem
(různé výskyty můžou být nahrazeny různými kvantifikátory) tak, aby ekvivalence
formulí byla splněna; anebo konstatujte, že to není možné.
a) Qx(A(x) ∧ B(x)) ≈ Qx A(x) ∧ Qx B(x);
b) Qx(A(x) ∨ B(x)) ≈ Qx A(x) ∨ Qx B(x);
c) Qx(A(x) → B(x)) ≈ Qx A(x) → Qx B(x);
d) Qx(A(x) ↔ B(x)) ≈ Qx A(x) ↔ Qx B(x).
Příklad 8
24 bodů
Nechť L = {0, s, +, ·} je jazyk aritmetiky (s rovností) a N je jeho standardní
realizace (tj. nosič je N, symbol 0 se realizuje jako číslo 0, s jako následník, +
jako sčítání a · jako násobení). Zformulujte první Gödelovu větu o neúplnosti.
Dále rozhodněte a dokažte, zda existuje teorie T jazyka L taková, že
a) T je konečná a úplná;
b) T je konečná a N |= T;
c) T je úplná a N |= T;
d) T je konečná, úplná a N |= T.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
10. února 2016 MA007 Matematická logika 4. 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ů
Jsou dány jazyky L = {P} a L = {P, Q} bez rovnosti, kde P, Q jsou unární
predikátové symboly. Zadejte nějakou konečnou teorii T jazyka L tak, aby teorie
T = {∀x(P(x) → Q(x)), ∀x(P(x) → ¬Q(x))} jazyka L byla jejím konzervativním
rozšířením.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
10. února 2016 MA007 Matematická logika 4. 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 3
10 bodů
Nechť → je binární spojka se sémantikou ϕ → ψ ≈ ¬(ϕ → ψ), • je unární spojka
se sémantikou •ϕ ≈ ϕ → ϕ a ◦ je unární spojka se sémantikou ◦ϕ ≈ ¬(ϕ → ϕ).
Dejte příklad formule ϕ logického systému L(→, •, ◦), která je ekvivalentní formuli
A ∨ B.
Příklad 4
30 bodů
Je dán jazyk L = {s, P} s rovností, kde s je unární funkční symbol a P je unární
predikátový symbol.
Realizaci M jazyka L nazveme pěknou, právě když platí obě následující podmínky:
nosičem je množina N = {0, 1, 2, . . . } všech přirozených čísel;
s se realizuje jako následník (tj. přičtení jedničky).
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 násobek tří , tj. PM = {3k | k ∈ N}.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
10. února 2016 MA007 Matematická logika 4. 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ů
Definice. Teorie T, T jazyka L se nazývají sémanticky ekvivalentní, právě když
pro každou realizaci M jazyka L platí M |= T ⇔ M |= T .
Rozhodněte a dokažte, zda:
a) ke každé teorii existuje konečná teorie, která je s ní sémanticky ekvivalentní;
b) ke každé konečné teorii existuje jednoprvková teorie, která je s ní sémanticky ekvivalentní.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
10. února 2016 MA007 Matematická logika 4. 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 = {P, f, c, d} s rovností; mimologické symboly popisuje tabulka:
symbol typ arita
P predikátový 1
f funkční 2
c funkční 0
d funkční 0
Uvažme teorii T = {f(x, y) = f(y, x), f(f(x, y), z) = f(x, f(y, z)), P(f(f(c, c), d))} jazyka L. Jak
se realizuje symbol P v kanonické struktuře M teorie T? Dokažte správnost své odpovědi.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
10. února 2016 MA007 Matematická logika 4. 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
10 bodů
Nechť S, T jsou splnitelné soubory formulí výrokové logiky. Rozhodněte a dokažte,
zda nutně platí, že soubor S ∪ T je:
a) splnitelný;
b) nesplnitelný.
Příklad 8
20 bodů
Formulujte větu o dedukci pro Lukasiewiczův odvozovací systém z přednášky.
Dejte příklad vlastního odvozovacího systému (rovněž pro systém L(¬, →)),
který je korektní a pro nějž platí právě jedna z (meta)implikací věty o dedukci.
Zdůvodněte správnost vaší volby.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
18. prosince 2014 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, kdy platí M |= P(x) [e].
Definujte, kdy platí M |= x = y [e].
Příklad 2
10 bodů
Je dán jazyk L = {P, f, c} bez rovnosti; mimologické symboly popisuje tabulka:
symbol typ arita
P predikátový 1
f funkční 1
c funkční 0
Dejte příklad realizace M jazyka L takové, že pro právě 3 uzavřené termy t jazyka L platí M |= P(t).
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
18. prosince 2014 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 3
10 bodů
Nechť ◦ je unární spojka odpovídající „konstantní nepravdě , tj. ◦ϕ ≈ ¬(ϕ → ϕ).
Dejte příklad formule ϕ logického systému L(→, ◦), která je ekvivalentní formuli
A ∧ B.
Příklad 4
36 bodů
Je dán jazyk L = {+, ·} s rovností, kde oba mimologické symboly jsou binární
funkční. Uvažme jeho realizaci R, kde nosičem je množina R všech reálných čísel,
+ se realizuje jako sčítání a · jako násobení.
Zadejte formuli ϕ(x, y, z) jazyka L takovou, že pro každé ohodnocení e platí
R |= ϕ [e], právě když e(x), e(y), e(z) jsou délky stran nějakého trojúhelníku.
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.
18. prosince 2014 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
40 bodů
Jsou dány jazyky L1 = {·, n}, L2 = {·, n, f}, L3 = {·, n, f, p} s rovností; mimologické
symboly popisuje tabulka:
symbol typ arita
· funkční 2
n funkční 0
f funkční 1
p funkční 0
Uvažme formule ϕ ≡ x·y = y ·x ∧ (x·y)·z = x·(y ·z) ∧ x·n = x, ψ ≡ x·f(x) = n, ξ ≡ f(p) = p
a teorie T1 = {ϕ} nad jazykem L1, T2 = {ϕ, ψ} nad jazykem L2 a T3 = {ϕ, ψ, ξ} nad jazykem L3.
Rozhodněte a dokažte, zda
a) teorie T2 je rozšířením teorie T1;
b) teorie T2 je konzervativním rozšířením teorie T1;
c) teorie T3 je konzervativním rozšířením teorie T2;
d) teorie T2 je konzervativním rozšířením teorie T3.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
18. prosince 2014 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
24 bodů
Uvažme výrokovou logiku se spojkami ¬, → a Lukasiewiczovým odvozovacím
systémem z přednášky. Nechť S označuje soubor všech splnitelných formulí. Rozhodněte
a dokažte, zda
a) S A → B;
b) S |= ¬(A → A);
c) lze soubor S rozdělit na soubory S1, S2 (tj. S1 ∩ S2 = ∅ a S1 ∪ S2 = S) tak, že oba dva soubory
S1, S2 jsou splnitelné.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
18. prosince 2014 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
20 bodů
Zformulujte nutnou a postačující podmínku (∗) pro jazyk L predikátové logiky,
aby mělo smysl uvažovat kanonickou strukturu M teorie T nad jazykem L
(tj. aby M měla neprázdný nosič).
Dále rozhodněte a dokažte, zda pro kanonickou strukturu M každé úplné teorie T nad každým
jazykem L bez rovnosti, který splňuje podmínku (∗), platí, že M je modelem teorie T.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
14. ledna 2015 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ů
Je dán jazyk L = {P, g, c} s rovností; mimologické symboly popisuje tabulka:
symbol typ arita
P predikátový 1
g funkční 2
c funkční 0
Definujte, co je term jazyka L.
Definujte, co je realizace tM[e] termu t při ohodnocení e v realizaci M jazyka L.
Dejte příklad 3 uzavřených termů jazyka L.
Příklad 2
10 bodů
Nechť S, T jsou nesplnitelné soubory formulí výrokové logiky. Rozhodněte a dokažte,
zda nutně platí, že je nesplnitelný i soubor
a) S ∩ T;
b) S ∪ T.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
14. ledna 2015 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 3
10 bodů
Nechť V označuje soubor všech proměnných výrokové logiky. Valuaci v nazveme
pěknou, právě když v(X) = 0 pro všechny X ∈ V −{A, B, C} (existuje tedy právě
8 pěkných valuací). Dejte příklad formule ϕ logického systému L(¬, →), která je
pravdivá při právě 5 pěkných valuacích.
Příklad 4
30 bodů
Je dán jazyk L = {·, c, P} s rovností; mimologické symboly popisuje tabulka:
symbol typ arita
· funkční 2
c funkční 0
P predikátový 1
Uvažme jeho realizaci M, kde:
nosičem je množina Q+ všech kladných racionálních čísel;
· se realizuje jako násobení, tj. ·M = {((x, y), xy) | x, y ∈ Q+};
c se realizuje jako osmička, tj. cM = 8;
P se realizuje jako „je celé číslo , tj. PM = N+.
Zadejte formuli ϕ(x) jazyka L takovou, že pro každé ohodnocení e platí
M |= ϕ [e], právě když jmenovatel čísla e(x) (v základním tvaru) je sudý.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
14. ledna 2015 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
40 bodů
Nechť P je binární predikátový symbol. Rozhodněte a dokažte, zda existuje splnitelná
teorie T, která má jen modely s nekonečným nosičem, a navíc:
a) T je nad jazykem {P} s rovností;
b) T je konečná a nad jazykem {P} s rovností;
c) T je nad jazykem {P} bez rovnosti;
d) T je konečná a nad jazykem {P} bez rovnosti.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
14. ledna 2015 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ů
Je dán jazyk L = {a, b, c, P, X, Y } s rovností; mimologické symboly popisuje
tabulka:
symbol typ arita
a, b, c funkční 0
P predikátový 1
X, Y predikátový 0
Uvažme formule ϕ1 ≡ X ∨ Y , ϕ2 ≡ X ↔ (P(a) ∧ P(b)), ϕ3 ≡ Y ↔ (P(a) ∧ P(c)), ϕ4 ≡ x = y a
teorie T1 = {ϕ1, ϕ2, ϕ3}, T2 = {ϕ1, ϕ2, ϕ3, ϕ4} nad jazykem L.
Popište kanonickou strukturu M1 teorie T1 a kanonickou strukturu M2 teorie T2.
Rozhodněte, zda M1 |= ϕ1, M1 |= ϕ2, M1 |= ϕ3, M2 |= ϕ1, M2 |= ϕ2, M2 |= ϕ3, M2 |= ϕ4.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
14. ledna 2015 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
30 bodů
Nechť T1 je teorie nad jazykem L1 bez rovnosti a T2 je teorie nad jazykem L2 bez
rovnosti, přičemž T1 je úplná a T2 je jejím konzervativním rozšířením. Rozhodněte
a dokažte, zda nutně platí, že T2 je úplná, pokud dále víme, že
a) L1 = L2;
b) L1 = L2.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
26. ledna 2015 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ů
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ů
Nechť S je soubor formulí výrokové logiky, který má nekonečně mnoho splnitelných
podsouborů. Rozhodněte a dokažte, zda nutně platí, že S je splnitelný.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
26. ledna 2015 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 3
10 bodů
Dejte příklad formule ϕ, která je v konjunktivní normální formě a která je ekvivalentní
formuli (A → B) → C.
Příklad 4
30 bodů
Je dán jazyk L = {⊂} bez rovnosti, kde ⊂ je binární predikátový symbol. Uvažme
jeho realizaci M, kde:
nosičem je množina 2N všech podmnožin množiny N všech přirozených čísel;
⊂ se realizuje jako ostrá množinová inkluze.
Zadejte formuli ϕ(x, y) jazyka L takovou, že pro každé ohodnocení e platí
M |= ϕ [e], právě když množiny e(x), e(y) jsou navzájem svými komplementy.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
26. ledna 2015 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
40 bodů
Nechť f je unární a c nulární funkční symbol. Uvažme teorii
T = {∀x∃y(f(y) = x), ∀x(f(x) = x), ∃x(f5(x) = x), ψ}, kde
ψ ≡ ∃x1∃x2∃x3∃x4∃x5


5
i=1
5
j=i+1
xi = xj ∧ ∀y
5
i=1
y = xi

 .
a) Intuitivně vysvětlete význam jednotlivých formulí.
b) Dokažte, že teorie T není úplná nad jazykem {f, c} (s rovností).
c) Je tato teorie úplná nad jazykem {f} (s rovností)? Svou odpověď zdůvodněte.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
26. ledna 2015 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
20 bodů
Je dán jazyk L = {f, g}, kde oba symboly jsou funkční s aritami po řadě 1 a 3.
Nechť pc(t), pf (t) a pg(t) označují po řadě počet čárek, počet symbolů f a počet
symbolů g v termu t jazyka L. Zformulujte všeobecně platnou závislost pc na pf
a pg (tj. exaktně řečeno: najděte funkci h: N2 → N takovou, že pro každý term t jazyka L platí
pc(t) = h(pf (t), pg(t))). Dokažte tuto závislost strukturální indukcí.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
26. ledna 2015 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 7
14 bodů
Definice. Formule ξ jazyka L predikátové logiky se nazývá tautologie, právě když
M |= ξ pro každou realizaci M jazyka L.
Je dán jazyk L = {P} bez rovnosti, kde P je binární predikátový symbol, a dále je dána formule
ψ ≡ ∀x∃y P(x, y). Dejte příklad formule ϕ jazyka L takové, že formule ψ je sémantickým důsledkem
teorie {ϕ}, ale ϕ → ψ není tautologie. Dokažte, že při vaší volbě formule ϕ skutečně platí, že ϕ → ψ
není tautologie.
Příklad 8
16 bodů
Je dán jazyk L = {c} s rovností, kde c je nulární funkční symbol (konstanta).
Dokažte, že teorie T = ∅ nad jazykem L není henkinovská. Dejte příklad splnitelné
henkinovské teorie nad jazykem L.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
5. února 2015 MA007 Matematická logika 4. 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žme systém L(¬, ∧) výrokové logiky, obsahující jen negaci a konjunkci.
Definujte, co je formule systému L.
Definujte, co je valuace (výrokových proměnných).
Definujte rozšíření valuace z výrokových proměnných na všechny formule systému L.
Příklad 2
10 bodů
Je dán jazyk L = {A, B, C, D, E} bez rovnosti. O každém z jeho mimologických
symbolů určete, jakého je typu (predikátový/funkční) a jakou má aritu, víte-li,
že (A(B, C(x, D(y)), z) → E) je formule jazyka L.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
5. února 2015 MA007 Matematická logika 4. 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 3
10 bodů
Nechť značí operátor NOR, tj. ψ ξ ≈ ¬(ψ ∨ ξ). Dejte příklad formule ϕ
logického systému L( ), která je ekvivalentní formuli A → B.
Příklad 4
30 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 {a, b}+ všech neprázdných slov nad abecedou {a, b};
· se realizuje jako zřetězení.
Zadejte formuli ϕ(x) jazyka L takovou, že pro každé ohodnocení e platí
M |= ϕ [e], právě když slovo e(x) začíná a končí na stejné písmeno.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
5. února 2015 MA007 Matematická logika 4. 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} s rovností, kde P je binární predikátový symbol. Dále jsou
dány forumle ϕ, ψ, ξ, ζ a teorie T1, T2, T3 nad jazykem L:
ϕ ≡ ∃x∃y∃z(x = y ∧ x = z ∧ y = z)
ψ ≡ ∀x∀y P(x, y) T1 = {ϕ, ψ}
ξ ≡ ∀x∃y P(x, y) T2 = {ϕ, ξ, ¬ζ}
ζ ≡ ∃y∀x P(x, y) T3 = {ϕ, ¬ξ, ζ}
O každé z teorií T1, T2, T3 rozhodněte a dokažte, zda je splnitelná.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
5. února 2015 MA007 Matematická logika 4. 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
36 bodů
Je dán jazyk L = {P, f, g, c} s rovností; mimologické symboly popisuje tabulka:
symbol typ arita
P predikátový 1
f funkční 1
g funkční 1
c funkční 0
Uvažme teorii T = {P(c), ∀x(P(x) ↔ P(f(f(x)))), ∀x(f(g(x)) = x), ∀x(g(f(x)) = x)} ∪
∪ {∀x(fn(x) = x) | n ∈ N+} nad jazykem L. Popište kanonickou strukturu M teorie T. Dbejte
přitom též na precizní popis nosiče. 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.
5. února 2015 MA007 Matematická logika 4. 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
24 bodů
Definice. Obrazem zobrazení g: A → B rozumíme množinu {g(a) | a ∈ A}.
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 nad jazykem L taková, že pro libovolnou realizaci M jazyka L platí
M |= T, právě když obraz zobrazení fM je
a) konečný;
b) nekonečný.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.