Wrocław, 7 listopada 2012

Wydział Informatyki i Zarządzania, rok I
Logika dla informatyków

Zadania – lista 5

1. Niech X, Y, Z będą wielozbiorami. Pokazać, że jeżeli X



Y oraz Y



Z, to X



Z.

2. Niech W = <U, F> będzie wielozbiorem nad zbiorem U, gdzie funkcja liczności F jest

zdefiniowana następująco: F(x) = n dla każdego x



U. Jeżeli A jest podwielozbiorem wielozbioru

W, to przez A’ oznaczamy operację dopełnienia wielozbioru A, którą definiujemy jako: A



=

def

W \

A. Sprawdzić, czy zachodzą prawa de Morgana:

(A



B)



= A





B



(A



B)



= A





B



3. Zaproponować sposoby reprezentacji grafów w pamięci komputera. Rozważyć oddzielnie grafy

skierowane i nieskierowane. Oszacować złożoność pamięciową proponowanych reprezentacji.

4. Pokazać równoliczność zbioru liczb naturalnych i zbioru liczb pierwszych.

5. Niech A =

df

{0, 1}, B =

df

{0, 1, 2, ..., n} oraz C = Nat. Które pary spośród zbiorów A

*

, B

*

, C

*

są

zbiorami równolicznymi?

Uwaga:

Jeśli X jest zbiorem, to X

*

oznacza zbiór, którego elementami są wszystkie, skończonej

długości ciągi złożone z elementów zbioru X.

6. Pokazać, że zbiór potęgowy zbioru A jest równoliczny ze zbiorem funkcji określonych na A i o

wartościach w zbiorze {0, 1}, czyli ze zbiorem {f | f : A



{0, 1}}.

7. Ile jest rosnących ciągów liczb wymiernych zbieżnych do 1?

8. Ile jest relacji równoważności określonych na zbiorze liczb naturalnych takich, że wszystkie ich

klasy abstrakcji są skończone?

9. Udowodnić, że każdy zbiór rozłącznych odcinków na prostej jest przeliczalny.

10. Udowodnić, że jeżeli A nie jest zbiorem przeliczalnym i B jest zbiorem przeliczalnym, to A/B nie

jest zbiorem przeliczalnym.

11. Udowodnić, że produkt kartezjański dwóch zbiorów przeliczalnych jest zbiorem przeliczalnym.

12. Udowodnić, że zbiór liczb wymiernych jest przeliczalny.

13. Czy zbiór wszystkich funkcji o sygnaturze f : Nat



Nat jest przeliczalny?

14. Czy przeliczalny jest zbiór wszystkich programów, które można napisać w danym języku

programowania?