Logika dla informatyków, Kolokwium nr 2, styczeń 2013
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?
1/2
Logika dla informatyków, Kolokwium nr 2, styczeń 2013
Czy zbiór wszystkich liczb całkowitych podzielnych jednocześnie przez 2 i 3 jest
równoliczny ze zbiorem wszystkich liczb podzielnych jednocześnie przez 2, 3 i 4?
C) Niech alfabet Al języka formalnego F będzie następującym sześcioelementowym
zbiorem Al = {p, óð,ð ð ð~, Éð,ð ð(, )}. Przyjmijmy poniższe reguÅ‚y syntaktyczne definiujÄ…ce jÄ™zyk
formalny F:
·ð Każdy symbol p, póð, póðóð, póðóðóð, póðóðóðóð, póðóðóðóðóð, .... jest poprawnym sÅ‚owem jÄ™zyka F.
·ð Jeżeli A jest poprawnym sÅ‚owem jÄ™zyka F, to ciÄ…g znaków ~(A) jest poprawnym
słowem języka F.
·ð Jeżeli A i B sÄ… poprawnymi sÅ‚owami jÄ™zyka F, to ciÄ…gi znaków (A), (B) i (AÉðB) sÄ…
poprawnymi słowami języka F.
C.1) Podać przykłady ciągów ze zbioru F* nie będących słowami języka F.
C.2) Podać przykłady ciągów ze zbioru F* będących słowami języka F.
D)
a b
aµðb a Å»ð b
0 0 1 1
0 1 1 0
1 0 1 0
1 1 0 0
R.K.
2/2