Zkoušky z předmětu MA007 Matematická logika Obsah Podzim 2018 1. termín 3 2. termín 7 3. termín 12 4. termín 17 Podzim 2017 1. termín 22 2. termín 27 3. termín 32 4. termín 37 Podzim 2016 1. termín 42 2. termín 47 3. termín 52 4. termín 56 Podzim 2015 1. termín 60 2. termín 65 3. termín 69 4. termín 74 Podzim 2014 1. termín 79 2. termín 84 3. termín 89 4. termín 94 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. 14. ledna 2019 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ů 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 8 bodů Je dán jazyk L = ∅ s rovností. O každé z následujících formulí rozhodněte, ve kterých realizacích jazyka L platí (tj. např. v každé / v žádné / právě v těch s n-prvkovým nosičem (pro vhodné n ∈ N) apod.): a) ∀x(x = x); b) ∀x∀y(x = y); c) ∀x∃y(x = y); d) ∃x∀y(x = y). Příklad 3 10 bodů Dejte příklad formulí ϕ0, ϕ1, ϕ2 systému L(¬, ∧, ∨, →) výrokové logiky takových, že všechny jsou vzájemně ekvivalentní, každá obsahuje právě jeden výskyt binární spojky, a to každá jiné spojky, a pro každé i ∈ {0, 1, 2} formule ϕi obsahuje právě i výskytů negace. Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu. 14. ledna 2019 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 30 bodů Je dán jazyk L = {+, ·, P} s rovností; mimologické symboly popisuje tabulka: symbol typ arita + funkční 2 · funkční 2 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 sčítání; · se realizuje jako násobení; 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 (základního tvaru) čísla e(x) je roven šesti. Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu. 14. ledna 2019 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 36 bodů Jsou dány jazyky L1 = {f} a L2 = {f, P} s rovností, kde f je unární funkční symbol a P je unární predikátový symbol. Uvažme následující teorii T jazyka L2: T = {∃x∃y∃z(x = y ∧ x = z ∧ y = z ∧ ∀u(u = x ∨ u = y ∨ u = z)), P(x) ↔ ¬P(f(x))}. a) Dokažte, že teorie T není úplná. b) Dejte příklad konečné teorie S jazyka L1 tak, aby teorie T byla jejím konzervativním rozšířením. c) Je teorie S úplná? Správnost své odpovědi zdůvodněte. Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu. 14. ledna 2019 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 26 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 každé individuum má v zobrazení fM: a) konečně mnoho vzorů; b) nekonečně mnoho vzorů. Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu. 14. ledna 2019 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ť T je teorie jazyka L predikátové logiky, který obsahuje unární predikátový symbol P a 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 = PM, pokud dále víme, že teorie T je: a) bezesporná; b) bezesporná a henkinovská; c) úplná. Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu. 25. ledna 2019 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 10 bodů Je dán jazyk L = {P} bez rovnosti, kde P je binární predikátový symbol. Nechť pro formuli ϕ značí ϕx/y formuli, která vznikne z ϕ nahrazením všech výskytů proměnné x proměnnou y. Dejte příklad realizace M jazyka L a formule ϕ jazyka L takových, že x nemá vázaný výskyt ve ϕ a platí M |= ϕ, ale M |= ϕx/y. Příklad 3 10 bodů Dejte příklad formule ϕ, která je v disjunktivní 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. 25. ledna 2019 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 38 bodů Je dán jazyk L = {f} s rovností, kde f je binární funkční 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 a f se realizuje jako množinový rozdíl. Rozhodněte a dokažte, zda existuje formule ϕ(x) jazyka L taková, že pro každé ohodnocení e platí M |= ϕ [e], právě když: a) e(x) = ∅; b) e(x) = {1}; c) |e(x)| = 2. Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu. 25. ledna 2019 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 = {f} s rovností, kde f je unární funkční symbol. Uvažme teorii T = {∀x∃y(x = f(y)), f(x) = x, f(f(x)) = x} jazyka L. 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) Určete množinu A = {n ∈ N+: teorie T ∪ {ϕn} je úplná}. c) Dokažte, že pro n = max A + 1 teorie T ∪ {ϕn} není úplná. Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu. 25. ledna 2019 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 16 bodů Rozhodněte a dokažte, zda systém L(¬, ↔) výrokové logiky je plnohodnotný. Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu. 25. ledna 2019 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 30 bodů Nechť L je jazyk bez rovnosti obsahující unární predikátový symbol P a nulární funkční symbol c. Dále nechť ϕ, ψ jsou libovolné uzavřené formule jazyka L. Označme T1 = {ϕ}, T2 = {ψ} a T = {ϕ ∨ ψ} a dále nechť M1, M2, M jsou po řadě kanonické struktury teorií T1, T2, T. Rozhodněte a dokažte, zda nutně platí, že a) PM ⊆ PM1 ∪ PM2 ; b) PM ⊇ PM1 ∪ PM2 ; c) PM ⊆ PM1 ∩ PM2 ; d) PM ⊇ PM1 ∩ PM2 . Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu. 11. února 2019 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ž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 = {f, c} s rovností, kde oba symboly jsou funkční s aritami po řadě 2 a 0. Uvažme realizaci M jazyka L, kde nosičem je množina 2N všech podmnožin množiny N všech přirozených čísel a f se realizuje jako sjednocení. Ohodnocení e nazveme pěkné, právě když e(v) = ∅ pro každou proměnnou v různou od x a y (relevantní je tedy jen e(x) a e(y)). Stanovte cM tak, aby pro právě a) 1; b) 2; c) 3 pěkná ohodnocení e platilo M |= f(x, y) = c [e]; anebo konstatujte, že to není možné. V kladném případě uveďte i dotyčná ohodnocení. Příklad 3 10 bodů Nechť | značí operátor NAND, tj. ψ | ξ ≈ ¬(ψ ∧ ξ). Dejte příklad formule ϕ, která je v konjunktivní normální formě a je ekvivalentní formuli (A | B) | C. Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu. 11. února 2019 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 32 bodů Je dán jazyk L = {f, s, c} s rovností, kde všechny symboly jsou funkční s aritami po řadě 1, 1, 0. Realizaci M jazyka L nazveme pěknou, právě když splňuje všechny tři 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); c se realizuje jako 0. Dejte příklad teorie T jazyka L takové, že pro každou pěknou realizaci M platí M |= T, právě když pro každé n ∈ N platí fM(n) = 3n; a navíc: a) T je konečná; b) T je konečná a žádná formule ϕ ∈ T neobsahuje symbol c; c) každá formule ϕ ∈ T je uzavřená a atomická (tj. tvaru t1 = t2 pro vhodné termy t1, t2). Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu. 11. února 2019 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 jazyky L = {P, Q} a L = {P, Q, c, d} bez rovnosti, kde P, Q jsou unární predikátové symboly a c, d jsou konstanty. Dále uvažme teorie S1 = {P(c), Q(c)} a S2 = {P(c), Q(d)} nad jazykem L . a) Rozhodněte a dokažte, zda teorie S1 je rozšířením a zda je konzervativním rozšířením teorie S2. b) Dejte příklad konečných teorií T1 a T2 jazyka L tak, aby pro obě i ∈ {1, 2} byla teorie Si konzervativním rozšířením teorie Ti. c) Rozhodněte a dokažte, zda teorie S1 je rozšířením a zda je konzervativním rozšířením teorie T2. Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu. 11. února 2019 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 24 bodů Uvažujme následujících pět binárních spojek výrokové logiky: ∧, ∨, →, ↔, ⊕ (⊕ je xor, tj. v(ϕ ⊕ ψ) = (v(ϕ) + v(ψ)) mod 2). Vyberte z nich: a) dvě, které spolu tvoří plnohodnotný systém; b) čtyři, které spolu tvoří neplnohodnotný systém. Správnost své volby dokažte. Můžete využít faktu, že systém L(¬, ∧, ∨, →) je plnohodnotný. Plnohodnotnost jiných systémů nepředpokládejte. Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu. 11. února 2019 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ů 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. 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.