Logika dla informatyków

Egzamin poprawkowy

14 lutego 2003

Zadanie 1 (14 pkt). Podaj przykład przeliczalnego liniowego porządku, takiego że każdy element posiada następnik, istnieje element najmniejszy, każdy element prócz najmniejszego posiada poprzednik, ale nie izomorficznego ze zbiorem liczb naturalnych ze zwykłym porządkiem.

Zadanie 2 (15 pkt). Udowodnij, że zbiór R relacji równoważności określonych na ustalonym zbiorze X uporządkowany przez relację zawierania jest kratą. Czy zbiór C relacji częściowego porządku na zbiorze X uporządkowany przez relację zawierania jest kratą?

Zadanie 3 (14 pkt). Wykaż przez indukcję, że dla każdej formuły zdaniowej ϕ zbudowanej ze zmiennych oraz spójników ∧ i ∨ istnieje formuła ψ postaci ψ_{1}∨ψ_{2}∨…∨ψ_{n}, taka że dla każdego i ≤ n formuła ψ_{i} jest koniunkcją zmiennych oraz ▷ϕ ⇔ ψ◁ jest tautologią.

Zadanie 4 (14 pkt). Udowodnij, że dla dowolnej rodziny zbiorów {A_{t,s}}_{t∈T ,s∈S} zachodzi zawieranie

⋃_{t∈T} ⋂_{s∈S} A_{t,s} ⊆ ⋂_{s∈S} ⋃_{t∈T}A_{t,s}.

Czy zachodzi inkluzja odwrotna?

Zadanie 5 (15 pkt). Wykaż, że zbiory ℝ^{ℕ} i ℝ są równoliczne (ℝ oznacza zbiór liczb rzeczywistych, a ℕ zbiór liczb naturalnych).

Zadanie 6 (15 pkt). Niech f : ℝ → ℝ. Mówimy, że x ∈ ℝ jest lokalnym maksimum funkcji f, jeżeli istnieje taka dodatnia liczba rzeczywista r, że dla każdego y ∈ ℝ jest spełniony warunek

▷x − r < y < x C r ∧ x D̸ y◁ ⇒ f ▷x◁ > f ▷y◁

Udowodnij, że dla każdej funkcji f : ℝ → ℝ zbiór jej lokalnych maksimów jest przeliczalny.

Ciąg dalszy na odwrocie → Zadanie 7 (13 pkt). Funkcje f : ℕ → {0, 1} oraz g : ℕ → {0, 1} są równe prawie wszędzie, jeśli zbiór

{n ∈ ℕ | f ▷n◁ D̸ g▷n◁}

jest skończony. Zapis f ≈ g oznacza, że funkcje f i g są równe prawie wszędzie. Funkcja f : ℕ → {0, 1} majoryzuje funkcję g : ℕ → {0, 1}, jeśli zbiór

{n ∈ ℕ | f ▷n◁ < g▷n◁}

jest skończony. Zapis g ⪯ f oznacza, że funkcja f majoryzuje funkcję g. Na zbiorze F D {[f]_{≈} | f : ℕ → {0, 1}} klas abstrakcji relacji ≈ wprowadzamy relację ⪯ przyjmując, że

[f]_{≈} ⪯ [g]_{≈} ⇔ f ⪯ g

Niech {A_{i} | i ∈ ℕ} będzie podziałem zbioru ℕ na zbiory nieskończone. Definiujemy ciąg funkcji {f_{j} | j ∈ ℕ} kładąc

f_{j} ▷n◁ D \{ \begin{matrix}1, & jeżeli n ∈ ⋃ _{iD1}^{j} A_{i} \\ 0, & w przeciwnym przypadku \end{matrix}

Niech g : ℕ → {0, 1}. Napisz, nie używając symbolu ≈, symboli oznaczających klasy abstrakcji ani symbolu relacji majoryzowania, co to znaczy, że [g]_{≈} jest ograniczeniem górnym zbioru {[f_{j}]_{≈} | j ∈ ℕ}. Napisz, co to znaczy, że [g]_{≈} nie jest kresem górnym tego zbioru. Możesz używać kwantyfikatorów, spójników logicznych, nawiasów, formuł |A| < ∞ i |A| D ∞ oznaczających, że zbiór A jest, odpowiednio, skończony bądź nieskończony oraz zapisu {n ∈ ℕ | 8}, gdzie 8 oznacza dowolną formułę utworzoną z symboli g▷n◁, f_{j} ▷n◁, ≤, D oraz <.