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 = 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?