RELACE,
OPERACE
Relace Užití:
1. K popisu (evidenci) nějaké množiny objektů či jevů, které lze charakterizovat pomocí jejich vlastnostmi. Entita je popsána pomocí atributů. Ty se vybírají z domén. Různé entity se liší aspoň v jednom atributu. Viz relační databáze. Coodova algebra pro práci s relacemi. 2. K tomu, abychom formálně popsali vlastnosti předmětů dané množiny a vztahy mezi dvěma nebo více předměty dané množiny objektů či jevů (entit). Formálně: Relace s doménami A1, A2, ... , An ≡DEF každá podmnožina kartézského součinu A1 × A2 × ... × An. Jsou-li domény totožné nazývá se relace relací na množině A. n- ární relace na A ≡DEF podmnožina A × A × ... × A = An. Unární relace ...... Vlastnost Binární relace ..... Vztah dvou prvků Ternární relace .... Vztah tří prvků ... . Důležité vlastnosti binárních relací na množině, kterých je třeba si všímat:
Symetrická relace, právě když pro všechna a, b ∈ A platí vztah a R b ⇒ b R a. Pak ovšem můžeme také psát, že a R b ⇔ b R a. Reflexivní relace, právě když pro všechna a ∈ A platí vztah a R a. Transitivní relace, právě když pro všechna a, b, c ∈ A platí vztah (a R b ∧ b R c) ⇒ a R c. Tranzitivnost je nutný požadavek pro vyjádření preference pomocí binární relace.
Pro popření těchto vlastností se užívá přepon „ne“, „anti“ případně „a“, jejichž význam může být odlišný. Tak například u symetričnosti se těchto předpon obvykle užívá v tomto smyslu: Nesymetrická relace je relace, pro kterou existuje alespoň jedna dvojice prvků a, b ∈ A taková, že a R b, ale neplatí b R a. Tedy relace, která není symetrická. Antisymetrická relace je relace, pro kterou pro všechna a, b ∈ A platí, že pokud a R b a současně b R a, potom je a = b. Pojmy symetrická a antisymetrická relace nejsou navzájem opakem. Existuje řada relací, které nejsou ani symetrické, ani antisymetrické. Například na množině čísel {1,2,3} relace obsahující dvojice {(1,2) (2,1) (1,3)}). Přítomnost prvků (1,2) i (2,1) vylučuje antisymetričnost, přítomnost (1,3) a nepřítomost (3,1) vylučuje symetričnost relace. Existují dokonce i relace, které jsou zároveň symetrické i antisymetrické. Například relace obsahující dvojice {(1,1) (2,2) (3,3)}.
Asymetrická relace je pak relace pro všechna a, b ∈ A platí vztah a R b ⇒ ¬(b R a). Negativně transitivní relace je relace, pro kterou z neplatnosti vztahu a R b a neplatnosti vztahu b R c plyne neplatnost vztahu a R c (jinými slovy, pokud je x R y, potom pro libovolné z ∈ A je buď x R z, nebo z R y. Úplná relace, je relace, ve které pro libovolné dva prvky a, b ∈ A platí, že je buď a R b, nebo b R a. Slabě úplná relace, pokud pro každé dva různé prvky a, b ∈ A, a ≠ b, je buď a R b nebo b R a. Ekvivalence ≡DEF relace, která je symetrická, reflexivní a tranzitivní. Určuje, které prvky jsou z určitého hlediska záměnné. Ekvivalence definuje rozklad množiny na disjunktní podmnožiny vzájemně ekvivalentních prvků.
Ostré preference a % b. Popisují, že a dáváme (z jistého hlediska) přednost před b. V případě, že neplatí ani a % b ani b % a nevíme zda a a b jsou ekvivalentní nebo zda jsou neporovnatelné. Neostré preference a À b. Popisují, že a je z daného hlediska stejně dobré nebo lepší než b. Popíšeme-li situaci pomocí neostrých preferencí a À b lze neporovnatelné a ekvivalentní prvky odlišit takto: Pokud a À b a současně b À a jsou prvky a a b ekvivalentní, Pokud neplatí ani a À b ani b À a jsou prvky a , b neporovnatelné. Ostrou relaci preference % lze na základě neostré definovat vztahem % = À ¿. Ekvivalenci ≈ vztahem ≈ = À ∩ ¿. Proto je výhodnější užít pro popis preferencí neostré relace. Zvolímeli ostré relace je ekvivalenci nutné dodefinovat dodatečně. KVAZIUSPOŘÁDÁNÍ na množině A ≡DEF reflexivní a tranzitivní relace na A (může obsahovat jak různé ale ekvivalentní prvky, tak i prvky neporovnatelné). ČÁSTEČNÉ USPOŘÁDÁNÍ na množině A ≡DEF reflexivní tranzitivní a antisymetrická relace na A, tedy kvaziuspořádání, v kterém nemohou existovat dva různé, ale ekvivalentní prvky (neporovnatelné existovat mohou). SLABÉ USPOŘÁDÁNÍ na množině A ≡DEF reflexivní tranzitivní a úplná relace na A, tedy kvaziuspořádání, v kterém jsou libovolné dva prvky porovnatelné (mohou ale být ekvivalentní). USPOŘÁDÁNÍ na množině A ≡DEF reflexivní tranzitivní, antisymetrická a úplná relace na A, tedy relace, která je současně částečným i slabým uspořádáním (libovolné dva prvky jsou vždy porovnatelné a neexistují různé ale ekvivalentní prvky).
Tomu odpovídají typy ostrých preferencí: OSTRÉ ČÁSTEČNÉ USPOŘÁDÁNÍ ≡DEF tranzitivní a asymetrická relace (taková relace je samozřejmě reflexivní) OSTRÉ SLABÉ USPOŘÁDÁNÍ ≡DEF asymetrická a negativně tranzitivní relace (odtud lze odvodit, že je i tranzitivní) OSTRÉ USPOŘÁDÁNÍ ≡DEF asymetrická, tranzitivní a úplná relace. Jak zaznamenat relaci: Výčtem prvků (málo přehledné): {(orchidej, orchidej), (orchidej, růže), (orchidej, karafiát), (orchidej, tulipán), (orchidej, fialka), (orchidej, bodlák), (růže, růže), (růže, karafiát), (růže, tulipán), (růže, bodlál), (karafiát, karafiát), (karafiát, bodlák), (tulipán, tulipán), (tulipán, bodlák), (fialka, fialka), (fialka, bodlák), (bodlák, bodlák)}. Tabulkou (maticí): orchidej růže orchidej - o 1 růže -r 0 karafiát - k 0 tulipán - t 0 fialka - f 0 bodlák - b 0
karafiát 1 1 0 0 0 0
tulipán 1 1 1 1 0 0
Grafem relace
1 1 1 1 0 0
bodlák 1 0 0 0 1 0
Hasseho diagramem
o
o
r
r
f k
fialka
t
f k
b
Smyčky se obvykle vynechávají
t b
Jen pro tranzitivní relace!
1 1 1 1 1 1
Uspořádání a slabé uspořádání lze pro konečné množiny a nekonečné spočetné množiny (též pro některé, ale ne všechny nekonečné nespočetné množiny) vyjádřit jedinou „známkou“. a À b ⇔ zn(a) ≥ zn(b), či zn(a) ≤ zn(b). Uspořádání a slabé uspořádání je lineární. U kvaziuspořádání, které není slabým uspořádáním to nelze. Potřebujeme více „známek“.
Některé vztahy nelze plně popsat pomocí klasifikace: Kvaziuspořádání
Částečné uspořádání
Slabé uspořádání
Uspořádání
Například prahovou nerozlišitelnost. Vztah „je blízký tak, že nemůžeme odlišit“ totiž není tranzitivní (není ekvivalencí).
Operace Intuitivně: Operace = Předpis, který dvěma (nebo více) vstupním hodnotám (argumentům) z dané množiny přiřazuje jednoznačně výsledek. Binární operace na množině A ≡ Ternární relace R na A, která má vlastnost: Pokud (x, y, z) ∈ R a současně (x, y, v) ∈ R, potom z = v. Jinými slovy: Binární operace na A je zobrazení z množiny A × A do A. Množina A se nazývá nosič operace. Pro operace obvykle užíváme značky připomínající operace s čísly: třeba: +, ⋅, *, •, ⊕, ⊗, N, É … .
Obvykle užíváme tak zvanou „infixovou“ notaci: z = x ⊕ y místo (x, y, z) ∈⊕
Některé důležité vlastnosti binárních operací, kterých je vhodné si všímat: Binární operace s nosičem A se nazývá: Totální [total] (někdy též úplná [complete]), pokud pro libovolná a, b ∈ A existuje c ∈ A tak, že a ⊕ b = c. Totální operace tedy musí mít výsledek pro libovolnou dvojici argumentů. Asociativní [associative], pokud pro libovolná a, b, c ∈ A platí a ⊕ (b ⊕ c ) = (a ⊕ b) ⊕ c. Komutativní [commutative] , pokud pro libovolná a, b ∈ A platí a ⊕ b = b ⊕ a. S neutrálním prvkem [with neutral element] ε, pokud pro libovolné a ∈ A platí a ⊕ ε = ε ⊕ a = a. S inverzními prvky [with inverse element], pokud ke každému a ∈ A existuje a’ ∈ A takové, že platí a ⊕ a’ = ε, kde ε je neutrální prvek.
Množina s jednou nebo několika operacemi se nazývá
algebra. V matematice se vyšetřuje řada algeber. Příklad algeber s dvěma operacemi tvoří různé číselné obory: přirozená čísla, celá čísla, racionální čísla, reálná čísla, komplexní čísla s operacemi sčítání a násobení. Čím se tyto algebry liší? Přemýšlejte a hledejte rozdíly vzhledem k vlastnostem operací sčítání a násobení!
Dvě důležité algebry GRUPA: operací, která má všechny zmíněné vlastnosti s výjimkou komunikativnosti (je totální, asociativní s neutrálním prvkem a ke každému prvku existuje prvek inverzní) se nazývá grupa. Pokud v grupě platí i komutativní zákon, hovoříme o Abelově grupě. Grupy jsou příkladem struktur, které se v matematice vyskytují často. Příklady grup: Celá čísla, racionální čísla, reálná čísla i komplexní čísla tvoří Abelovu grupu vzhledem k operaci sčítání. Ne však vzhledem k operaci násobení (k nule neexistuje převrácená hodnota). Příklady grup: Permutace konečné množiny a euklidovské pohyby v rovině tvoří grupu vzhledem k operaci skládání. Tyto dvě grupy nejsou Abelovy.
SVAZ ≡DEF Množina s dvěma operacemi spojení ∨ a průsek ∧, pro které platí obdobná pravidla jako pro disjunkci a konjunkci logických hodnot nebo pro sjednocení a průnik množin. Tedy komutativní a asociativní zákon, zákony absorbce a ∨ (a ∧ b) = a, a ∧ (a ∨ b) = a a idempotence a ∨ a = a, a ∧ a = a. Příklady svazů: Booleovská algebra operace: OR a AND, Algebra všech podmnožin dané množin operace: ∪ a ∩. Svaz lze ekvivalentně popsat pomocí částečného uspořádání, pokud je splněna podmínka, že pro libovolné dva prvky existuje nejmenší, který je větší nebo roven než oba (infimum – odpovídá spojení) a největší, který je menší nebo roven oběma (infimum – průsek).
