Ćwiczenia 3 MAD 16 października 2001

Relacje

1. Udowodnić, że

· dla dowolnych A, B, C, A ´ (B\C) = (A ´ B)\ (A ´ C).

· jeśli zbiory A,B,C są niepuste, to
A Í B i C Í D wttw A´ C Í B´D.

· dla dowolnych A, B, C zachodzi wzór (A Å B) ´ C = (A ´ C) Å (B ´ C).

2. Niech U= {0,1,2,3} i niech r1, r2 ÍU ´ U będą relacjami takimi, że

(n,m)Î r1 wttw m-n jest liczbą parzystą
(n,m) Î r2 wttw m £ n.

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

3. Zbadać własności relacji

· x r y wttw 2|(x+y) dla x,y ÎN

· x r y wttw sgn x £ sgn y x,y Î R

· x r y wttw |x+y+1| £ 1 x,y ÎR (narysować wykres relacji)

4. Podać (wymieniając pary uporządkowane, albo definiując tabelkę relacji, albo rysując graf) przykład relacji binarnej w zbiorze X={a,b,c,d}.

· Zwrotnej

· symetrycznej

· przechodniej

5. Niech x0 będzie ustaloną liczbą rzeczywistą dodatnią. Podać wykres relacji (r1È r2) wiedząc, że

r1 = {(x,y) Î R⁺´R : y = - Öx i x £x0} r2 = {(x,y) Î R⁺´R : y = +Öx i x >x0}

6. Udowodnić, że

· jeśli r1 i r2 są relacjami zwrotnymi, to jest nią również relacja (r1 Ç r2)

· relacja r jest przechodnia wttw r o r Í r

· ( r1 È r2) ^-1 = r1^-1 È r2^-1

7. Wyznaczyć złożenie r o r, jeśli r = {(x,y) Î R ´ R : x+y £ 0}.

8. Ile różnych relacji binarnych zwrotnych można utworzyć w zbiorze n-elementowym?

9. Zakładając, że relacja jest reprezentowana przez macierz incydencji (sąsiedztwa) zaproponować algorytm badania, np.: jej zwrotności i przeciwzwrotności.