egzmad11

1.02.199?)

PJWSTK: Egzamin z matematyki dyskretnej

1. (5 pkt.) Czy dopełnienie różnicy symetrycznej zbiorów jest operacją łączną?

2. (5 pkt.) Rozważmy zbiór M macierzy kwadratowych n x n o elementach rzeczywistych. Określmy następującą relację na M:

(A, B) £ r 3CeM : (dci(C) # 0 A B = C~ ^XAC)

Pokaż, że r jest relacją równoważności.

3. (4 pkt.} Zakładając, że 7j(x) oznacza predykat _ux jest liczba pierwszą¹, a a c(x): ,_sx jc«*t liczbą parzysta⁵¹, wyraź w języku logiki następujące stwierdzenia:

a. Każdą liczbę większą od 2 można przedstawić, jako sumę trzech liczb pierwszych.

b. Nie istnieje liczba naturalna większa od 2, która byłaby jednocześnie pierwsza i parzy

sta.

4. (6 pkt.) Podaj przykład zbioru i relacji na nim określonej (po jednym przykładzie do każdego-z podpunktów), która jest

a. aulysymetryczna, a jednocześnie jest symetryczna.

b. przechodnia i zwrotna, ale nie jest relacją porządku.

c. spójna, a jednocześnie jest relacją równoważności.

5. (5 pkt.) Załóżmy, że węzłami grafu są pola szachownicy m x n dla pewnych n.m > .

Dwa węzły są połączone krawędzią wtedy i tylko wtedy gdy odpowiadające im pola mają wspólny bok. Okreśi zbiór wszystkich par (m. n), dla których w "takim grane istnieje ścieżka Eulera.

G. (4 pkt.) Podaj przykład warunku logicznego w C ilustrujący brak łączności koni*.inką:i w prog ramach C*.

7. (15 pkt.) Ze zbioru trzech kuł białych i jednej czarnej losujemy dwie. Przy założeniu, że wybói* każdej z czterech kul byljediiakowo prawdopodobny, określ model probabilistyczny oraz oblicz prawdopodobieństwo tego, że

S(a. wylosowane kule są różnego koloru b. druga z wylosowanych kul jest_biała

\ c. druga z wylosowanych kul jest-biała, pod warunkiem, że pierwsza jest biała.

d. druga z wylosowanych kul jest biała pod warunkiem, że pierwsza jest czarna.

e. z wylosowanych kul wylosujemy w kolejnym losowaniu kulę biała.

8. (nadobowiązkowe) Rozważmy zbiór IN. Określmy relacje równoważności o i <7 na !N\

zpy 12j(x - y),xcy 15j«'x - //}.

a. Czy relacja pCio jest relacją równoważności?

b. Czy relacja per jest relacją równoważności?

c. C/.v relacja n U s jest relacją równoważności?

d. Ih ekauentów ma zbiór żV/,_;jrj7-?

egzmad11

egzmad11

(A, B) £ r 3CeM : (dci(C) # 0 A B = C~ XAC)

zpy 12j(x - y),xcy 15j«'x - //}.

(A, B) £ r 3CeM : (dci(C) # 0 A B = C~ ^XAC)