Kartézský součin, relace
Doc. Dr. Vladimír Homola, Ph.D.
Kartézský součin
Definice: Kartézský součin množin A, B (značení: A ´ B) je množina všech uspořádaných dvojic takových, že první prvek dvojice je prvkem A a druhý prvek dvojice prvkem B:
A ´ B = { [a,b] ˝ a Î A Ů b Î B }
Obdobně kartézský součin množin A, B, C (značení: A ´ B ´ C) je množina všech uspořádaných trojic:
A ´ B ´ C = { [a,b,c] ˝ a Î A Ů b Î B Ů c Î C }
atd. Je-li jedna z množin prázdná, je i kartézský součin prázdná množina.
Označení: Součin A ´ A označujeme také A2, M ´ M ´ M ´ M ´ M označujeme také M5 atd.
Jsou-li množiny A a B konečné s počty prvků nA a nB, je i jejich kartézský součin A ´ B konečná množina; počet jejich prvků (=počet uspořádaných dvojic) je roven nA ´ nB - dvojice obsahují kombinace “každý z A s každým z B”. Pro grafické zobrazení kartézského součinu se pro množiny s malým počtem prvků může použít tabulka; např. pro {červené, zelené, žluté} ´ {jablko, hruška}:
| jablko | hruška | |
| červené | červené jablko | červená hruška |
| zelené | zelené jablko | zelená hruška |
| žluté | žluté jablko | žlutá hruška |
I v některých případech nekonečných množin lze s výhodou kartézský součin znázornit graficky. Je-li např. A=<2,6> a B=<1,4> (uzavřené intervaly reálných čísel), pak znázornění A ´ B může být např. následující:
Relace
Definice: Binární relace R z množiny A do množiny B je libovolná podmnožina kartézského součinu A ´ B:
R Í A ´ B
Označení: Je-li [a,b] Î
R, píšeme: aRb a čteme: prvku a je v relaci R přiřazen
prvek b, nebo: prvek a je v relaci R s prvkem b.
Je-li naopak [a,b] Ď R, píšeme a
b
a čteme: prvek a není v relaci R s prvkem b.
Označení: Je-li R Í A ´ A, pak R nazýváme relací v množině A.
Příklad: V množině A = {3, 5, 7, 9} je
dána relace R = { [3,5], [3,7], [3,9], [5,7], [5,9], [7,9] }. Je
tedy např. 3R7, 7R9, ale 93.
Jsou-li množiny A a B konečné, lze pro znázornění relací použít několika způsobů. Nejčastěji používané jsou dva: maticový a tabulkový. Maticovým zápisem relace R z předchozího příkladu je následující matice 4x4 (nad matici resp. před matici byly pro přehlednost přidány nadpisy sloupců resp. řádků); v ní hodnota 0 značí, že prvky v relaci nejsou, hodnota 1 značí, že prvky v relaci jsou:
| (aŻ) R (b®) | 3 | 5 | 7 | 9 |
| 3 | 0 | 1 | 1 | 1 |
| 5 | 0 | 0 | 1 | 1 |
| 7 | 0 | 0 | 0 | 1 |
| 9 | 0 | 0 | 0 | 0 |
Tabulkovým zápisem relace R z předchozího příkladu je následující tabulka:
| a Î A | b Î B |
| 3 | 5 |
| 3 | 7 |
| 3 | 9 |
| 5 | 7 |
| 5 | 9 |
| 7 | 9 |
Definice: n-ární relace je libovolná podmnožina R kartézského součinu A1 ´ A2 ´ ... ´ An.
Maticové zobrazení n-árních relací pro větší n je velmi nepraktické a nepřehledné. Proto se relace s konečným (často i značným) počtem prvků zobrazují výhradně jako n-sloupcové tabulky - pokud se samozřejmě nedají vyjádřit jinak, např. symboly výrokového počtu apod.
Definice: V následující tabulce jsou definovány některé základní typy relací podle svých vlastností; relace R je vždy v těchto případech relací v množině A:
| Relace R je ... | ... právě když platí: |
| reflexivní | " x Î A : xRx |
| symetrická | " x,y Î A : xRy ® yRx |
| tranzitivní | " x,y,z Î A : xRy Ů yRz ® xRz |
| areflexivní | " x,y Î A : xRy ® x ą y |
| antisymetrická | " x,y Î A : xRy Ů yRx ® x=y |
| ekvivalence | R je reflexivní, symetrická, tranzitivní |
| (neostré) uspořádání | R je reflexivní, antisymetrická, tranzitivní |
| ostré uspořádání | R je areflexivní, tranzitivní |
Příklad: Nechť je dána relace - viz příklad shora. Tato relace je areflexivní (pro všechna [x,y] Î R je x ą y) a tranzitivní (3R5 Ů 5R7 ® 3R7; 3R7 Ů 7R9 ® 3R9; 5R7 Ů 7R9 ® 5R9). Relace je tedy ostré uspořádání; tato relace se často místo obecného R značí “<”. Je tedy 3<5, 3<7, 3<9, 5<7, 5<9, 7<9.
Relační databáze
Na shora zavedeném pojmu relace jsou konstruovány tzv. relační databáze. Nechť například množiny D, C a N značí po řadě množinu všech datumů, množinu všech řetězců (řetězec = posloupnost jednoho nebo více písmen, cifer a jiných znaků) a množinu všech racionálních čísel. Mějme relaci R definovanou jako podmnožinu kartézského součinu K = D ´ N ´ C ´ C. Množina K je (nekonečná) množina všech uspořádaných čtveřic, kde první prvek čtveřice je datum, druhý racionální číslo, třetí je řetěz a čtvrtý je rovněž řetěz. Množinu R vytvořme tak, že vybereme jen některé čtveřice. Z hlediska praktického použití jakékoliv náhodná čtveřice, např.
[12/04/1543, 0, blabla, gaga],
asi nebude příliš zajímavá. Ovšem čtveřice
[01/01/1992, 9200, Novák, řidič]
už může vypovídat o jisté reálné situaci: prvního ledna 92 byl přijat Novák jako řidič s platem 9200 Kč. Tabulkový zápis relace R pak může vypadat např. takto:
| Datum Î D | Plat Î N | Jméno Î C | Profese Î C |
| 01/01/1992 | 9.200 | Novák | řidič |
| 15/06/1973 | 14.500 | Novotný | vedoucí |
| 01/11/1990 | 8.300 | Nováček | vrátný |
| ... | ... | ... | ... |
| 15/06/1978 | 17.800 | Bratka | analytik |
Rev. 10 / 2002