MAD s2 zaoczne kacprzak

Mattmatylm Dyskretna 1 - materiały ćwicztniow* Studia zaoczne PJWSTK ©

SPRAWDZIAN II, grupa A

|| Dana jest funkcja / : R —» R, / (x) = a'³ - 3. Kolejno:

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

(b)    wyznacz / (.Jf), gdzie X = R⁺,

(c)    wyznacz f¹ (Y), gdzie Y = [—2,2],

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

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

•    / (ⁿ) ⁼ n.y/ń,

•    g(n) = nlgn,

•    h(n)== n².

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

(a)    f(n) — O (g (n)),

(b)    g(n) = «(/»(«)),

(c)    h(n) = B (/ (n) 4- g (»)),

(d)    (/toh)(n)=0(/(n)<7(n)).

3. Niech uniwersum relacji r będzie zbiór U = P({a,b, c,d}). Powiemy, że zbiór X jest w relacji r ze zbiorem >' 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 \Y\ > \X\ do

if \Y\ mod 2-0 then Y:=Y\{el. alfabetycznie najmniejszy tu 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-du 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 C U, takiego, że B nie posiada kresu górnego w zbiorze U względem relacji r.