Logika dla informatyków

Egzamin połówkowy

30 listopada 2002

Za dzisiejszy egzamin można otrzymać od −40 do 40 punktów, za egzamin końcowy zaś od −60 do 60 punktów. Łącznie można więc otrzymać od −100 do 100 punktów. Jeżeli punktacja za zadanie egzaminacyjne wynosi n, znaczy to, że za rozwiązanie tego zadania można otrzymać od −n do n punktów. Punkty ujemne będą przyznawane za umieszczenie w rozwiązaniu odpowiedzi kompromitująco fałszywych. Za brak rozwiązania zadania otrzymuje się 0 punktów. Punkty z egzaminu zasadniczego przeliczają się na oceny zgodnie z tabelką:

−100 ÷ 32 ndst
33 ÷ 45 dst
46 ÷ 58 dst+
59 ÷ 71 db
72 ÷ 84 db+
85 ÷ 100 bdb

Czas trwania egzaminu wynosi 3 godziny zegarowe.

Zadanie 1 (8 punktów). Niech I oznacza relację identyczności na zbiorze X. Udowodnij, że relacja R ⊆ X × X jest relacją równoważności wtedy i tylko wtedy, gdy spełniony jest warunek

I ⊆ R ∧ R^{−1} D R ∧ RR ⊆ R.

Zadanie 2 (6 punktów). Pokaż, że

▷A_{1} ∪ A_{2}◁ · − ▷B_{1} ∪ B_{2}◁ ⊆ ▷A_{1} · − B_{1}◁ ∪ ▷A_{2} · − B_{2}◁.

Czy zawieranie

▷A_{1} ∩ A_{2}◁ · − ▷B_{1} ∩ B_{2}◁ ⊆ ▷A_{1} · − B_{1}◁ ∪ ▷A_{2} · − B_{2}◁

jest prawdziwe dla dowolnych zbiorów A_{1}, A_{2}, B_{1} i B_{2}? Odpowiedź uzasadnij.

Zadanie 3 (4 punkty). Udowodnij, że dla dowolnych rodzin zbiorów {A_{t} : t ∈ T } i {B_{t} : t ∈ T } zachodzi inkluzja

⋂_{t∈T}A_{t} ∪ ⋂_{t∈T}B_{t} ⊆ ⋂_{t∈T}▷A_{t} ∪ B_{t}◁.

Czy zachodzi też inkluzja odwrotna? Odpowiedź uzasadnij.

Ciąg dalszy na odwrocie → Zadanie 4 (4 punkty). Używając tylko kwantyfikatorów, zmiennych, nawiasów, spójników logicznych oraz symboli ∈, ℕ, C, ×, D i ≤ napisz formułę mówiącą, że wśród każdych trzech liczb naturalnych zawsze znajdą się dwie, których różnica jest nieujemna i parzysta. Czy taką formułę można zapisać używając wyłącznie kwantyfikatorów, zmiennych, nawiasów, spójników logicznych oraz symboli ∈, ℕ, C i D ? Używając tylko kwantyfikatorów, zmiennych, nawiasów, spójników logicznych oraz symboli ∈, ℕ, C, ×, D, < i symbolu f napisz formułę mówiącą, że jeśli funkcja f : ℕ → ℕ jest silnie rosnąca (dla większych argumentów ma większe wartości), to jej wartości są nieograniczone.

Zadanie 5 (7 punktów). Dla jakich zbiorów C prawdziwe jest zdanie: dla dowolnych zbiorów A i B zachodzi

A × C ⊆ B × C ⇒ A ⊆ B

Zadanie 6 (11 punktów). Zbiory A i B są równoliczne. Pokaż, że dla dowolnego zbioru C równoliczne są zbiory:

1. C × A i C × B,

2. C^{A} i C^{B},

3. A^{C} i B^{C}.

Zadanie 7 (bonusowe, 15 punktów). Niech A będzie zbiorem, a f — bijekcją przekształcającą zbiór A w A. Zdefiniujmy relację R ⊆ A^{2} przyjmując, że

xRy ⇔ f ▷x◁ D y.

Symbolem R_{∞} oznaczamy przechodnie domknięcie relacji R, czyli relację ⋃ _{nD1}^{∞} R^{n}, gdzie R^{1} D R oraz R^{nC1} D R^{n}R. Czy

1. R_{∞} jest relacją równoważności?

2. R_{∞} jest relacją równoważności, jeśli A jest zbiorem skończonym?

Odpowiedzi uzasadnij.

Zadanie 8 (bonusowe, 5 punktów). Niech A, B będą dowolnymi zbiorami. Kiedy równanie

A ∪ X D B

1. ma dokładnie jedno rozwiązanie,

2. ma nieskończenie wiele rozwiązań,

3. nie ma rozwiązań?

Odpowiedź uzasadnij.