Sesje binarne

Sesja binarna jest specjalnym typem sesji z licznością dwa. Typowe relacje binarne obejmują mniej niż, równość, podzielność, większe niż itp.

Przykłady

Relacja binarna jest jedną z typowych i często spotykanych relacji. Posiada ona również kilka interesujących właściwości, które opiszemy poniżej.

Przykładem relacji binarnej może być relacja "ojciec-syn", para "pojazd - liczba kół" lub bardziej ogólna "obiekt - właściwość obiektu". Obiektem może być zwierzę, a właściwością liczba nóg, oczekiwana długość życia, liczba włosów na głowie itd.

Relację binarną R między zbiorami M₁ i M₂ można zdefiniować w następujący sposób: R ⊆ M₁ × M₂ Relacja binarna jest więc zbiorem par, gdzie zbiór ten jest podzbiorem iloczynu kartezjańskiego dwóch zbiorów, między którymi ustalamy relację. Tak więc relacja ojciec-syn może być relacją między zbiorami wszystkich ludzi, między zbiorami wszystkich ludzi w Europie lub w Pradze. Możemy ograniczyć zbiór w innym kierunku, możemy powiedzieć, że definiujemy relację między zbiorami wszystkich mężczyzn, a nie mężczyzn w ogóle.

Zwykle używamy specjalnej notacji dla relacji binarnych. Zamiast pisać [a, b] ∈ R, możemy napisać aRb. Na przykład, zamiast [3, 1] ∈ >, możemy napisać 1 > 3. Podobnie dla innych sesji. Tak więc napisanie aSb jest równoważne napisaniu [a, b] ∈ S.

Sesje odwrotne

Sesja odwrotna to sesja przeciwna do bieżącej sesji (Uwaga, nie mylić z sesją uzupełniającą). Co jest odwrotnością sesji mniejszej niż? Jeśli sesja less-than zawiera element [4, 7], tj. 4 < 7, to element inverse będzie odwrotnością: 7 > 4, odwrotnością [7, 4] w sesji inverse.

Jeśli mamy sesję R ⊆ M₁ × M₂, to konstruujemy sesję odwrotną R⁻¹ biorąc wszystkie elementy [a, b] ∈ R i wstawiając ich odwrotności do R⁻¹. Tak więc, jeśli sesja R zawiera element [a, b], to sesja R⁻¹ musi zawierać element [b, a]. Odwrotność jest również prawdą, jeśli R⁻¹ zawiera element [b, a], to sesja R musi zawierać element [a, b].

Jeśli mielibyśmy to zdefiniować, to sesja R⁻¹ jest odwrotnością R tylko wtedy, gdy ma to zastosowanie:

$$\forall a\in M_1,\forall b\in M_2:\quad [a, b]\in R \Leftrightarrow [b, a]\in R^{-1}$$

6 < 8 ma zastosowanie tylko wtedy, gdy 8 > 6. Podobnie dla innych par.

Składanie sesji

Sesje binarne możemy składać ze sobą. Miejmy dwie sesje, pierwsza, R, byłaby "byciem ojcem mojego syna", a druga, S, byłaby "byciem bratem mojej siostry". Tak więc sesja R zawiera pary [otec, syn], a druga sesja zawiera pary [bratr, sestra].

W tym momencie spróbujmy połączyć sesje. Otrzymamy nową sesję, nazwijmy ją $R \circ S$, a ta sesja zawiera element [a, c] tak samo jak [a, b] ∈ R i jednocześnie [b, c] ∈ S. Zauważ, że oba elementy zawierają b, raz na drugiej pozycji, a następnie na pierwszej pozycji pary. Jest to rodzaj elementu łączącego składanie.

Przykład: R = {[Tonda, Marek], [Petr, Jakub]} i S = {[Marek, Jana], [Marek, Lenka], [Jakub, Lucie]}. Tonda jest ojcem Marka, Peter jest ojcem Jamesa. Marek ma siostry Janę i Lenkę, a Jakub ma siostrę Łucję.

Teraz skompilujemy sesję: $R \circ S$. Szukamy takiej pary z R, która ma kogoś w miejsce syna, który jest wymieniony jako brat w sesji S. Na przykład te dwie pary: [Tonda, Marek] i [Marek, Jana]. Mark jest elementem łączącym, nie jest nam już potrzebny i tworzymy nową parę z pozostałych nazw: [Tonda, Jana] Sesja $R \circ S$ zawiera więc parę [Tonda, Jana]. Marek ma jeszcze jedną siostrę, Lenkę, i dodajemy ją do sesji złożonej: [Tonda, Lenka]. Na koniec pozostaje nam syn Jakub. Ma on siostrę Łucję. Mamy więc dwie pary: [Petr, Jakub] i [Jakub, Lucie]. Tworzy to kolejny element: [Petr, Lucie].

Wynikiem jest sesja: $R \circ S = {[Tonda, Jana], [Tonda, Lenka], [Petr, Lucie]}$. Jak moglibyśmy nazwać tę sesję? Prawdopodobnie "bycie ojcem dla swojej córki".

Jeszcze raz, cała definicja:

$$[a, c] \in (R \circ S) \Leftrightarrow \exists b\quad [a, b] \in R \wedge [b, c] \in S$$

Uwaga: czasami używana jest notacja odwrotna, tzn. dla tej samej definicji można użyć $S \circ R$ zamiast $R \circ S$.