Logika dla informatyków

Egzamin końcowy

3 lutego 2003

Zadanie 1 (16 pkt). Niech ϕ będzie formułą zdaniową zbudowaną ze zmiennych zdaniowych i spójników alternatywy, koniunkcji i negacji. Przez wartościowanie formuły ϕ rozumiemy funkcję, która zmiennym wystepującym w formule ϕ przyporządkowuje wartości ze zbioru {0, 1}. Niech n będzie dodatnią liczbą naturalną.

a) (6 pkt) Udowodnij, że dla każdej liczby naturalnej k ≤ 2^{n} istnieje formuła zdaniowa ϕ zawierająca n zmiennych i spełniona przez dokładnie k wartościowań.

b) (10 pkt) Dla jakich liczb k istnieje formuła ϕ zawierająca n zmiennych, w której każda ze zmiennych występuje dokładnie jeden raz i która jest spełniona przez dokładnie k wartościowań?

Zadanie 2 (15 pkt). Niech α : ℕ → {0, 1} będzie ciągiem zero-jedynkowym. Symbolem ∼_{α} oznaczamy relację w zbiorze {0, 1}^{ℕ} nieskończonych ciągów zero-jedynkowych zdefiniowaną formułą

β ∼_{α} γ ⇔ ▷∀n∈ℕ◁ α▷n◁β▷n◁ D α▷n◁γ ▷n◁.

Czy istnieje taki ciąg α, dla którego:

a) (5 pkt) relacja ∼_{α} ma przeliczalnie i nieskończenie wiele klas równoważności?

b) (5 pkt) wszystkie klasy równoważności relacji ∼_{α} są przeliczalne i nieskończone?

c) (5 pkt) istnieje przeliczalna i nieskończona klasa równoważności relacji ∼_{α}?

Zadanie 3 (12 pkt). Na zbiorze X określone są takie relacje równoważności Q i R, że 1. każda klasa równoważności relacji Q ma q elementów,

2. każda klasa relacji R ma r elementów oraz

3. istnieje klasa równoważności relacji Q, która ma dokładnie jeden element wspólny z każdą klasą równoważności relacji R. Ile elementów ma zbiór X?

Zadanie 4 (15 pkt). Niech 6 D {C, a} będzie sygnaturą zawierającą dwuargumentowy symbol funkcji C i symbol stałej a. Dla dowolnej dodatniej liczby naturalnej n niech A_{n} D {0, 1, …, n − 1}, ⊕ _{n} oznacza dodawanie modulo n, zaś a_{n} D 0. Rozważmy algebry A_{n} D ⟨A_{n}, ⊕ _{n}, a_{n}⟩. Udowodnij, że jeżeli k D l · m, to istnieje homomorfizm h algebry A_{k} na algebrę A_{l} (surjekcja) taki, że |{E \atop h^{−1}} ▷\{0\}◁| D m. Podaj przykład takich k, l i m, dla których istnieją co najmniej dwa takie homomorfizmy. Ile jest takich homomorfizmów, jeśli zamiast sygnatury 6 będziemy rozważać sygnaturę 6′ D {C, a, b} zawierajacą dwa symbole stałych a i b oraz algebry A′_{n} D ⟨A_{n}, ⊕_{n}, a_{n}, b_{n}⟩, gdzie b_{n} D 1?

Zadanie 5 (12 pkt). Pokaż, że zbior liczb wymiernych ze zwykłym porządkiem i zbiór niepustych skończonych ciągów liczb wymiernych z porządkiem leksykograficznym są izomorficzne (rozważamy porządek leksykograficzny generowany przez zwykły porządek na liczbach wymiernych). Przypominamy, że ⪯ jest porządkiem leksykograficznym generowanym przez porządek ≤, jeśli

⟨a_{0}, a_{1}, …a_{m}⟩ ⪯ ⟨b_{0}, b_{1}, …, b_{n}⟩

wtedy i tylko wtedy, gdy ⟨a_{0}, a_{1}, …a_{m}⟩ jest prefiksem ⟨b_{0}, b_{1}, …, b_{n}⟩ lub

▷∃ k◁ (k ≤ m ∧ k ≤ n ∧ a_{k} < b_{k} ∧ ▷∀ i< k◁ a_{i} D b_{i}).

Wskazówka: Skorzystaj z twierdzenia o gęstych porządkach udowodnionego na ćwiczeniach. Przytocz sformułowanie tego twierdzenia.