Matematyka dyskretna dla informatyków. Wykład 3,4,5 (9.11.98) Wersja 1.0

1 Relacje

1.1 Podstawowe poj_{}ecia

Poj_{}ecie relacji jest jednym z najważniejszych w matematyce i informatyce. Formalnie relacj _{}a n-argumentow _{}a określon _{}a w zbiorach A_{1} × ⋯ × A_{n} nazwiemy dowolny podzbiór iloczynu kartezjańskiego A_{1} × ⋯ × A_{n}. Czyli określenie relacji polega na wybraniu z wszystkich możliwych n-tek (a_{1},…, a_{n}) : a_{1} ∈ A_{1}, ⋯, a_{n} ∈ A_{n} takich, których zestawienie z jakiegoś powodu nas interesuje. Niech na przykład A_{1} oznacza zbiór pasażerów w pewnej bazie danych, A_{2} zbiór linii lotniczych w tej bazie, zaś A_{3} — zbiór wszystkich poł _{}aczeń lotniczych zarejestrowanych w tej bazie. Zbiór A_{1} ×A_{2} ×A_{3} oznacza zestawienie wszystkich możliwości lotu każdego z pasażerów na każdej z tras każd _{}a z linii. Elementami tego zbioru b_{}ed _{}a też trójki, które w rzeczywistości mog _{}a nie odpowiadać stanowi faktycznemu choćby z tego powodu, że dana linia lotnicza na danej trasie może nie mieć żadnego lotu w rozkładzie. Nas b_{}ed _{}a interesowały rezerwacje, których pasażerowie dokonali w tej bazie danych. Możemy określić relacj_{}e R dokonanych rezerwacji w taki sposób, że (a_{1}, a_{2}, a_{3}) ∈ R wtedy i tylko wtedy gdy pasażer a_{1} dokonał rezerwacji lotu w liniach lotniczych a_{2} na trasie a_{3}.

Zauważmy przy tym, że jeden pasażer może dokonać kilku rezerwacji na danej trasie w różnych liniach, że kilku różnych pasażerów może dokonać rezerwacji na t_{}e sam _{}a tras_{}e t _{}a sam _{}a lini _{}a, że w końcu jeden pasażer może korzystać z usług jednej linii na kilku trasach. Wszystkie te sytuacje możemy wyrazić umieszczaj _{}ac odpowiednie zestawienia w relacji R. Nasza relacja jest jednak za słaba, żeby wyrazić np. fakt rezerwacji kilku różnych lotów t _{}a sam _{}a lini _{}a na identycznej trasie przez tego samego pasażera (np. dzień po dniu). Gdybyśmy chcieli i t_{}e wiadomość uj _{}ać w relacji opisuj _{}acej rezerwacje, musielibyśmy wprowadzić dodatkowe zbiory opisuj _{}ace konkretne loty i daty i określić now _{}a relacj_{}e, np. 5-argumentow _{}a, której elementem b_{}edzie pi _{}atka (pasażer, linia lotnicza, trasa, nr lotu, data).

Szczególnym rodzajem relacji s _{}a relacje dwuargumentowe. Stanowi _{}a one na tyle ważn _{}a klas_{}e relacji, że b_{}edziemy opuszczali przymiotnik ,,dwuargumentowa” i mówi _{}ac o relacjach bez dodatkowych określeń b_{}edziemy rozumieli właśnie relacje dwuargumentowe.

Jak zobaczyliśmy, zbiory poł _{}aczone relacj _{}a mog _{}a być bardzo różne. Czasami jednak zdarza si_{}e, że wszystkie składniki relacji, szczególnie dwuargumentowej, s _{}a identyczne. Relacja taka jest wtedy podzbiorem kwadratu kartezjańskiego A × A oznaczanego też przez A^{2}. Mówimy wtedy, że relacja jest określona w zbiorze A.

Przykładami takich relacji s _{}a:

• Relacja niemniejszości określona w zbiorze liczb naturalnych, czyli ≤IN = {(a, b) ∈ IN^{2}∃k ∈ IN : a + k = b}.

• Relacja niemniejszości określona w zbiorze liczb rzeczywistych, czyli ≤R= {(a, b) ∈ R^{2}∃c ∈ R : a + c^{2} = b}.

• Relacja przystawania modulo n w zbiorze liczb naturalnych, czyli mod_{n} = {{(a, b) ∈ IN^{2}∃k, l, r ∈ IN : a = kn + r, b = ln + r}

Rzecz jasna nie s _{}a to jedyne możliwe sposoby definiowania tych sk _{}adin _{}ad znanych relacji. Zwykle w przypadku relacji dwuargumentowych stosuje si_{}e notacj_{}e infiksow _{}a pisz _{}ac np. zamiast (2, 5) ∈≤IN po prostu 2 ≤IN 5 lub wr_{}ecz 2 ≤ 5, gdy jasne jest w jakiej dziedzinie (w tym przypadku — naturalnej) relacja ≤ została określona.

Dziedzin _{}a relacji nazwiemy zbiór tych elementów, które wyst_{}epuj _{}a jako pierwszy składnik par wchodz _{}acych w jej skład, a przeciwdziedzin _{}a — zbiór tych elementów, które wyst_{}epuj _{}a jako drugi składnik par wchodz _{}acych w jej skład. Przykładowo dziedzin _{}a relacji ostrej wi_{}ekszości określonej na liczbach naturalnych jest zbiór IN\{0}, zaś przeciwdziedzin _{}a zbiór IN. Relacja pusta, to po prostu zbiór pusty, a relacja pełna, to zbiór A × A = A^{2}. Żadne dwa elementy nie s _{}a ze sob _{}a w relacji pustej; każde dwa elementy s _{}a ze sob _{}a w relacji pełnej.

Relacj _{}a odwrotn _{}a do relacji R ⊆ A × B nazwiemy relacj_{}e R^{−1} określon _{}a w B × A w nast_{}epuj _{}acy sposób: (b, a) ∈ R^{−1} ⇔ (a, b) ∈ R. Zauważmy, że (R^{−1})^{−1} = R.

Dla dwóch relacji binarnych R_{1} ∈ A_{1} × A_{2} oraz R_{2} ∈ A_{2} × A_{3} określamy ich złożenie jako relacj_{}e R ⊆ A_{1} × A_{3} w nast_{}epuj _{}acy sposób: (a_{1}, a_{3}) ∈ R ⇔ ∃a_{2} ∈ A_{2} : (a_{1}, a_{2}) ∈ R_{1}, (a_{2}, a_{3}) ∈ R_{2}. Najcz_{}eściej mamy do czynienia z sytuacj _{}a, gdy A_{1} = A_{2} = A_{3}, czyli gdy wszystkie relacje s _{}a określone w tym samym zbiorze. Wtedy interpretuj _{}ac relacje w postaci strzałek ł _{}acz _{}acych elementy zbioru musimy rozróżnić (na przykład kolorem) te pary punktów, które s _{}a poł _{}aczone relacj _{}a R_{1} (powiedzmy strzałki czerwone) oraz te. które s _{}a poł _{}aczone relacj _{}a R_{2} (powiedzmy strzałki zielone). Wtedy złożenie R_{1} i R_{2} b_{}edzie relacj _{}a, która ł _{}aczy ze sob _{}a te elementy, które s _{}a poł _{}aczone dwiema kolejnymi strzałkami: najpierw czerwon _{}a, a potem zielon _{}a. Ustalmy też notacj_{}e dla relacji złożonej ze sob _{}a kilka razy. Przyjmijmy, że R^{0} = id oraz R^{n+1} = R · R^{n} dla n ≥ 0.

Pewna klasa relacji odgrywa ogromne znaczenie w matematyce. Niektóre relacje R ⊆ A_{1} × ⋯ × A_{n} maj _{}a t_{}e cech_{}e, że gdy ustalimy elementy a_{1},…, a_{n−1}, wówczas tylko co najwyżej jeden element a_{n} b_{}edzie z nimi w relacji, czyli spełniony jest ogólny warunek: ∀a_{1} ∈ A_{1},…, a_{n−1} ∈ A_{n−1}(∃a_{n}, a′_{n} ∈ A_{n} : (a_{1},…, a_{n−1}, a_{n}) ∈ R ∧ (a_{1},…, a_{n−1}, a′_{n}) ∈ R ⇒ a_{n} = a′_{n}. Innymi słowy jeśli dwa elementy a_{n} oraz a′_{n} s _{}a w relacji R z elementami a_{1},…, a_{n−1}, to musz _{}a być sobie równe. Dokładniej: jeżeli ustalimy elementy a_{1},…, a_{n−1}, to s _{}a dwie możliwości: albo nie b_{}edzie żadnego elementu wchodz _{}acego z nimi w relacj_{}e (implikacja wyst_{}epuj _{}aca w definicji jest w sposób trywialny prawdziwa, jako że poprzednik implikacji jest fałszywy), albo b_{}edzie tylko jeden taki element. Relacj_{}e R, która spełnia powyższy warunek nazywamy funkcj _{}a cz_{}eściow _{}a, albo, krócej, funkcj _{}a. Jeżeli dodatkowo dla każdych a_{1},…, a_{n−1} istnieje element a_{n} (rzecz jasna jedyny) b_{}ed _{}acy z nimi w relacji, to funkcja taka nazywa si_{}e funkcj _{}a całkowit _{}a.

Zauważmy, że szkolne poj_{}ecie funkcji odpowiada funkcji całkowitej, a poj_{}ecia dziedziny funkcji, złożenia funkcji, odwracania funkcji, znane ze szkoły średniej s _{}a szczególnymi przypadkami powyższych określeń dla relacji. Zauważmy też, że choć dla każdej relacji istnieje relacja odwrotna, to nie dla każdej funkcji istnieje funkcja odwrotna. Relacja odwrotna do relacji, która jest funkcj _{}a, sama być funkcj _{}a nie musi. Na przykład relacja {(x, y) ∈ R^{2} : x^{2} = y} jest funkcj _{}a, ale relacja odwrotna {(y, x) ∈ R^{2} : x^{2} = y} już funkcj _{}a nie jest. Należ _{}a do niej choćby pary (1, −1) oraz (1, 1). Przykład Rozważmy relacj_{}e log_{2} określon _{}a w zbiorze R w nast_{}epuj _{}acy sposób: (x, y) ∈ log_{2} ⇔ x > 0 ∧ 2^{y} = x. Dziedzin _{}a tej relacji jest zbiór wszystkich liczb dodatnich, przeciwdziedzin _{}a cały zbiór R. Relacja ta jest funkcj _{}a. Należ _{}a do niej przykładowo pary

(\frac{1}{1024}, −10), (\frac{1}{2}, −1), (1, 0), (2, 1), (1024, 10).

Jest to funkcja logarytmiczna. Standardowo piszemy np. zamiast (2, 1) ∈ log_{2} po prostu log_{2}(2) = 1 lub wr_{}ecz log_{2} 2 = 1. Relacja odwrotna do log_{2} jest także funkcj _{}a. Jej dziedzin _{}a jest zbiór R, a przeciwdziedzin _{}a zbiór R_{+}. Składa si_{}e ona m.in. z par

(−10, \frac{1}{1024}), (−1, \frac{1}{2}), (0, 1), (1, 2), (10, 1024).

Jest to funkcja wykładnicza. Złożenie relacji log_{2} oraz relacji odwrotnej log_{2}^{−1} jest także funkcj _{}a. Jest to funkcja identycznościowa na zbiorze R_{+} (czyli zbiór par (x, x) takich że x ∈ R_{+}). Z kolei złożenie relacji (funkcji) log_{2}^{−1} oraz relacji (funkcji) do niej odwrotnej, czyli log_{2} także jest funkcj _{}a, ale nieco inn _{}a. Też jest to funkcja identycznościowa, ale na całym zbiorze R.

Niektóre cechy relacji s _{}a szczególnie ważne. Przedstawimy teraz podstawowe rodzaje relacji. Niech R ⊆ X × X dla pewnego ustalonego zbioru X.

• R jest zwrotna ⇔ ∀a ∈ X : (a, a) ∈ R.

• R jest przeciwzwrotna ⇔ ∀a ∈ X : (a, a) ∉ R.

• R jest symetryczna ⇔ ∀a, b ∈ X : (a, b) ∈ R ⇒ (b, a) ∈ R.

• R jest asymetryczna ⇔ ∀a, b ∈ X : (a, b) ∈ R ⇒ (b, a) ∉ R.

• R jest antysymetryczna ⇔ ∀a, b ∈ X : (a, b) ∈ R ∧ (b, a) ∈ R ⇒ a = b.

• R jest przechodnia ⇔ ∀a, b, c ∈ X : (a, b) ∈ R ∧ (b, c) ∈ R ⇒ (a, c) ∈ R.

• R jest spójna ⇔ ∀a, b ∈ X : (a, b) ∈ R ∨ (b, a) ∈ R.

Ważnym poj_{}eciem jest też domkni_{}ecie relacji ze wzgl_{}edu na pewn _{}a cech_{}e, czyli jej uzupełnienie o minimaln _{}a liczb_{}e elementów tak, aby zapewnić zachodzenie tej cechy. Zwłaszcza istotne s _{}a domkni_{}ecia przechodnie, a także symetryczne i zwrotne. Zacznijmy może od tego ostatniego. Domkni_{}eciem zwrotnym relacji R nazwiemy relacj_{}e R ∪ id. Domkni_{}ecie symetryczne relacji R, to relacja R ∪ R^{−1}. Domkni_{}ecie przechodnie relacji R, to relacja, która składa si_{}e z wszystkich par (a, b) takich, że (a, b) ∈ R^{n} dla pewnego n ≥ 1. Domkni_{}ecie przechodnie relacji R b_{}edziemy oznaczali symbolem R^{+}, domkni_{}ecie zwrotne symbolem R^{z}, domkni_{}ecie symetryczne symbolem R^{s}, a domkni_{}ecie jednocześnie zwrotne i przechodnie symbolem R^{∗}.

Jeżeli spojrzymy na relacj_{}e R graficznie jako na strzałki ł _{}acz _{}ace ze sob _{}a narysowane punkty, to jej domkni_{}ecie zwrotne odpowiada dorysowaniu brakuj _{}acych p_{}etelek (czyli strzałek prowadz _{}acych od każdego w_{}ezła do siebie samego) przy każdym punkcie, domkni_{}ecie symetryczne — uzupełnienie każdej strzałki o przeciwny kierunek, a domkni_{}ecie przechodnie — poł _{}aczenie strzałk _{}a każdej pary punktów (a, b) takiej, że z a do b można dojść po strzałkach relacji R.

Zauważmy w końcu, że relacje s _{}a zbiorami, wi_{}ec można na nich wykonywać wszystkie działania teorii zbiorów, a wi_{}ec sumowanie, iloczyn, różnic_{}e, dopełnienie itd.

Przedstawimy teraz kolekcj_{}e relacji każdemu doskonale znanych z życia codziennego i spróbujemy zilustrować wprowadzone poj_{}ecia. Załóżmy, że rozważamy relacje rodzinne w zbiorze ludzi znajduj _{}acych si_{}e obecnie na ziemi (można też dorzucić do tego zbioru par_{}e minionych pokoleń). W tym zbiorze określone s _{}a naturalne relacje MATKA i OJCIEC. Powiemy, że (x, y) ∈ MATKA jeśli y jest matk _{}a x, zaś (x, y) ∈ OJCIEC jeśli y jest ojcem x. Załóżmy też istnienie jednoargumentowych relacji ON i ONA mówi _{}acych o tym, czy ktoś jest m_{}eżczyzn _{}a czy kobiet _{}a. Zatem x ∈ ONA, albo, krócej, ONA(x), gdy x jest kobiet _{}a i analogicznie dla m_{}eżczyzn. Z przyczyn technicznych warto też zdefiniować relacje ONI = {(x, x) : ON(x)} oraz ONE = {(x, x) : ONA(x)}. Relacje ONI i ONE s _{}a podzbiorami relacji id. Dowolna relacja złożona z relacj _{}a ONI (ONE) pozostawi tylko te elementy, które na drugiej współrz_{}ednej maj _{}a m_{}eżczyzn (kobiety). Podobnie, relacja ONI (ONE) złożona z dowoln _{}a relacj _{}a pozostawi z niej tylko te pary, które maj _{}a na pierwszej współrz_{}ednej m_{}eżczyzn (kobiety). Podstawowymi relacjami b_{}ed _{}a też relacje M _{}AŻ = {(x, y) : y jest m_{}eżem x} i ŻONA = M _{}AŻ^{−1}.

B_{}ed _{}a to nasze relacje bazowe i z nich wyprowadzimy znane sk _{}adin _{}ad dalsze relacje rodzinne.

• Relacja ,,x jest rodzicem y” to po prostu relacja RODZIC = MATKA ∪ OJCIEC

• Relacja ,,b jest bratem a”, to relacja BRAT = {(a, b) : a ≠ b ∧ ON(b) ∧ ∃m, o : MATKA(a, m), MATKA(b, m), OJCIEC(a, o), OJCIEC(b, o)}. Zauważmy, że relacja ((MATKA·MATKA^{−1})∩(OJCIEC·OJCIEC^{−1})\id)·ONI jest dokładnie relacj _{}a BRAT.

• SIOSTRA = ((MATKA · MATKA^{−1}) ∩ (OJCIEC · OJCIEC^{−1}) \ id)ONE

• Relacja CAŁE RODZEŃSTWO = (MATKA∪OJCIEC)(MATKA∪OJCIEC)^{−1}\id definiuje rodzeństwo zarówno naturalne, jak i przyrodnie.

• Relacja OJCIEC · BRAT to STRYJ.

• Spróbujmy zdefiniować relacj_{}e WUJ. Jest to niew _{}atpliwie brat matki, a wi_{}ec możemy go zdefiniować jako MATKA · BRAT (najpierw idziemy po strzałce do matki, a potem do jej brata). Wujem też nazywa si_{}e m_{}eża ciotki. Zatem kim jest ciotka? Ciotka, to siostra matki lub ojca, wi_{}ec CIOTKA = RODZICSIOSTRA. Uwaga: zgodnie z polsk _{}a tradycj _{}a żona wuja to wujenka, a nie ciotka. Inaczej mielibyśmy małe kłopoty: do zdefiniowania wuja byłaby potrzebna ciotka (jako jego żona), a do zdefiniowania ciotki — wuj (jako jej m _{}aż). Groziłoby to zap_{}etleniem si_{}e. Ostatecznie jednak WUJ = MATKA · BRAT ∪ CIOTKA · M _{}AŻ.

• Dziadek, to rodzic do kwadratu płci m_{}eskiej: DZIADEK = RODZIC^{2}ONI, a babcia to BABCIA = RODZIC^{2}ONE. Można też inaczej: DZIADEK = RODZIC · OJCIEC, a BABCIA = RODZIC · MATKA.

• WNUCZ _{}E = (DZIADEK ∪ BABCIA)^{−1}, zaś WNUK = WNUCZ _{}E · ONI.

• PRZODEK = RODZIC^{+}, POTOMEK = PRZODEK^{−1}.

• KREWNY = PRZODEK^{z} · POTOMEK^{z}. Ktoś jest zatem moim krewnym, jeśli znajd_{}e takiego swojego przodka, którego on jest potomkiem.

Podamy teraz definicj_{}e grafu relacji, która zostanie później uogólniona. Grafem relacji R określonej w zbiorze A nazwiemy par_{}e (A, R). Zbiór A nazywamy zbiorem w_{}ezłów lub wierzchołków grafu, a zbiór R — zbiorem jego kraw_{}edzi. Grafy b_{}edziemy reprezentowali graficznie w postaci rysunków, w których w_{}ezły s _{}a punktami, a elementy relacji — strzałkami.

Ścieżk _{}a długości n w grafie relacji (A, R) nazwiemy ci _{}ag v_{0}, e_{1}, v_{1}, e_{2},…, e_{n}, v_{n}, gdzie dla każdego i = 1,…, n : e_{i} = (v_{i−1}, v_{i}). Ścieżk _{}a jest zatem ci _{}ag kolejnych w_{}ezłów i kraw_{}edzi prowadz _{}acych od v_{0} do v_{n}. Jeżeli v_{0} = v_{n}, to ścieżk_{}e nazywamy cyklem. Jeśli dodatkowo żaden pozostałych z w_{}ezłów si_{}e nie powtarza, to taki cykl nazywamy prostym.

Graf nazwiemy pełnym, jeśli R = A^{2}, czyli gdy jest grafem relacji pełnej: każde dwa elementy A s _{}a wtedy ze sob _{}a w relacji. Graf relacji symetrycznej b_{}edziemy nazywali niezorientowanym i strzałki odpowiadaj _{}ace relacjom b_{}edziemy rysować w postaci odcinków zakładaj _{}ac, że każdy (niezorientowany) odcinek reprezentuje dwie strzałki: po jednej dla każdego kierunku.

1.2 Relacje równoważności i podziały

Relacj _{}a równoważności jest każda relacja jednocześnie zwrotna, symetryczna i przechodnia.

Przykłady relacji równoważności:

• Relacja równości elementów dowolnego zbioru (identyczność) jest relacj _{}a równoważności.

• Relacja osi _{}agalności w grafie relacji zwrotnej i symetrycznej, któr _{}a definiujemy tak: b jest osi _{}agalne z a, jeśli istnieje ścieżka prowadz _{}aca w tym grafie od a do b.

• Relacja RODZEŃSTWO, która obejmuje te pary, które maj _{}a identycznych rodziców.

• Relacja mod_{n} przystawania modulo n dla n > 0 w zbiorze liczb naturalnych: (a, b) ∈ mod_{n} ⇔ amodn = bmodn.

• Relacja należenia do tej samej grupy ćwiczeniowej z PRG.

Nie s _{}a natomiast relacjami równoważności nast_{}epuj _{}ace relacje:

• Relacja pokrewieństwa KREWNY. (brak przechodniości!)

• Relacja BRAT(ani zwrotna ani symetryczna ani przechodnia!)

• Relacja należenia do tej samej grupy ćwiczeniowej z czegokolwiek w PJWSTK.

Klas _{}a abstrakcji elementu a ∈ A relacji równoważności R nazwiemy zbiór {b : (a, b) ∈ R}. Klas_{}e abstrakcji elementu a oznaczamy przez [a]. Zbiór klas abstrakcji relacji R oznaczamy przez A/R i nazywamy zbiorem ilorazowym. Podziałem zbioru A nazwiemy rodzin_{}e jego podzbiorów A_{1},…, A_{k} tak _{}a, że spełnione s _{}a dwa warunki:

• A_{1} ∪ ⋯ ∪ A_{k} = A

• ∀i ≠ j : A_{i} ∩ A_{j} = ∅.

Czyli podziałem zbioru A nazywamy każdy zbiór rozł _{}acznych parami podzbiorów zbioru A, które w sumie daj _{}a cały zbiór A. Zasada abstrakcji głosi, że mi_{}edzy podziałami zbioru, a relacjami równoważności istnieje wzajemna odpowiedniość. Każda relacja równoważności wyznacza pewien podział, a każdy podział definiuje unikaln _{}a relacj_{}e równoważności: tak _{}a, że para elementów jest ze sob _{}a w tej relacji, gdy oba elementu znajduj _{}a si_{}e w jednym podzbiorze.

Przykłady:

• Relacja osi _{}agalności definiuje podział zbioru A na regiony poł _{}aczone ze sob _{}a ścieżkami w grafie relacji. W szczególności gdybyśmy rozważali graf poł _{}aczeń drogowych na kuli ziemskiej, to zapewne jedn _{}a klas_{}e abstrakcji stanowiłyby wszystkie kontynentalne w_{}ezły azjatyckie, europejskie i afrykańskie, kolejn _{}a w_{}ezły obu Ameryk, kolejn _{}a — w_{}ezły australijskie, dalej osobno w_{}ezły brytyjskie, islandzkie itd. Ogólnie każda wyspa stanowiłaby swoj _{}a klas_{}e abstrakcji.

• Relacja RODZEŃSTWO utożsamia dzieci tych samych rodziców. Z pewnych wzgl_{}edów rozróżnianie mi_{}edzy nimi może być nieistotne: na przykład gdy rodzic dostaje zaproszenie na jak _{}aś imprez_{}e dla siebie i jednego dziecka, to nie ważne, które ze swoich dzieci ze sob _{}a zabierze. Mówi _{}ac w j_{}ezyku potocznym ,,jedno dziecko” mamy w takim przypadku na myśli reprezentanta odpowiedniej klasy abstrakcji relacji RODZEŃSTWO.

• Relacja mod_{n} dzieli zbiór liczb naturalnych na n klas abstrakcji. Do pierwszej z nich należ _{}a te wszystkie liczby, które przy dzieleniu przez n daj _{}a reszt_{}e 0, do drugiej — te, które daj _{}a reszt_{}e 1, …, do n-tej te, które daj _{}a reszt_{}e n − 1.

Praktyka pokazuje, że przy analizie systemów należy abstrahować od nieistotnych szczegółów ustalaj _{}ac możliwie duż _{}a relacj_{}e równoważności, która pozwoli skoncentrować si_{}e na istotych różnicach. Zbiór ilorazowy takiej relacji jest z reguły prostszy i przez to łatwiejszy do implementacji. Ustalenie odpowiedzniej relacji równoważności jest jednym z podstawowych narz_{}edzi informatyka porz _{}adkuj _{}acego badany przez siebie świat.

1.3 Relacje porz _{}adku

Inn _{}a ważn _{}a klas _{}a relacji s _{}a relacje porz _{}adkuj _{}ace zbiór. Ze szkoły znamy najprostsze takie relacje: porz _{}adki liczbowe. Zbiory liczb naturalnych, wymiernych i rzeczywistych s _{}a uporz _{}adkowane relacj _{}a niemniejszości. Uogólnimy teraz to poj_{}ecie.

Relacja R określona na zbiorze A jest relacj _{}a porz _{}adku cz_{}eściowego lub, krócej, relacj _{}a porz _{}adku, wtedy i tylko wtedy gdy jest

• zwrotna

• antysymetryczna

• przechodnia.

Zauważmy, że relacje ≤ porz _{}adkuj _{}ace zbiory liczbowe spełniaj _{}a wszystkie te własności. Zauważmy, że nie ma założenia o spójności relacji porz _{}adku cz_{}eściowego. Może si_{}e zdarzyć, że relacja porz _{}adku nie jest w stanie uporz _{}adkować dwóch różnych elementów. Oznacza to, że może si_{}e zdarzyć sytuacja, w której nie można stwierdzić ani że (a, b) ∈ R, ani że (b, a) ∈ R. Natomiast gdy relacja porz _{}adku cz_{}eściowego jest dodatkowo spójna (czyli mi_{}edzy każdymi dwoma elemenatmi można określić, który z nich jest wi_{}ekszy lub równy), to tak _{}a relacj_{}e nazwiemy relacj _{}a porz _{}adku liniowego.

Przykłady.

• Relacja ≤IN porz _{}adkuj _{}aca punkty przestrzeni IN^{n}, czyli wektory liczb naturalnych. Powiemy, że (a_{1},…, a_{n}) ≤ (b_{1},…, b_{n}) ⇔ a_{1} ≤ b_{1} ∧ ⋯ ∧ a_{n} ≤ b_{n}.

• Relacja porz _{}adku leksykograficznego, stosowana w słownikach. Na zbiorach słów nad danym skończonym alfabetem definiujemy porz _{}adek w nast_{}epuj _{}acy sposób. Po pierwsze określamy porz _{}adek liter w alfabecie. Nast_{}epnie maj _{}ac dwa słowa ustalamy, że interesuje nas pierwsza od lewej różni _{}aca je litera. Mniejsze b_{}edzie to słowo, którego taka pierwsza od lewej rózni _{}aca je litera jest mniejsza w sensie porz _{}adku alfabetycznego od swojej odpowiedniczki w drugim słowie. Jeżeli takiej litery nie ma, to jedno z rozważanych słów musi być pocz _{}atkiem drugiego. Wtedy to z nich, które jest krótsze jest mniejsze. Jeśli oba s _{}a dodatkowo tej samej długości, to s _{}a one równe.

• Porz _{}adkujemy punkty płaszczyzny w układzie kartezjańskim nast_{}epuj _{}aco: (x_{1}, y_{1}) ≤_{K} (x_{2}, y_{2}) ⇔ (x_{1} < x_{2}) ∨ (x_{1} = x_{2}) ∧ (y_{1} ≤ y_{2}). Zdefiniowany porz _{}adek nazywamy leksykograficznym porz _{}adkiem kartezjańskim.

• Porz _{}adkujemy punkty płaszczyzny nast_{}epuj _{}aco: każdemu punktowi przypisujemy par_{}e liczb: (r, φ). Zakładamy przy tym, że r ≥ 0, 0 ≤ φ < 2π. Interpretujemy r jako odległość od środka układu współrzednych O, zaś φ jako miar_{}e k _{}ata mi_{}edzy osi _{}a OX, a prost _{}a ł _{}acz _{}ac _{}a pocz _{}atek układu współrz_{}ednych z naszym punktem, o ile jest on różny od O. Umawiamy si_{}e dodatkowo, że punkt O ma współrz_{}edne (0, 0).

Reszta — tak jak poprzednio: (r_{1}, φ_{1}) ≤_{B} (r_{2}, φ_{2}) ⇔ (r_{1} < r_{2}) ∨ (r_{1} = r_{2}) ∧ (φ_{1} ≤ φ_{2}). Zdefiniowany porz _{}adek nazywamy leksykograficznym porz _{}adkiem biegunowym.

• Relacja inkluzji na zbiorze podzbiorów dowolnego zbioru.

• Relacja porz _{}adku na zbiorze funkcji rzeczywistych określonych na domkni_{}etym odcinku [a, b] zdefiniowana nast_{}epuj _{}aco: f ≤ g ⇔ ∀x ∈ [a, b] : f(x) ≤ g(x).

Zauważmy, poza pierwsz _{}a i ostatni _{}a z przykładowych relacji wszystkie przykładowe relacje s _{}a relacjami porz _{}adku całkowitego. Ostatnia relacja porz _{}adku na funkcjach jest relacj _{}a porz _{}adku cz_{}eściowego: nie sposób np. stwierdzić, która z dwóch funkcji: f(x) = x^{2} oraz g(x) = 1 jest wi_{}eksza na przedziale [0..2].

Porz _{}adki leksykograficzne stanowi _{}a z informatycznego punktu widzenia wyj _{}atkowo ważn _{}a klas_{}e porz _{}adków. Umożliwiaj _{}a one określenie relacji porz _{}adku liniowego na iloczynach kartezjańskich (bazy danych!) gdy dane s _{}a porzadki liniowe na składnikach tego iloczynu.

Ważnymi poj_{}eciami s _{}a też określenia elementów najwi_{}ekszych i maksymalnych (odpowiednio najmniejszych i minimalnych).

Niech ≤_{A} b_{}edzie relac _{}a porz _{}adku cz_{}eściowego określonego w zbiorze A. Elementem najwi_{}ekszym (odp. najmniejszym) nazwiemy taki element a ∈ A, że dla każdego b ∈ A zachodzi b ≤_{A} a (odp. a ≤_{A} b). Elementem maksymalnym (odp. minimalnym) nazwiemy taki element a ∈ A, że nie istnieje różny od a element b ∈ A taki, że a ≤_{A} b (odp. b ≤_{A} a).

Przykład 1: Rozważmy zbiór niezerowych wektorów o współrz_{}ednych naturalnych oraz relacj_{}e ≤IN porz _{}adku cz_{}eściowego po współrz_{}ednych (zdefiniowan _{}a wcześniej w przykładach). W zbiorze tym istniej _{}a trzy elementy minimalne: [1, 0, 0], [0, 1, 0] oraz [0, 0, 1]. Nie ma w tym zbiorze elementu najmniejszego, ani maksymalnego (a tym bardziej najwi_{}ekszego). Gdybyśmy uzupełnili ten zbiór o wektor zerowy [0, 0, 0], to stałby si_{}e on elementem najmniejszym tej relacji i jednocześnie jedynym minimalnym.

Przykład 2: Rozważmy domkni_{}ecie zwrotne relacji ,,bycia przodkiem” w drzewie genealogicznym ludzkości. Powiemy wi_{}ec, że xPRZODEK^{z}y, jeśli x jest przodkiem y lub x = y. Jest to relacja cz_{}eściowego porz _{}adku (patrz ćwiczenia do tego rozdziału). Umówmy si_{}e, że xPRZODEK^{z}y b_{}edzie miało znaczenie x ≤ y (żeby określić kierunek strzałek). Elementy maksymalne tej relacji, to wszyscy ludzie, którzy nigdy nie mieli, lub nie maj _{}a dzieci. Elementy minimalne s _{}a dwa: Adam i Ewa.

Zauważmy, w każdej relacji porz _{}adku każdy element najwi_{}ekszy jest maksymalny (a najmniejszy — minimalny), ale nie na odwrót. W zbiorze może być co najwyżej jeden element najwi_{}ekszy (najmniejszy), a elementów maksymalnych może być wi_{}ecej niż jeden.

Relacje porz _{}adkuj _{}ace pełni _{}a fundamentaln _{}a rol_{}e w przygotowaniu danych do ich wykorzystania w algorytmach. Przede wszystkim chodzi tu o algorytm przeszukiwania binarnego, który omówimy dokładnie na programowaniu. Aby móc zastosować ten algorytm trzeba mieć relacj_{}e porz _{}adku liniowego. Czasami tak _{}a relacj_{}e wprowadza si_{}e całkowicie sztucznie (np. porz _{}adkuje si_{}e kolory, rodzaje materiału itp.) tylko po to, żeby wymusić odpowiedź na pytanie, który element jest wi_{}ekszy lub równy.

Okazuje si_{}e też, co pokazał Szpilrajn, że każd _{}a relacj_{}e porz _{}adku cz_{}eściowego można uzupełnić o takie elementy, aby stała si_{}e relacj _{}a porz _{}adku całkowitego. Algorytmy, które tego dokonuj _{}a nazywaj _{}a si_{}e algorytmami sortowania topologicznego.

1.4 Podobieństwa i pokrycia

Cz_{}esto spotykamy si_{}e z sytuacj _{}a, kiedy interesuj _{}aca nas relacja maj _{}aca pogrupować elementy w grupy o zbliżonych właściwościach nie jest przechodnia. Przykładem takiej relacji jest relacja podobieństwa w rodzinie. Cz_{}esto zdarza si_{}e tak, że ojciec jest podobny do córki, córka do matki, a ojciec do matki — niekoniecznie. Mówi si_{}e co prawda, że to córka jest podobna do ojca, ale przyjmiemy tutaj, że relacja podobieństwa w rodzinie jest symetryczna.

Ogólnie relacj _{}a podobieństwa nazwiemy każd _{}a relacj_{}e zwrotn _{}a i symetryczn _{}a. Przykłady relacji podobieństwa:

• Relacja pokrewieństwa KREWNY. Matka jest krewn _{}a syna, syn krewnym ojca, ale matka na ogól krewn _{}a ojca nie jest.

• Relacja podobngo owłosienia głowy zdefiniowana tak, że podobne owłosienie maj _{}a takie dwie osoby, których liczba włosów na głowie różni si_{}e co najwyżej o jeden. Zwrotność i symetryczność tej relacji jest oczywista, a przechodniość nie zachodzi: gdyby tak było, to kompletnie łysy facet miałby owłosienie podobne do Claudii Schiffer.

• Wszystkie relacje równoważności (nie jest wcale zastrzeżone, że podobieństwo nie może być relacj _{}a przechodni _{}a).

Dla danej relacji podobieństwa ważne jest określenie maksymalnych podzbiorów, w których ta relacja jest też przechodnia. W pewnym sensie możemy mówić wtedy o silnym podobieństwie ze wzgl_{}edu na pewn _{}a cech_{}e. Tyle tylko, że ta cecha nie musi być jednakowa dla wszystkich takich grup (tak było w przypadku relacji równoważności). Na przykład dla relacji pokrewieństwa takim podzbiorem może być zbiór krewnych danej osoby. Typem podobieństwa b_{}edzie w tym przypadku pokrewieństwo z t _{}a właśnie osob _{}a.

Niech zatem dla danej relacji podobieństwa P typem podobieństwa b_{}edzie każdy maksymalny podzbiór elementów, w którym każde dwa s _{}a ze sob _{}a w relacji P.

Pokryciem zbioru A nazwiemy k _{}ażd _{}a tak _{}a rodzin_{}e jego podzbiorów {A_{1}, A_{2} …, że A_{1} ∪ A_{2}∪, ⋯ = A. Pokrycie P nazwiemy właściwym, jeśli żaden podzbiór A_{i} ∈ P nie jest podzbiorem żadnego A_{j} ∈ P dla i ≠ j.

Okazuje si_{}e, że mi_{}edzy relacjami podobieństwa, a pokryciami właściwymi każdego zbioru istnieje analogiczny zwi _{}azek, jak mi_{}edzy relacjami równoważności, a podziałami. Jeżeli dane jest podobieństwo P, to zbiór typów tego podobieństwa stanowi jednoznacznie wyznaczone pokrycie. Jest to pokrycie właściwe. Na odwrót, jeśli dane jest pokrycie właściwe P = A_{1}, A_{2},… zbioru A, to relacja P = {(a, b)} : ∃i : (a, b) ∈ A_{i} jest relacj _{}a podobieństwa.

Jeżeli relacja podobieństwa jest jednocześnie relacj _{}a równoważności, to pokrycie z ni _{}a zwi _{}azane jest podaziałem, a typy tej relacji podobieństwa s _{}a klasami abstrakcji.

Zadania

1. Zadania 1/140, 2/141,13,14/142,3,6,7,8,9,10/141 z ,,Matematyki dyskretnej”.

2. Które ze zdefiniowanych własności spełniaj _{}a relacje pusta i pełna?

3. Czy prawdziwe s _{}a nast_{}epuj _{}ace stwierdzenia

• Jeśli relacja jest asymetryczna (odp. przeciwzwrotna), to nie jest symetryczna (odp. zwrotna)

• Jeśli relacja jest symetryczna i przechodnia, to jest zwrotna

• Domkni_{}ecie przechodnie relacji przechodniej jest jej równe

• Wynik domkni_{}ecia relacji zwrotnego, symetrycznego i przechodniego zależy od kolejności dokonywania tych domkni_{}eć

• Domkni_{}ecie zwrotne, symetryczne i przechodnie jest relacj _{}a pełn _{}a

4. Zdefiniuj w rachunku relacji wychodz _{}ac od relacji zdefinowanych w tekście nast_{}epuj _{}ace relacje rodzinne:

• Stryjenka (żona stryja)

• J _{}atrew (w tym stosunku rodzinnym s _{}a ze sob _{}a żony braci)

• Kuzyn (wspólni dziadkowie, ale nie rodzice)

• Szwagier (m _{}aż siostry albo brat żony lub m_{}eża).

5. Które z poniższych równości s _{}a prawdziwe:

• DZIADEK = ONI · RODZIC^{2}?

• SIOSTRA = RODZEŃSTWO · ONE?

• BRAT · BRAT^{−1} = BRAT^{−1} · BRAT?

6. Dla każdej z relacji rodzinnych określ, czy jest ona zwrotna, symetryczna, przechodnia, antysymetryczna.

7. Pokaż, że relacja PRZODEK^{z} jest relacj _{}a cz_{}eściowego porz _{}adku.

8. Pokaż, że jeśli R jest relacj _{}a cz_{}eściowego porz _{}adku, to jest ni _{}a również relacja R^{−1}.

9. Która z liczb b_{}edzie pi_{}ećdziesi _{}ata w relacji uporz _{}adkowania leksykograficznego liczb

od 1 do 100 według zapisu

• literowego po polsku (liczby zapisujemy tak: jeden, dwa, trzy. … Oczywiście tutaj np. dwa<jeden<trzy)?

• cyfrowego w układzie dziesi_{}etnym. (Uwaga: tu np. 11 < 2)?

• rzymskiego?

10. Uogólnij definicje porz _{}adków kartezjańskiego i biegunowego na przypadek trójwymiarowy.

11. Czy relacja ≤_{K} ∩ ≤_{B} jest relacj _{}a • porz _{}adku cz_{}eściowego

• porz _{}adku liniowego?

12. Czy relacja ≤_{K} ∪ ≤_{B} jest relacj _{}a • porz _{}adku cz_{}eściowego

• porz _{}adku liniowego?