MAD s2 09 zaoczne kacprzak

Matematyka Dyskretną 1 - matęriały ćwiczeniowe Studia zaoczne PJWSTK O

SPRAWDZIAN II, grupa A

1.    Dana jest funkęja / ; R —♦ R, / (») = o;³ — 3. Kolejno:

(a)    określ czy jest ona iniekcją, suriekcją i bijekcją,

(b)    wyznacz f(X), gdzie X — R⁺,

(c)    wyznacz f~^l (Y), gdzie Y — [—2,2],

(d)    wyznacz funkcję odwrotną f~^x do funkcji /.

2.    Rozważmy następujące funkcje zmiennej naturalnej n:

•    / («) = ny/ń,

•    g(n) = nlgn,

•    h (n) == n².

Które z następujących ograniczeń jest prawdziwe:

(a)    / (n) = O {g (n)),

(b)    g(n) = n(h(n)),

(c)    Mn) = ©(/(») + $(»)),

(d)    (hoh)(n) = 0(f{n)g(n)).

3. Niech uniwersum relacji r będzie zbiór U = P({a,6,c,d}). Powiemy, że zbiór X jest w relacji r ze zbiorem Y' wtedy i tylko wtedy, gdy Alg(X,Y) = X. Sprawdź, czy relacja r jest relacją porządku w zbiorze U, gdy

Alg(X,Y)={

while |V{ > |X| do

if \Y] mod 2—0 then Y:=Y\fel. alfabetycznie najmniejszy to zbiorze Y); else Y:—Y\{el. alfabetycznie największy w zbiorze Y}; fi od

if X = Y then return X; else return {a, b, c, d) \X; fi

b

Jeżeli tak, to:

(a)    narysuj wybrany fragment diagramu Hassego relacji r (dla co najmniej 10-ciu elementów rozważanego uniwersum),

(b)    wyznacz elementy wyróżnione względem relacji r,

(c)    podaj przykład 2-elementowego zbioru A C U, takiego, że A posiada kres górny i kres dolny w zbiorze U względem relacji r,

(d)    podaj przykład 3-elementowego zbioru B ę. U, takiego, że B nie posiada kresu górnego w zbiorze U względem relacji r.

1 Magdalena Kacprzak & Paweł Rembelski