mad kol1 2009 s3

Matematyka dyskretna - materiały ćwiczeniowe PJWSTK

16. Który z poniższych ciągów funkcji jest uporządkowany rosnąco względem rzędów funkcji składowych:

-"(a) Ign², y/n, tiy/n, lgn!,

«—(b) nlgn, ny/n, 2ⁿ, 9^,

-f-{c) 2^lg", n²,n!, (n - l)"^-2?

17.    Które z poniższych oszacowań jest poprawne dla funkcji / (n) = ny/n:

-H») /(«) = n(nlgn),

— (b) /(n) = O(nlgn),

—(c) / (n) = © (n² — c), gdzie 0 < c < 1 jest pewną stałą?

18.    Rozważmy relację r = {(a, b) eNxN:a + 6 = 0 mod 2}, wtedy:

—-(a) relacja r jest zwrotna, przechodnia i spójna,

*/~(b) relacja r nie jest przeciwsymetryczna i antysymetryczna, •—(c) relacja r jest relacją równoważności w zbiorze N.

19. Niech r\ będzie relacją zwrotną i symetryczną oraz r₂ będzie relacją symetryczną i przechodnią, wtedy:

—(a) ri n r-2 jest relacją zwrotną, symetryczną i przechodnią,

-f~ib) rj U 7*2 jest relacją zwrotną, symetryczną i przechodnią,

(c) 7‘i ffi r₂ jest relacją zwrotną, symetryczną i przechodnią.

20. Załóżmy, że graf pewnej relacji równoważności r w zbiorze N składa się z 5-ciu rozłącznych podgra-fów, wtedy:

~-(a) liczba klas abstrakcji, na jakie relacja r dzieli zbór N jest nieokreślona,

*f~(b) relacja r dzieli zbiór N na co najwyżej 5 klas abstrakcji,

— (c) relacja r dzieli zbiór N na 5 klas abstrakcji, z których każda zawiera skończoną liczbę elementów.

3 Magdalena Kacprzak &: Paweł Rembelski