Relacja (matematyka) - Gry

Relacja (matematyka)

Z Wikipedii

Skocz do: nawigacji, szukaj
 Ten artykuł wymaga dopracowania zgodnie z zaleceniami edycyjnymi.
Należy w nim poprawić: coś o relacjach między wieloma zbiorami, choćby to, że się ich nie rozpatruje :).
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się na stronie dyskusji tego artykułu w sekcji Dopracować
Po wyeliminowaniu wskazanych powyżej niedoskonałości prosimy usunąć szablon {{Dopracować}} z kodu tego artykułu.

Spis treści

Relacja – dowolny podzbiór iloczynu kartezjańskiego zbiorów. Intuicyjnie, oznacza pewien związek pomiędzy elementami tych zbiorów.

[edytuj] Intuicje

Językiem relacji można opisywać wiele zjawisk życia codziennego. Przyjrzyjmy się społeczności wszystkich Polaków P (relacja na jednym zbiorze) i wprowadźmy pewne zależności.

Niech S będzie relacją między dwoma członkami społeczności P (relacja dwuargumentowa) określoną następująco:

x jest w relacji S z y wtedy i tylko wtedy, gdy x posiada samochód tej samej marki co y.

Relacja S jest:

  • zwrotna, ponieważ osoba x ma samochód tej samej marki co ona sama,
  • symetryczna, gdyż jeśli x ma samochód tej samej marki co y, to oczywiście y ma samochód tej samej marki co x.

Relacja ta pozwala wyróżnić w społeczności grupy osób (podzbiory): posiadaczy Roverów, Fiatów, Syren, itp. Grupy te nie muszą być rozłączne, ta sama osoba może posiadać kilka samochodów różnych marek i wówczas należy do kilku odpowiednich grup. Pozostaje ona wówczas w relacji S z osobami, które mogą nie być ze sobą w relacji S, a więc relacja nie jest przechodnia.

Gdyby jednak każdy członek społeczności posiadał samochody co najwyżej jednej marki, to relacja S byłaby przechodnia i wobec tego byłaby relacją równoważności, czyli wprowadzałaby podział społeczności P ze względu na markę samochodu (podzieliłaby ją na tzw. klasy abstrakcji).

Wprowadźmy inną relację na P:

osoba x jest w relacji F (relacja jednoargumentowa), jeśli posiada Ferrari.

Relacja ta wyróżnia podzbiór Polaków będących posiadaczami Ferrari.

Rozważmy zbiór kobiet X oraz mężczyzn Y będących członkami społeczności P (podział ten można otrzymać dzięki zastosowaniu odpowiedniej relacji równoważności) oraz zbiór M wszystkich marek samochodów. W iloczynie kartezjańskim X \times Y \times M można wprowadzić relację (trójargumentową) T taką, że:

trójka (x,y,s) jest w relacji T wtedy i tylko wtedy, gdy x jest żoną y i małżeństwo to posiada Fiata.

Wówczas żadna samotna osoba będąca posiadaczem Fiata nie ma szans "dostać się" do relacji T, dopóki nie znajdzie drugiej "połówki", małżeństwo natomiast – dopóki nie wejdzie w posiadanie Fiata.

[edytuj] Definicja

Niech dane będą dowolne zbiory X_1, X_2, \dots, X_n. Relacją n-członową (n-argumentową, n-arną) nazywamy dowolny podzbiór ich iloczynu kartezjańskiego

\varrho \subseteq X_1 \times X_2 \times \dots \times X_n.

[edytuj] Relacje jednego zbioru

Szczególnym przypadkiem są relacje zawarte w n-tej potędze kartezjańskiej jednego zbioru X, czyli relacje typu \varrho \subseteq X \times X \times \dots \times X = X^n

Jeżeli przez \operatorname{Rel}_n(X) oznaczymy zbiór wszystkich relacji n-członowych w zbiorze X, to moc tego zbioru dana jest wzorem

|\operatorname{Rel}_n(X)| = 2^{|X|^n}

Nad takim relacjami skupimy się w dalszej części artykułu.

[edytuj] Relacje zeroargumentowe

Zobacz więcej w osobnych artykułach: funkcja pusta, działanie zeroargumentowe.

Pod względem formalnym interesujący jest przypadek tzw. relacji zeroargumentowych, które zawarte są w zbiorze:

X^0 = \{\varnothing\}

Istnieją tylko dwie takie relacje, to jest \varnothing oraz \{\varnothing\}. Są one użyteczne w rozważaniach teoretycznych, ale trudno je zrozumieć intuicyjnie.

[edytuj] Relacje jednoargumentowe

Zobacz więcej w osobnym artykule: działanie zeroargumentowe.

Częściej używanymi relacjami są relacje jednoargumentowe (jednoczłonowe, unarne), czyli podzbiory zbioru X. Zwykle rola takiej relacji sprowadza się do wskazania pewnego podzbioru lub elementu należącego do zbioru X.

[edytuj] Przykłady

W zbiorze liczb rzeczywistych \mathbb R relacjami jednoargumentowymi są:

[edytuj] Relacje dwuargumentowe

Zobacz więcej w osobnych artykułach: funkcja (matematyka), działanie jednoargumentowe.

W praktyce najpopularniejsze i najszerzej stosowane są relacje dwuargumentowe (dwuczłonowe, binarne), zwykle nazywane po prostu relacjami.

Relacje te są zbiorami par uporządkowanych elementów postaci (x, y) \in X \times X. Zgodnie z tradycją zamiast (x, y) \in \varrho pisze się zazwyczaj x\; \varrho\; y i czyta „x \mbox{ jest w relacji } \varrho \mbox{ z } y”.

Zbiór wszystkich tych elementów X, które występują jako poprzedniki w parach należących do pewnej relacji (tzn. występują na pierwszych miejscach w parach) nazywamy dziedziną , a zbiór następników (elementów na drugim miejscu) – obrazem tej relacji.

[edytuj] Przykłady

Typowymi przykładami relacji binarnych są:

  • relacja pusta równa zbiorowi pustemu,
  • relacja pełna, równa X \times X oraz
  • przekątna, czyli zbiór par \{(x, x): x \in X\}.

W zbiorze liczb rzeczywistych \mathbb R:

W zbiorze liczb naturalnych \mathbb N:

  • relacja podzielności, tj. zbiór wszystkich par liczb naturalnych (m,n) takich, że n = km dla pewnej liczby naturalnej k. Para (m,n) jest elementem tej relacji wtedy i tylko wtedy, gdy liczba m dzieli liczbę n. Dlatego
    • (2,4) jest elementem relacji podzielności,
    • (2,5) nie należy do tej relacji.

[edytuj] Zobacz też

[edytuj] Ważniejsze relacje

własności

porządki

rodzaje






Wielka premiera muzyczna na MySpace
Powstająca od 15 lat płyta Chinese Democracy legendarnego zespołu Guns N’ Roses ma swoją premierę na portalu MySpace na kilka dni przed debiutem w sklepach.
Wodoodporna zwijana klawiatura
Dla wszystkich, którym zdarzyło się kiedyś wylać lub wysypać coś na klawiaturę komputera, Apollo przygotowało wodoodporną i pyłoodporną klawiaturę AK-500.
Bambusowy notebook!
Wielbiciele produktów inspirowanych cudami natury z pewnością nie przejdą obojętnie obok tego notebooka. ASUS Bamboo, jak sama nazwa sugeruje, posiada bambusową obudowę.
Koniec zamieszania z ceną Nokii
Telefon komórkowy z dotykowym wyświetlaczem - Nokia 5800 "Tube" - kosztuje jednak 280 euro, a nie 150 euro więcej, o czym mogliśmy przeczytać na hiszpańskiej witrynie firmy.
Król strzelanek obchodzi swoje dziesięciolecie
Dziś dzień jubileuszów. Oprócz dwóch rocznic związanych z Microsoftem, świętujemy też dziesięciolecie jednego z królów gier akcji: Half-Life'a.
Roslin swiat cianki dziaowe wentylacja BHP odchudzanie gry logiczne Katalog Stron 29284 master remont aktorzy warszawa