relacje.doc

Rozdział VI

RELACJE.

WSTĘP.

Obecny rozdział poświęcony będzie relacjom. Z relacjami zetknęliśmy się już w części poświęconej rachunkowi predykatów. Obecnie zostaną one omówione o wiele dokładniej. Będzie to rozdział najbardziej teoretyczny ze wszystkich; zadania będą stanowiły niewielki procent całości. Wynika to z faktu, iż związane z relacjami zadania polegają zwykle na wykrywaniu pewnych własności podanych relacji. Aby móc je rozwiązać, trzeba przede wszystkim posiadać teoretyczną wiedzę o tych własnościach. Gdy wiedza ta zostanie zdobyta, rozwiązanie takiego zadania jest zwykle niemal oczywiste.

6.1. CO TO JEST RELACJA.

6.1.1. ŁYK TEORII.

Relacja to pewien związek łączący obiekty. Mówiąc „relacja” mamy zwykle na myśli tak zwaną relację dwuczłonową, czyli związek łączący dwa obiekty. Taką relacją jest na przykład bycie starszym – pewna osoba x jest starsza od innej osoby y; inne przykłady to bycie żoną – osoba x jest żoną osoby y, lubienie – osoba x lubi osobą y itp.

Dla porządku dodajmy, że relacje mogą mieć dowolną ilość członów. Relacje jednoczłonowe (odnoszące się do jednego obiektu) nazywamy własnościami – tego typu relacje, to na przykład bycie wysokim, bycie w wieku 25 lat, bycie kobietą itp. Przykładem własności trójczłonowej jest słuchanie rozmowy – osoba x słucha rozmowy osoby y z osobą z. Relacjami innymi niż dwuczłonowe nie będziemy się jednak zajmować; mówiąc relacja – bez dodania do niej żadnego przymiotnika, będziemy mieli na myśli zawsze relację dwuczłonową.

Symbolicznie relacje możemy oznaczać na różne sposoby. Zwykle fakt, ze dwa obiekty x i y są ze sobą w relacji R zapisujemy R(x,y) lub xRy. Spotyka się też zapis (x,y) Î R (para x, y należy do relacji R).

Do lepszego zrozumienia relacji potrzebne nam będzie pojęcie tak zwanej pary uporządkowanej oraz iloczynu kartezjańskiego dwóch zbiorów.

Para uporządkowana.

Jak pamiętamy z poprzedniego rozdziału, w zwykłym zbiorze nie jest istotna kolejność elementów, w jakiej je wypiszemy. I tak na przykład zbiór X = {a, b} jest równy zbiorowi Y = {b, a}. Inaczej ma się rzecz w przypadku tak zwanych par uporządkowanych, w skrócie zwanych po prostu parami. Elementy par wypisujemy w nawiasach skośnych, np. áa, bñ lub, czasem, zwykłych – (a, b). W przypadku pary kolejność elementów ma kluczowe znaczenie. I tak para áa, bñ nie jest równa parze áb, añ; są to zupełnie różne obiekty.

Iloczyn kartezjański.

Iloczyn kartezjański to pewne specyficzne działanie na zbiorach, o którym jednak nie było mowy w rozdziale poświęconym zbiorom. Iloczyn kartezjański symbolicznie oznaczamy znakiem ´.  Zbiór, który powstaje w wyniku wykonania takiego działania, nie jest zwykłym zbiorem, ale zbiorem, którego elementy stanowią pary. Dokładniej, iloczyn kartezjański zbiorów X i Y (czyli X ´ Y) to zbiór wszystkich par, takich, w których na pierwszym miejscu jest element zbioru X, a na drugim element zbioru Y. Przykładowo, jeśli X = {a, b, c}, natomiast Y = {1, 2}, to iloczyn kartezjański X ´ Y = {áa, 1ñ, áa, 2 ñ, áb, 1ñ, áb, 2ñ, ác, 1ñ, ác, 2ñ}.

Kwadrat kartezjański jakiegoś zbioru X, oznaczany symbolicznie X2, to nic innego, jak iloczyn kartezjański zbioru X z sobą samym, czyli X ´ X. Jeśli zatem X = {a, b, c}, to X2 = {áa, añ, áa, b ñ, áa, cñ, áb, añ, áb, bñ, áb, cñ, ác, añ, ác, bñ, ác, cñ}

Pojęcia pary uporządkowanej oraz iloczynu kartezjańskiego łączy się z teorią relacji w ten sposób, że każdą relację możemy przedstawić (przynajmniej teoretycznie) jako zbiór par. Jeśli relacja określona jest w pewnym uniwersum, to możemy powiedzieć, że relacja ta zawiera się w kwadracie kartezjańskim tego uniwersum (stanowi podzbiór kwadratu kartezjańskiego tego uniwersum). Mówiąc po prostu, relacja to niektóre (a czasem wszystkie) pary, jakie można utworzyć z elementów uniwersum.

Najlepiej wyjaśnić to na przykładzie. Weźmy uniwersum złożone z czterech liczb U = {1, 2, 3, 4} i określmy w tym zbiorze relację większości. Bardziej formalnie relację tę możemy zapisać tak: xRy º x > y. Relacja nasza zawiera się w kwadracie kartezjańskim uniwersum (symbolicznie R Í U2), ponieważ należą do niej niektóre z par liczb, które to pary możemy utworzyć z uniwersum. Relację naszą możemy przedstawić jako następujący zbiór par, w których pierwsza liczba jest większa od drugiej: R = {á2,1ñ, á3,1ñ, á3,2ñ, á4,1ñ, á4,2ñ, á4,3ñ}.

Gdybyśmy w uniwersum złożonym z ludzi chcieli utworzyć relację bycia żoną, to relację tę moglibyśmy przedstawić jako zbiór takich par, gdzie pierwsza osoba jest żoną drugiej osoby: R = {áMaria Kowalska, Jan Kowalskiñ, áDanuta Wałęsa, Lech Wałęsañ, áHilary Clinton, Bill Clintonñ... itd. }. Oczywiście wypisanie wszystkich par należących do naszej relacji nie jest praktycznie możliwe, jednak nie ulega wątpliwości, że jest to podzbiór kwadratu kartezjańskiego zbioru ludzi, czyli R Í U2.

6.2. DZIEDZINY I POLE RELACJI.

6.2.1. ŁYK TEORII.

W każdej relacji możemy określić tak zwaną dziedzinę lewostronną, nazywaną czasem po prostu dziedziną, dziedzinę prawostronną, nazywaną również przeciwdziedziną oraz pole. Dziedzinę lewostronną relacji R oznaczamy symbolicznie DL(R), dziedzinę prawostronną – DP(R), natomiast pole – P(R).

Dziedzina lewostronna relacji R, to zbiór takich przedmiotów, które pozostają w R do jakiegoś (przynajmniej jednego) przedmiotu. Symbolicznie możemy to zapisać: DL(R) = {x: $y (xRy)} (dziedzina lewostronna relacji R to zbiór takich x, w stosunku do których istnieje jakiś y, taki że x jest w relacji R do tego y). W praktyce możemy sobie bardzo łatwo uzmysłowić, co jest dziedziną danej relacji, wypisując (lub wyobrażając sobie) pary tworzące tę relację. Dziedzinę lewostronną stanowić będzie zawsze zbiór tych obiektów, które przynajmniej raz znalazły się na pierwszym miejscu w jakiejś parze. Gdy weźmiemy, wspominaną wcześniej relację większości określoną w zbiorze U = {1, 2, 3, 4}, to po przedstawieniu tej relacji jako zbioru par: R = {á2,1ñ, á3,1ñ, á3,2ñ, á4,1ñ, á4,2ñ, á4,3ñ}, łatwo zauważymy, że DL(R) = {2, 3, 4}. W przypadku relacji bycia żoną dziedzinę lewostronną stanowić będzie zbiór kobiet zamężnych.

Dziedzina prawostronna (przeciwdziedzina) relacji R to, jak łatwo się domyślić, zbiór tych przedmiotów, do których jakiś przedmiot pozostaje w R. Symbolicznie: DP(R) = {y: $x (xRy)}. W przypadku naszej relacji większości DP(R) = {1, 2, 3}, natomiast przeciwdziedzinę relacji bycia żoną stanowić będzie (jeśli ograniczymy się do małżeństw heteroseksualnych) zbiór żonatych mężczyzn.

Pole relacji to po prostu suma dziedziny lewej i prawej. Symbolicznie P(R) = DP(R) È DL(R). W naszej relacji większości P(R) = {1, 2, 3, 4}. W tym przypadku pole pokryło się z uniwersum, jednak nie jest to wcale konieczne. Widać to na przykładzie relacji bycia żoną, gdzie pole to zbiór ludzi pozostających w związkach małżeńskich (będących żoną lub mających żonę), a więc nie całe uniwersum.

Uwaga na błędy!

Za błąd może zostać uznane powiedzenie, że polem relacji bycia żoną jest zbiór małżeństw. Zbiór małżeństw to bowiem zbiór, którego elementami są małżeństwa, a nie pojedyncze osoby (ma on w przybliżeniu dwa razy mniej elementów niż zbiór osób pozostających w związkach małżeńskich). Natomiast pole relacji bycia żoną musi być zbiorem złożonym z osób.

6.2.2. PRAKTYKA: OKREŚLANIE DZIEDZIN I POLA RELACJI.

Zadania związane z dziedzinami i polem relacji polegają na określeniu tych własności dla zadanej relacji. Rozwiązywanie takich przykładów nie jest trudne, jeśli tylko pamiętamy, że każdą relację możemy, przynajmniej teoretycznie przedstawić jako zbiór par. Dziedzina lewostronna będzie każdorazowo zbiorem tych elementów, które przynajmniej raz znalazły się w naszych parach na pierwszym miejscu, natomiast dziedzina prawostronna, zbiorem elementów, które przynajmniej raz wystąpiły na drugim miejscu. Po określeniu dziedziny lewej i prawej, wyznaczenie pola jest już banalnie proste.

Przykład:

Określimy dziedzinę, przeciwdziedzinę i pole relacji bycia matką (xRy º x jest matką y) określonej w zbiorze wszystkich ludzi (żyjących kiedykolwiek, a nie tylko aktualnie).

Gdybyśmy chcieli przedstawić naszą relację w postaci zbioru par, to na pierwszym miejscu byłaby każdorazowo kobieta posiadająca przynajmniej jedno dziecko, natomiast na drugim osoba będąca dzieckiem tej kobiety. Oczywiste więc jest, że dziedzinę lewostronną naszej relacji stanowić będzie zbiór kobiet mających dzieci. Dziedzina prawa to zbiór osób, które mają matkę. Ponieważ nasze uniwersum stanowi zbiór wszystkich ludzi kiedykolwiek żyjących, to o każdym człowieku można powiedzieć, że ma on (aktualnie lub kiedyś żyjącą) matkę; każdy więc znajdzie się jako element jakiejś pary z prawej strony. A zatem przeciwdziedzina naszej relacji to zbiór wszystkich ludzi. Skoro jedna z dziedzin stanowi już całe uniwersum, to oczywiste jest, że również pole naszej relacji będzie równe uniwersum, czyli zbiorowi wszystkich ludzi.

▲

Przykład:

Określimy dziedziny i pole określonej w zbiorze liczb naturalnych relacji bycia dwukrotnością (xRy º x jest dwukrotnością y).

Do naszej relacji należeć będą takie pary złożone z liczb naturalnych, gdzie pierwsza liczba będzie dwukrotnością drugiej, a zatem R = {á2, 1ñ, á4, 2ñ, á6, 3ñ, á8, 4ñ...}. Po wypisaniu kilku przykładowych par, widać jasno, że dziedzina lewa relacji, to zbiór liczb parzystych, natomiast dziedzina prawa (i jednocześnie pole) to zbiór wszystkich liczb naturalnych, czyli uniwersum.

▲

Przykład:

Określimy dziedziny i pole określonej w zbiorze wszystkich ludzi relacji bycia przeciwnej płci (xRy º x jest przeciwnej płci niż y).

Gdybyśmy chcieli wypisać niektóre z par należących do naszej relacji otrzymalibyśmy R = áJan, Mariañ, áMaria, Mieczysławñ, áKarolina, Zenonñ, áZenon, Karolinañ, áZenon, Mariañ...}

Widać wyraźnie, że każdy człowiek znajdzie się (wielokrotnie) zarówno z lewej strony jakiejś pary, jak i z prawej strony; do każdego można bowiem dobrać kogoś przeciwnej płci. A zatem w tym przypadku dziedzina prawa, równa się dziedzinie lewej, równa się polu relacji i stanowi całe uniwersum, czyli zbiór wszystkich ludzi.

Uwaga na błędy!

W przypadku powyższej relacji częstymi odpowiedziami na pytanie o którąś z dziedzin są dość dziwacznie brzmiące stwierdzenia na przykład: „ludzie przeciwnej płci”, „ludzie określonej płci”, czy też „ludzie jednej płci”. Nie są to jednak dobre odpowiedzi – cóż to bowiem są na przykład „ludzie przeciwnej płci”, jaki dokładnie jest to zbiór?

▲

Przykład:

Określimy dziedziny i pole określonej w zbiorze wszystkich ludzi relacji bycia w tym samym wieku (xRy º x jest w tym samym wieku co y).

Gdybyśmy wypisali pary należące do powyższej relacji, łatwo zauważylibyśmy, że do człowieka mającego np. 20 lat łatwo dobrać kogoś będącego w tym samym wieku; podobnie w stosunku do kogoś mającego np. 15 lat, 23 lata, 35 lat, 78 lat itd. Wątpliwości może budzić fakt, czy jesteśmy w stanie stworzyć parę z kimś mającym przykładowo 108 lat, zakładając że jest to jedyny człowiek na świecie w tym wieku. Otóż zawsze możemy to uczynić, tworząc parę złożoną z tego człowieka występującego zarówno na pierwszym miejscu, jak i na drugim; w przypadku tej relacji bowiem każdy, oprócz możliwości bycia w niej w stosunku do innych osób, pozostaje w niej również do samego siebie. Każdy jest bowiem w tym samym wieku, w którym jest on sam. Każdy więc, przynajmniej w tym jednym przypadku, wystąpi zarówno na pierwszym, jak i na drugim miejscu w pewnej parze.

Podobnie jak w poprzednim przykładzie, dziedzina lewa naszej relacji równa się dziedzinie prawej, równa się polu i stanowi całe uniwersum, czyli zbiór wszystkich ludzi.

▲

6.3. WŁASNOŚCI FORMALNE RELACJI.

6.3.1. ŁYK TEORII.

Relacje możemy charakteryzować pod względem pewnych własności. Obecnie omówimy najważniejsze z tych własności, grupując je w związku z istotnymi dla nich pojęciami.

Uwaga na marginesie.

Omawiane własności relacji dotyczą zawsze jakiegoś konkretnego uniwersum. Relacja posiadająca daną własność w jednym uniwersum, może nie posiadać jej w innym. Dlatego, ściśle rzecz biorąc, w poniższych wzorach wyrażenia "x (dla każdego x) powinny przybierać formę  "x Î U (dla każdego x należącego do danego uniwersum); podobnie $x (istnieje takie x) – $x Î U (istnieje takie x należące do U). Aby zbytnio wzorów nie komplikować, nie będziemy tak jednak pisać, domyślnie przyjmując, że każdorazowo chodzi nam jedynie o elementy z danego uniwersum.

Zwrotność.

Mówimy, że relacja jest zwrotna, gdy każdy element uniwersum jest w tej relacji do siebie samego. Symbolicznie:

R jest zwrotna º "x (xRx)

Przykładem relacji zwrotnej jest bycie w takim samym wieku (w zbiorze ludzi) lub bycie sobie równą (w zbiorze liczb). Każdy człowiek jest bowiem w takim samym wieku w stosunku do siebie samego, a każda liczba jest równa sobie samej.

Relacja jest przeciwzwrotna, gdy żaden element uniwersum nie jest w relacji do siebie samego. Symbolicznie:

R jest przeciwzwrotna º "x (~ (xRx))

Przeciwzwrotna jest przykładowo relacja bycia matką w zbiorze ludzi lub relacja mniejszości w zbiorze liczb.

Relacja może być ani zwrotna, ani przeciwzwrotna. Oznacza to, że są w uniwersum elementy będące w relacji do siebie samego, ale są też i takie, które do siebie samego w niej nie są. Relację taką nazywamy czasem niezwrotną. Symbolicznie:

R nie jest zwrotna ani przeciwzwrotna º $x (xRx) Ù $x ~ (xRx)

Przykładem takiej relacji może być relacja kochania – są ludzie, którzy kochają samych siebie, a są też i tacy, którzy siebie nie kochają.

Symetria.

Mówimy, że relacja jest symetryczna, gdy jest tak, że jeśli relacja zachodzi pomiędzy dwoma elementami w jedną stronę, to zachodzi i w drugą (jeśli zachodzi pomiędzy x i y, to zachodzi też pomiędzy y i x). Symbolicznie:

R jest symetryczna º "x"y (xRy ® yRx)

Symetryczną jest na przykład relacja bycia tej samej płci – jeśli osoba x jest tej samej płci, co osoba y, to również osoba y jest na pewno tej samej płci co osoba x.

Relacja jest asymetryczna (antysymetryczna, przeciwsymetryczna), gdy jest tak, że jeśli zachodzi w jedną stronę, to nie zachodzi w drugą. Symbolicznie:

R jest asymetryczna º "x"y [xRy ® ~ (yRx)]

Asymetryczna jest na przykład relacja bycia ojcem – jeśli jedna osoba jest ojcem drugiej, to druga na pewno nie jest ojcem pierwszej.

Relacja jest słabo asymetryczna (słabo antysymetryczna) gdy dla wszystkich różnych od siebie elementów uniwersum jest tak, że jeśli relacja zachodzi w jedną stronę, to nie zachodzi w drugą. Symbolicznie:

R jest słabo asymetryczna º "x"y [(x ...