30 (18)

i

Matematyka dyskretna - ćwiczenia 1 Relacje

Zad. 1. Niech X= {1,2}, Y = {a,b,c}. Z jakich elementów (par uporządkowanych ) składa się produkt kartezjański X x Y.

Zad. 2. Niech A={1,2,3,4} i B = {5,6,7,8,9}. Wypisz pary będące w relacji R, jeśli (a,b)eR wtedy i tylko wtedy, gdy a jest dzielnikiem b. Przedstaw relację w postaci tabelki (macierzy) oraz grafu.

/\o • 7

Zad.3. Przedstaw na różne sposoby relację podzielności w zbiorze

{1,2,3,4,5,6,7,8,9}. Czy ta relacja jest zwrotna? (a | b oznacza, że a dzieli b).

Zad. 4. Podaj przykłady relacji zwrotnej, przeciwzwrotnej, symetrycznej, asymetrycznej (przeciwsymetrycznej), anty symetrycznej, przechodniej.

Zad. 5. Niech A= {0,1,2,3} i niech R, (i = l,2,3,4,5) ę A x A będą relacjami takimi, że

j    % Ą ^    ^    1

v a) (m,n)s Ri, jeśli m-n jest liczbą parzystą    ź-*

b)    (m,n)e R₂, jeśli m < n

c)    (m,n)s R_3/ jeśli m + n =3

d)    (m,n)s R4, jeśli m + n < 4,

e)    (m,n) e R_Sł jeśli max{m, n} =3.

Zapisz każdą z relacji jako: zbiór par uporządkowanych, w postaci tabelki (macierzy) i w poąjiąci grafu. Dla każdej relacji określ jej własności (czy jest zwrotna, czy symetrycznaTtdy).    U,;*

n- - Zad. 6. Zbadaj własności relacji

*

a) x R_l y , jeśli 2|x+y dla x,y s N

b) xR₂y , jeśli 3|x-y dla x,y s Z.

Zad. 7. Narysuj wykres poniższych relacji Se R².

a)    dla każdego x, y eR, xSy gdy |x+y|< 1.

b)    dla każdego x, y e R, xSy gdy x=2 lub y=3.

c)    dla każdego x, y sR, xSy gdy x²+y²<4.

Zad. 8. Ocen, które z własności ma relacja R na zbiorze wszystkich ludzi, jeżeli (x, y) e R <=>

a)    x jest wyższy od y,

b)    x jes.t co najmniej tak wysoki jak y,

c)    x i y urodzili się, tego samego dnia tygodnia,

d)    x i y maję, wspólnych oboje rodziców,

e)    x jest dzieckiem y,

f)    x i y maja, wspólnego dziadka lub babcię.

Zad.9. Na zbiorze liczb naturalnych definiujemy relację R w ten sposób, że n R m oznacza, że n i m dają tę samą resztę z dzielenia przez 3. Uzasadnij, że R jest równoważnością.