Logika dla informatyków, Kolokwium nr 2, styczeń 2013
1/2
A) Zakres kolokwium
Zadanie 1. - przeliczalność zbiorów
Zadanie 2. - równoliczność zbiorów
Pytania pomocnicze do zadań 1-2 (patrz punkt B poniżej).
Zadanie 3. wielozbiory - działania
Zadanie 4. wielozbiory - własności działań
Zadanie 5. język formalny
Zadanie 6 - język formalny
Zadanie 7. język formalny - gramatyka
Pytanie pomocnicze do zadania 6 (patrz punkt C poniżej)
Zadanie 8. Rachunek zdań - tautologie
Zadanie 9. Rachunek zdań - tautologie
Zadanie 10. Rachunek zdań - pełność funkcjonalna zbiorów spójników
Zestaw dodatkowych spójników logicznych do zadania 10 (patrz punkt D)
B) Przyjmijmy następujące oznaczenia:
N - zbiór liczb naturalnych,
C - zbiór liczb całkowitych
E(X) - zbiór wszystkich relacji binarnych nad zbiorem X,
B(X) - zbiór wszystkich relacji równoważności nad zbiorem X,
Y*=
, gdzie
jest i-tym iloczynem kartezjańskim np.
.
B.1) Przytoczyć twierdzenia o przeliczalności podzbiorów, sum, iloczynów, itd. zbiorów
przeliczalnych.
B.2) Niech A =
df
{0, 1} i B =
df
{0, 1, 2, ..., n}. Które pary spośród zbiorów A*, B*, N* są
zbiorami równolicznymi?
B.3) Niech X={1,2} i Z={1,2,3,4}.
Czy zbiór E(X) jest równoliczny ze zbiorem B(X)?
Czy zbiór E(X)* jest równoliczny z N?
Czy zbiór (B(X)
E(X))* jest równoliczny z N?
Czy zbiór E(X)* jest równoliczny z N?
Czy zbiór
jest równoliczny z N?
B.4)
Czy zbiór
jest przeliczalny?
Czy zbiór
jest równoliczny z N?
B.5)
Czy zbiór wszystkich liczb całkowitych podzielnych jednocześnie przez 2 i 3 jest
przeliczalny?
Czy zbiór wszystkich liczb całkowitych podzielnych jednocześnie przez 2 i 3 jest
równoliczny ze zbiorem liczb naturalnych?
