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.