« poprzedni punkt     następny punkt »


2.5. Relacje wieloargumentowe

Relacje dwu-członowe są podzbiorami produktu kartezjańskiego dwóch zbiorów. Relacje n-argumentowe są podzbiorami produktu kartezjańskiego n zbiorów. Przykładem produktu kartezjańskiego trzech elementów jest przestrzeń euklidesowa R3 (R ´ R ´ R), której elementami są trójki liczb rzeczywistych oznaczające np. punkty w przestrzeni trójwymiarowej.

Przykład 2.5.1

  1. Rozważmy zależność zachodzącą między trójkami osób a, b, c, polegającą na tym, że a jest matką, a b ojcem osoby c. Jeśli przez X oznaczymy zbiór interesujących nas osób, to opisana wyżej zależność jest trójargumentową relacją w zbiorze X.
  2. Niech S będzie zbiorem studentów pierwszego roku PJWSTK. W sesji egzaminacyjnej po pierwszym semestrze studenci zaliczają cztery przedmioty MAD, TAK, PR, BD. Oceny uzyskane przez każdego studenta na egzaminach mogą być przechowywane w postaci tabeli, w której każdy wiersz odpowiada jednemu studentowi, a kolumny 2-5 odpowiadają wynikom w nauce studenta, którego nazwisko znajduje się w pierwszej kolumnie. Zależność opisana w takiej tabelce (por. Rys. 2.5.1) jest pięcio członową relacją. Na przykład piątka (Anna_A, 5,5,5,5) należy do tej relacji.

Rys. 2.5.1 Tabelka relacji wieloargumentowej.

Niech X1, X2, ..., Xn będą dowolnymi zbiorami, a n liczbą naturalną. Przez produkt tych zbiorów rozumiemy zbiór X1 ´ X2 ´ ... ´ Xn składający się z uporządkowanych n-tek elementów postaci (x1, x2, ...,xn), gdzie xi Î Xi dla i = 1,2...,n. Dwie n-tki (x1, x2, ...,xn) i (y1, y2, ...,yn), są równe wtedy i tylko wtedy, gdy odpowiadające sobie pozycje są równe, tzn. xi = yi, dla i =1,...n.

Lemat 2.5.1

Jeśli zbiór Xi ma ki elementów, to produkt kartezjański X1 ´ X2 ´ ... ´ Xn ma k1 * k2 *... * kn elementów.

Nieformalnie, dla każdego wyboru elementu z pierwszego zbioru możemy wybrać dowolny układ elementów z pozostałych zbiorów. Pierwszy element możemy wybrać na k1 sposobów, zatem wynik musi być równy k1*(liczba możliwych układów (n-1) -elementowych ze zbiorów X2 ´ ... ´ Xn. Dowód lematu jest dość prosty ale wymaga rozumowania indukcyjnego, o którym będzie mowa w dalszej części wykładu (por. wykład V).

Definicja 2.5.1

Każdy podzbiór zbioru X1 ´ X2 ´ ... ´ Xn nazywamy n-argumentową (inaczej n-członową) relacją. Zbiór Xi nazywa się i-tą dziedziną relacji n-członowej.

Jeśli r jest relacją n członową w produkcie X1 ´ X2 ´ ... ´ Xn , to zamiast (x1, x2, ..., xn) Î r , piszemy często r(x1, x2, ..., xn).

Przykład 2.5.2

  1. Niech r będzie podzbiorem produktu N ´ N ´ N takim, że (x,y,z) Î r wttw x2 + y2 = z2. r jest relacją trójczłonową w N. Trójka (3,4,5) Î r, a trójka (1,2,3) Ï r.
  2. Niech w będzie wielomianem jednej zmiennej stopnia n o współczynnikach rzeczywistych w(x) = a0 +a1*x + a2*x2...+ an*xn. Zdefiniujemy relację r w zbiorze R wzorem (a0, a1, ..., an, x, y) Î r wttw w(x) = y. r jest relacją n+3 argumentową, która zachodzi między elementami (a0, a1, ..., an, a, y) tylko wtedy, gdy y jest wartością wielomianu jednej zmiennej o współczynnikach a0, a1, ..., an , wyliczona dla argumentu a.
  3. Niech r oznacza teraz relację trójczłonową określoną w produkcie R3 taką, że (x,y,z) Î r wttw x<y<z, tzn. relacja ta zachodzi między elementami trójki wttw środkowy element można oszacować z dołu przez x, a z góry przez z.

Pytanie 2.5.1: Z ilu co najwyżej par uporządkowanych może składać się relacja binarna określona w pewnym zbiorze 100 elementowym?


« poprzedni punkt     następny punkt »