| « poprzedni punkt | następny punkt » |
W tej części będziemy rozważali relacje binarne określone w zbiorze X. Oznacza to, że zarówno dziedzina jak i przeciwdziedzina relacji są podzbiorami tego samego zbioru X.
Definicja 2.4
Relację binarną r Í X´ X nazywamy zwrotną wttw dla każdego x Î X, para (x, x) należy do r.
Relację binarną r Í X´ X nazywamy przeciwzwrotną wttw dla każdego x Î X, para (x, x) nie należy do r .
r jest zwrotna wttw {(x, x) : x Î X }Í r
r jest przeciwzwrotna wttw {(x, x) : x Î X }Ç r = Æ
Najbardziej charakterystycznym przykładem relacji zwrotnej jest relacja = w dowolnym zbiorze X. Składa się ona jedynie z par (x, x) dla wszystkich x Î X. Przykładem relacji przeciwzwrotnej jest relacja < w zbiorze liczb rzeczywistych: oczywiście dla żadnej liczby rzeczywistej nie zachodzi x <x, czyli żadna para (x, x) do tej relacji nie należy.
Zastanówmy się jak może wyglądać macierz relacji zwrotnej. Ponieważ każdy x jest ze sobą w relacji, zatem wszystkie pozycje na głównej przekątnej macierzy muszą być zaznaczone. Poza tym mogą być zaznaczone jeszcze inne pozycje, nie wpłynie to na fakt, że tak określona relacja jest zwrotna. Równie prosto można rozpoznać relację zwrotną (określoną w skończonym zbiorze) patrząc na graf tej relacji: relacja jest zwrotna, jeśli przy każdym węźle jedna z krawędzi wychodzących z tego węzła jest skierowana do tego właśnie węzła (o takiej krawędzi mówimy, że jest to pętla).
W przypadku relacji przeciwzwrotnej, żadna z pozycji na głównej przekątnej macierzy relacji nie może być zaznaczona i żaden z węzłów grafu relacji nie ma pętli.
Przykład 2.6
Rozważmy relację podzielności w zbiorze {1,2,3,4,5,6,7,8,9}. Jest to relacja zwrotna, bo każda liczba jest swoim własnym dzielnikiem. Macierz tej relacji oraz jej graf przedstawiono na rysunku Rys.2.6.
Rys. 2.6 Relacja podzielności w zbiorze {1,2,3,4,5,6,7,8,9}.
Zauważmy, że relacja binarna może nie być ani zwrotna ani przeciwzwrotna: te pojęcia nie są przeciwstawne. Na rysunku 2.7 przedstawiliśmy przykład takiej relacji:
nie jest ona zwrotna, bo np. para (6,6) do niej nie należy,
nie jest ona przeciwzwrotna, bo np. para (1,1) należy do tej relacji.
Rys. 2.7 Przykład relacji, która nie jest zwrotna i nie jest preciwzwrotna.
Pytanie 3: Dana jest tablica kwadratowa T (macierz), której wiersze i kolumny są ponumerowane liczbami naturalnymi od 0 do 9. Elementami tej tablicy są jedynie zera lub jedynki. Jaką własność relacji reprezentowanej przez macierz T, sprawdza następujący algorytm:
{i:=0; wynik := true;
while (i<10 and wynik) do
if T[i,i] = 0 then wynik := false; fi;
i := i+1;
od }
Definicja 2.5
Relację binarną r Í X´ X nazywamy symetryczną wttw dla dowolnych x, y Î X, jeśli para (x, y) należy do r , to para (y,x) też należy do r. Relację r nazwiemy przeciwsymetryczną (inaczej asymetryczną) wttw dla dowolnych x, yÎ X z tego, że (x, y) Î r wynika, że (y, x) Ï r.
Przykładem relacji symetrycznej jest relacja || równoległości prostych na płaszczyźnie:
l1 || l2 wttw prosta l1 jest równoległa do l2
Przykładem relacji przeciwsymetrycznej jest relacja < w zbiorze liczb rzeczywistych: jeśli x < y, to nie jest prawdą by y < x.
Zarówno relację symetryczną jak i przeciwsymetryczną bardzo łatwo rozpoznać, jeśli mamy jej macierz lub graf relacji. Macierz relacji symetrycznej jest symetryczna względem głównej przekątnej, por. Rys.2.8a. Natomiast, graf relacji symetrycznej ma wszystkie krawędzie w obu kierunkach, por. Rys.2.8b.
Rys. 2.8 (a) Macierz relacji symetrycznej i (b) jej graf.
Zauważmy, że relacja może nie być ani symetryczna ani przeciwsymetryczna, jak to ma miejsce w przypadku relacji przedstawionej na rysunku 2.7. Nie jest to relacja symetryczna, bp para (5,4) należy do relacji a para (4,5) nie należy. Nie jest to relacja przeciwsymetryczna, bo para (4,3) należy do relacji i para (3,4) też należy do relacji.
Definicja 2.6
Relację binarną rÍ X´ X nazywamy antysymetryczną wttw dla dowolnych x, y Î X, jeśli obie pary (x, y) i (y, x) należą do r, to x = y.
Przykładem relacji antysymetrycznej jest relacja £ w zbiorze liczb rzeczywistych i relacja podzielności w zbiorze liczb naturalnych.
Definicja 2.7
Relację binarną r Í X´ X nazywamy przechodnią wttw dla dowolnych x, y, z Î X, jeśli (x,y) Î r i (y,z) Î r, to (x, z) Î r.
Przykładem relacji przechodniej jest relacja < lub relacja £ w zbiorze liczb rzeczywistych. Wiele innych przykładów poznamy w dalszych częściach wykładu.
Pytanie 4: Czy każda relacja przeciwzwrotna i przechodnia jest przeciwsymetryczna?
Zobacz odpowiedźPrzykład 2.7
Niech p będzie ustaloną liczbą całkowitą większą od 1. Zdefiniujemy relację º przystawania liczb modulo p następująco: dla dowolnych x, y całkowitych,
x º y (mod p) wttw (x - y) jest wielokrotnością p
Tak określona relacja
jest zwrotna, bo (x-x)=0 = 0*p,
jest symetryczna, bo jeśli ( x - y)= k* p dla pewnego k całkowitego, to (y - x)= (-k)*p,
jest przechodnia, bo jeśli x º y (mod p) i y º z (mod p), to (x - y) =k* p i (y-z) = k'* p, a stąd (x - z) = (k + k')*p, czyli x º z (mod p).
Pytanie 5: Czy relacja r zdefiniowana w zbiorze liczb rzeczywistych warunkiem x r y wttw |x+y+1|=1 jest przechodnia?
Zobacz odpowiedź| « poprzedni punkt | następny punkt » |