wieczorowe

h//ć OUJ&O OJ/E

M*0

Matematyka Dyskretna Egzamin końcowy, 1 lutego 2002 r.

Grupa A

7 zad 1.

Dany jest ciąg

a_n — 2a_n_i + 1, clq = 5.

Napisać i udowodnić przez indukcję jawny (tj.nierekurencyjny) wzór na n-ty wyraz tego ciągu.    ^x

^tzad 2.

Pokazać, że następująca formula nie jest tautologią, przez podanie interpretacji, w której staje się ona zdaniem fałszywym.

V_r(p(x) V g(x)) V_xp(x) V V_xq(x)

0^-zad 3.

Niech X = {1,2,Oznaczmy przez T zbiór wszystkich funkcji f \ X —* X.

Na zbiorze T definiujemy relację =. Dla /, g 6 J-, f = g wtedy i tylko wtedy gdy f(X) = g{X) (tj. / i g mają takie same zbiory wartości). Udowodnić, że relacja = jest relacją równoważności na zbiorze T. Ile elementów ma klasa równoważności \id\=. gdzie id jest funkcją identycznościową na zbiorze X? Odpowiedź uzasadnij.

zad 4.    17 w    bi-    ,

Na ile sposobów można rozmieścić 12 identycznych pomarańczy w 5 różnych s skrzynkach? Odpowiedź uzasadnij.

ad 5.

(a)    Oblicz prawdopodobieństwo, że losowo wybrana liczba ze zbioru {1,2,..., 1000} nie dzieli się przez 15 pod warunkiem, że nie dzieli się przez 7.

(b)    Sformułuj zasadę włączania-wyłączania.

zad 6.

(a)    Podaj definicję zbioru częściowo uporządkowanego.

(b)    Narysuj diagram Hassego dla zbioru częściowo uporządkowanego

({2,4,6,9,12,18,27,36,48,60,72},|} (gdzie symbol | oznacza relację podzielności). Znajdź elementy maksymalne i minimalne oraz elementy:    najmniejszy i

największy, o ile istnieją.    _v