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?