Celkové hodnocení BI-MLO (nevyplňujte!) Semestr Cvičení Aktivita
Zkouška 2. část 3. část
1. část
Ústní
Celkem
Známka
BI-MLO
Písemná zkouška
9. února 2016
Matematická logika
FIT ČVUT v Praze
Varianta B
Jméno:
Příjmení:
Login:
Podpis:
Písemná zkouška trvá 90 minut a sestává ze tří částí. Pro úspěšné složení zkoušky potřebujete z každé části získat alespoň polovinu bodů. Pracujte samostatně a pamatujte, že ČVUT považuje opisování za závažný prohřešek. Nepoužívejte žádné pomůcky kromě tužky. Pište čitelně!
1. část První část zkoušky sestává z osmi elementárních otázek po čtyřech bodech. Ze čtyř nabízených odpovědí mohou být správné všechny, žádná, nebo cokoli mezi tím. Správné odpovědi zřetelně zaznamenejte do tabulky níže. Bodové hodnocení: úplné korektní řešení 4b, jedna odlišnost 2b, více odlišností 0b. Pro úspěšné složení této části potřebujete získat 16 bodů z 32 možných.
1
2
3
4
a) b) c) d) Body
1
5
6
7
8
2
1. Které z následujících formulí jsou výrokové tautologie? a) (P ⇔ Q) ∨ (¬P ⇔ Q) b) ¬(P ⇒ Q) ⇔ (¬P ⇒ ¬Q) c) ¬(P ⇔ Q) ⇒ (¬P ⇔ ¬Q) d) (P ⇒ Q) ∨ (Q ⇒ P ) 2. Nalezněte minimální tvary Booleovské funkce f (A, B, C) = a) (A ∧ ¬B) ∨ (¬A ∧ C) ∨ (B ∧ ¬C) b) (A ∧ ¬B) ∨ (¬A ∧ C) ∨ (B ∧ C) c) (¬A ∧ B) ∨ (A ∧ ¬C) ∨ (¬B ∧ ¬C) d) (¬A ∧ B) ∨ (A ∧ ¬C) ∨ (¬B ∧ C)
P
m(1, 2, 3, 4, 5, 6)
3. Které z následujících formulí jsou důsledky {P ⇒ (Q ∨ R), R ⇒ (S ∨ T ), ¬(P ⇒ Q), T ⇒ S} ? a) ¬P b) ¬P ∨ P c) ¬P ∨ S ∨ T d) ¬P ∨ Q ∨ ¬R ∨ ¬S ∨ T 4. Booleova algebra výroků nad výrokovými proměnnými A, B, C, D má a) čtyři atomy b) osm atomů c) osm prvků d) šestnáct prvků 5. Které z následujících formulí jazyka se dvěma unárními predikáty p, q jsou logicky platné? a) ((∀x)p(x) ∨ (∀x)q(x)) ⇒ ((∀x)(p(x) ∨ q(x))) b) ((∃x)(p(x) ∧ q(x))) ⇒ ((∃x)p(x) ∧ (∃x)q(x)) c) ((∀x)(p(x) ⇒ q(x))) ⇒ ((∀x)p(x) ⇒ (∀x)q(x)) d) ((∃x)p(x) ∧ (∃x)q(x)) ⇒ ((∃x)(p(x) ∧ q(x))) 6. Úplná teorie v jazyce L a) obsahuje jako axiom buďto ϕ nebo ¬ϕ, pro každou formuli ϕ jazyka L b) dokazuje buďto ϕ nebo ¬ϕ, pro každou formuli ϕ jazyka L c) dokazuje buďto ϕ nebo ¬ϕ, pro každou uzavřenou formuli ϕ jazyka L d) dokazuje ϕ ∨ ¬ϕ, pro každou formuli ϕ jazyka L 7. Uvažte následující interpretace jazyka s jediným binárním relačním symbolem R. Které z nich splňují sentenci (∀x)(∀y)(∃z)(R(x, z) ∧ R(y, z)) ? a) množina celých čísel opatřená obvyklým uspořádáním b) množina přirozených čísel opatřená relací dělitelnosti c) množina všech konečných podmnožin celých čísel opatřená inkluzí d) množina všech přímek v rovině opatřená relací rovnoběžnosti 8. Na Booleově algebře (B, +, ·, 0 , 0, 1) uvažte binární operaci x4y = (x · y 0 ) + (y · x0 ). Které z následujících formulí platí ve struktuře (B, 4, 0)? a) (∀x)(x40 = x) b) (∀x)(x4x = 0) c) (∀x)(∃y)(x4y = 0) d) (∀x)(∃y)((x4y) = (y4x)0 )
3
2. část Druhá část sestává ze tří početních příkladů po šesti bodech. Podrobně a přehledně popište své kroky a úvahy. Pro úspěšné složení této části potřebujete získat 9 bodů z 18 možných.
Pomocná tabulka pro hodnocení 2. části (nevyplňujte!): Příklad
1
2
3
Celkem
1. Najděte disjunktivní a úplný konjunktivní tvar následujícíh formulí. S pomocí normálního tvaru pak rozhodněte, která formule je (nebo není) logickým důsledek kterých ostatních. P ⇒ (Q ∨ R), P ⇒ (Q ⇒ (R ⇒ P )), (P ⇒ Q) ∨ (P ⇒ R)
4
2. V jazyce {<, =, 0, f }, kde f je unární funkční symbol, napište formuli, která vyjadřuje následující tvrzení o reálných funkcích: ostře klesající funkce nemá minimum. Pak formuli znegujte tak, aby negace stála jen u atomických podformulí.
3. Uvažte následující formuli v jazyce s binárním predikátem r. Rozhodněte, zda je tato formule logicky platná, splnitelná, či kontradiktorická. Pokud není kontradiktorická, popište nějakou intepretaci, kde platí. Pokud není logicky platná, popište nějakou intepretaci, kde neplatí. (∃x)(∀y)(r(x, y) ⇒ x = y)
5
3. část Třetí část sestává ze čtyř teoretických otázek po pěti bodech. Přesně formulujte požadované definice, věty a důkazy, podrobně a přehledně popište své úvahy a argumenty. Pro úspěšné složené této části potřebujete získat 10 bodů z 20 možných.
Pomocná tabulka pro hodnocení 3. části (nevyplňujte!): Příklad
1
2
3
4
Celkem
1. Vyslovte větu o kompaktnosti výrokové logiky a s její pomocí ukažte, že je-li výroková formule důsledkem výrokové teorie, je už důsledkem nějaké její konečné části.
2. Definujte pojem modelu teorie a sporné teorie v predikátové logice. Ukažte, že teorie, která má model, je bezesporná.
6
3. Definujte uspořádání Booleovy algebry oběma obvyklými způsoby a ukažte, že jsou ekvivalentní. Dále ukažte, že pro každé dva prvky každé Booleovy algebry platí x ∧ y ≤ y ≤ x ∨ y.
4. Pro každou z následujících grup napište nějakou formuli jazyka {∗,−1 , 1} teorie grup, která v dané grupě platí, ale v ostatních dvou neplatí. (a) celá čísla s obvyklým sčítáním (b) kladná reálná čísla s obvyklým násobením (c) permutace množiny {1, 2, 3} se skládáním
