Teorie množin
 V matematice je všechno množina
 I čísla jsou definována pomocí množin
 Informatika stojí na matematice
 Znalosti Teorie množin využijeme
 v databázových systémech
 v informačních systémech
 při navrhování algoritmů
 ...
 Čekají nás
 základní množinové operace
 kartézské součiny, relace
 zobrazení, operace
Teoretické základy informatiky. ZS 2008/09 1
Pojem množina
 Naivní teorie množin
 Množina je souhrn objektů
 Paradoxy naivní teorie množin
 Axiomatická teorie množin
 Množina je primitivní pojem
 Množiny, které by vedly ke sporu není možné
konstruovat
 Určení množiny
 Výčtem prvků: M = {1,2,3}
 Vlastností: M = {nN | n < 4}
Teoretické základy informatiky. ZS 2008/09 2
Příslušnost do množiny
 Intuitivně se držíme označení
,,množina" pro ,,souhrn objektů"
 Skutečnost, že a je prvkem
množiny A, značíme aA.
 Skutečnost, že a není prvkem
množiny A, značíme aA.
Teoretické základy informatiky. ZS 2008/09 3
Počet prvků množiny
 Též označovaný pojmem mohutnost nebo kardinalita
 Značíme |M|
 Např. pro M = {1, 2} je |M|=2
 Konečné množiny
 mají konečný počet prvků
 tedy |M|N
 Nekonečné množiny
 mají nekonečný počet prvků
 tedy |M|N
 Prázdná množina
 nemá žádný prvek
 značení  nebo {}
 NE {}
 Platí tedy, že ||=0
Teoretické základy informatiky. ZS 2008/09 4
Rovnost množin
 Def.: Dvě množiny jsou si rovny,
jestliže mají stejné prvky
 Značíme A = B
A = B  ((x)((xA)(xB)) 
(x)((xB)(xA))(
 Platí zřejmá implikace
(A = B)  (|A| = |B|)
Teoretické základy informatiky. ZS 2008/09 5
Příklady
 Určete počet prvků množin
 A = {a, b, c, d}
 B = {a, a, b, b}
 C = {a, {b, c}, d}
 D = {{a, b, c, d}}
 E = {, {a, b}, c}
 F = {, }
 G = {}
 Které z uvedených množin jsou si rovny?
Teoretické základy informatiky. ZS 2008/09 6
Podmnožina
 Def.: Řekneme, že množina A je podmnožinou
množiny B, právě tehdy, když každý prvek množiny A
je zároveň prvkem množiny B.
 Značíme A  B
 Platí tedy A  B  (x)((xA)  (xB))
 Pojem podmnožina připouští i rovnost množin
 Každá podmnožina je podmnožinou sebe sama
 A = B  A  B, čili A  A
 Prázdná množina je podmnožinou každé množiny
   A pro libovolnou množinu A
 Tedy speciálně i   
 ((A  B)  (B  A))  (A = B)
 ((A  B)  (B  C))  (A  C)
Teoretické základy informatiky. ZS 2008/09 7
Vlastní podmnožina
 Řekneme, že množina A je vlastní
podmnožinou množiny B právě tehdy,
když je její podmnožinou, ale AB
 Značíme A  B
 V množině B tedy existují prvky,
které nejsou prvky množiny A
 Platí:
 (A  B)  (A  B) (ale ne naopak!)
Teoretické základy informatiky. ZS 2008/09 8
Potenční množina
 Množinu všech podmnožin množiny A
nazveme potenční množinou množiny A
 Značíme P(A)
 Příklady
 P({1,2}) = {, {1}, {2}, {1,2}}
 P({a}) = {, {a}}
 P() = {}
 Otázka: Kolik prvků má potenční množina
n-prvkové množiny?
 Příklad: Určete P(P({d})) a P(P())
Teoretické základy informatiky. ZS 2008/09 9
Sjednocení množin
 Je množina prvků, které patří alespoň do jedné ze
sjednocovaných množin.
 Značíme AB
 A B = {x | (xA)  (xB)}
 Příklad
 A = {a, b, c, d}
 B = {a, c, e}
 A  B = {a, b, c, d, e}
 Vlastnosti sjednocení
 A  (A  B) pro libovolné množiny A, B
 (A  B) = (B  A)
 (A  ) = A
Teoretické základy informatiky. ZS 2008/09 10
Průnik množin
 Je množina prvků, které patří alespoň do obou množin
současně.
 Značíme A  B
 A  B = {x | (xA)  (xB)}
 Příklad
 A = {a, b, c, d}
 B = {a, c, e}
 AB = {a, c}
 Vlastnosti průniku
 (A  B)  A pro libovolné množiny A,B
 (A  B) = (B  A)
 (A  ) = 
 Množiny se nazývají disjunktní, jestliže mají prázdný
průnik
 tj. nemají žádný společný prvek
Teoretické základy informatiky. ZS 2008/09 11
Rozdíl množin
 Rozdíl množin A a B je množina prvků, které patří do
množiny A a nepatří do množiny B.
 Značíme A-B
 A ­ B = {x | (xA)  (xB)}
 Příklad
 A = {a, b, c, d}
 B = {a, c, e}
 A ­ B = {b, d}
 Vlastnosti rozdílu
 (A ­ B)  A pro libovolné množiny A, B
 (A ­ B) = (B ­ A)  (A = B)
 (A ­ ) = A
  ­ A = 
Teoretické základy informatiky. ZS 2008/09 12
Vlastnosti množinových operací
 Sjednocení a průnik je komutativní a asociativní
 A  B = B  A
 A  B = B  A
 A  (B  C) = (A  B)  C
 A  (B  C) = (A  B)  C
 Rozdíl není ani komutativní, ani asociativní
 Platí zákony idempotence
 A  A = A
 A  A = A
 Platí distributivní zákony
 A  (B  C) = (A  B)  (A  C)
 A  (B  C) = (A  B)  (A  C)
Teoretické základy informatiky. ZS 2008/09 13
Příklady
 Dokažte platnost distributivních
zákonů pomocí Venových diagramů i
pomocí formálního jazyka teorie
množin
 Dokažte, že platí
 A - (B  C) = (A - B)  (A - C)
 A - (B  C) = (A - B)  (A - C)
Teoretické základy informatiky. ZS 2008/09 14
Doplněk množiny v množině
 Nechť A a M jsou množiny takové, že A 
M. Doplňkem množiny A v množině M
nazveme množinu všech prvků, které jsou
prvky množiny M, ale nejsou prvky množiny
A.
 Značíme A'M
 Platí A'M = M ­ A
 O doplňku hovoříme tehdy, je-li množina A
podmnožinou nějakého univerza M . V
opačném případě hovoříme o rozdílu
Teoretické základy informatiky. ZS 2008/09 15
Vlastnosti doplňku (předp. A  M)
 Zákony jednotky
 A  M = M A  M = A
 A   = A A   = 
 Zákony negace
 A  A'M = M A  A'M = 
 M'M =  ' = M
 de Morganovy zákony
 (A  B)'M = A'M  B'M
 (A  B)'M = A'M  B'M
Teoretické základy informatiky. ZS 2008/09 16
Číselné množiny
 N ­ přirozená čísla: 1, 2, 3, ...
 Z ­ celá čísla: 0, 1, -1, 2, -2, ...
 Q ­ racionální čísla: desetinná čísla, která
lze vyjádřit ve tvaru zlomku celého a
přirozeného čísla
 R ­ reálná čísla: čísla, jež lze znázornit na
číselné ose
 C ­ komplexní čísla: uspořádané dvojice
reálných čísel
 Platí N  Z  Q  R  C
Teoretické základy informatiky. ZS 2008/09 17
Příklady
 Vypočtěte množinu C, jestliže víte, že
C = {B}  B, B = {A}  A a A = {}
 Zapište všechny podmnožiny množiny
A = {0, , -1, }, které jsou
současně podmnožinou množiny
 N
 Z
 Q
 R
Teoretické základy informatiky. ZS 2008/09 18
Příklady
 Rozhodněte, zda platí
   
   {}
   {{}}
 {}  {}
 {}  {{}}
   {}
 {}  {{}}
  = {}
Teoretické základy informatiky. ZS 2008/09 19
Uspořádaná dvojice
 Prvky množiny nejsou uspořádané
 Dvouprvková množina společně s
uspořádáním prvků se nazývá
uspořádaná dvojice
 Značí se (a, b)
 Neplést s {a, b}
 Důsledek uspořádání:
 {a, b} = {b, a}
 (a, b)  (b, a) pro ab
Teoretické základy informatiky. ZS 2008/09 20
Kartézský součin
 Jsou dány množiny A, B. Jejich
kartézským součinem A  B rozumíme
množinu
A  B = {(a,b)| aA, bB}
 Kartézský součin je tedy množina všech
uspořádaných dvojic takových, že první
prvek patří do první množiny a druhý prvek
patří do druhé množiny.
 Kartézský součin není komutativní
 Plyne z nerovnosti (a, b)  (b, a)
 (A  B = B  A)  (A = B  A =   B = )
Teoretické základy informatiky. ZS 2008/09 21
Vlastnosti kartézského součinu
 |A| = m, |B| = n, pak |AB| = m*n
 Distributivní zákony
 A  (B  C) = (A  B)  (A  C)
 A  (B  C) = (A  B)  (A  C)
 ...a stejně tak i kartézské násobení zprava
 Prázdná množina v kartézském součinu
 A   =  pro lib. množinu A
   A =  pro lib. množinu A
    = 
Teoretické základy informatiky. ZS 2008/09 22
Kartézský součin více množin
 Kartézská mocnina
 A1 = A
 An = An-1  A
 Kartézský součin více množin
 A1A2...An = {(a1, a2, ..., an)| aiAi
i{1, 2, ..., n}}
 Značení
 Zřejmě platí
Teoretické základy informatiky. ZS 2008/09 23
Binární relace
 (Binární) relací rozumíme libovolnou
podmnožinu kartézského součinu dvou
množin   A  B
 Pro prvky aA a bB takové, že (a,b)
budeme binární relaci zapisovat pomocí
označení ab
 Relace je množina, můžeme na ni tedy
aplikovat množinové operace
 Prázdná relace:   A  B
 Plná relace:  = A  B
Teoretické základy informatiky. ZS 2008/09 24
N-ární relace
 Připomenutí: Arita = počet operandů
 Řekneme, že  je n-ární relace
právě tehdy, když
 N-ární relace je tedy podmnožina
kartézského součinu n množin
 Speciální případ: unární relace   A
Teoretické základy informatiky. ZS 2008/09 25
Určení relace
 Výčtem prvků
 A = {0, 1, 2}, B = {a, b}
 r = {(0,a), (0,b), (1,b), (2,a)}
 Požadovanou vlastností (vztahem prvků)
 A = B = Z
 r = {(a,b)| a  b}
 Graficky pomocí spojnic prvků
ve Venových diagramech
 Graficky pomocí tabulky
a b
0 1 1
1 0 1
2 1 0
Teoretické základy informatiky. ZS 2008/09 26
Skládání relací
 Mějme   A  B a   B  C
 Definujeme složenou relaci   
(čteme  po ) takto:
   = {(a,c) | bB: (ab  bc)}
 Skládání relací je asociativní
 (  )   =   (  )
Teoretické základy informatiky. ZS 2008/09 27
Relace na množině
 Binární relace na množině je zvláštní
případ relace, kdy A = B (tedy   A  A)
 N-ární relace na množině   An
 Relace identita
 idA = {(a, a) | a  A}
 Vlastnosti identity a skládání zobrazení
   idA = 
 idB   = 
Teoretické základy informatiky. ZS 2008/09 28
Inverzní relace
 Nechť   A  B je relace.
Relaci -1  B  A nazveme inverzní relací k
relaci  právě tehdy, když pro aA, bB
platí, že (a,b)  (b,a)-1
 Inverzní relace tedy obsahuje právě opačné
uspořádané dvojice
 Platí tedy b-1a  ab
 Inverze složené relace
 (  )-1 = -1  -1
Teoretické základy informatiky. ZS 2008/09 29
Reflexivní relace
 Řekneme, že relace   A  A je reflexivní právě
tehdy, když (aA)(aa)
 Tedy když každý prvek množiny je v relaci sám
se sebou
 Tedy pokud idA  
 V tabulce relace jsou 1 na hlavní diagonále
 Příklady reflexivních relací
 =, , |
 Mít stejné jméno, mít stejnou barvu očí, ...
Teoretické základy informatiky. ZS 2008/09 30
Symetrická relace
 Řekneme, že relace   A  A je symetrická
právě tehdy, když (a,bA)(ab  ba)
 Ke každé uspořádané dvojici, která je v relaci, je
v relaci i dvojice opačná
 Tedy -1  
 Tabulka relace je symetrická podle hlavní
diagonály
 Příklady symetrických relací
 =, , dávat stejný zbytek po dělení 7
 být vlastním sourozencem, být příbuzný
Teoretické základy informatiky. ZS 2008/09 31
Antisymetrická realce
 Řekneme, že relace   A  A je antisymetrická
právě tehdy, když (a,bA)(ab  ba  a = b)
 Je-li spolu s danou dvojicí v relaci zároveň i
dvojice opačná, nutně se musí jednat o dvojice
stejných prvků
 Tedy -1  idA
 V tabulce relace jsou na polích symetrických
podle hlavní diagonály vždy různé hodnoty
 Příklady antisymetrických relací
 , , , | (na N)
Teoretické základy informatiky. ZS 2008/09 32
Tranzitivní relace
 Řekneme, že relace   A  A je tranzitivní
právě tehdy, když
(a,b,cA)((ab  bc)  ac)
 Jsou-li v relaci prvek a s prvkem b a prvek b s
prvkem c, pak musí být v relaci i prvek a s
prvkem c.
 Tedy     
 Tranzitivitu relace nelze na první pohled vyčíst
z tabulky
 Příklady tranzitivních relací
 , , , <, >, =, |
 mít stejné ...
Teoretické základy informatiky. ZS 2008/09 33
Asymetrická relace
 Řekneme, že relace   A  A je asymetrická
právě tehdy, když (a,bA)(ab  ba)
 Situace, že by s některou uspořádanou dvojicí
byla v relaci i dvojice opačná, nenastává nikdy.
 Tedy ani u dvojic, v nichž je některý prvek sám se
sebou.
 Tedy   -1 = 
 V tabulce jsou na polích symetrických podle
hlavní diagonály opačné hodnoty a na hlavní
diagonále jsou nuly
 Příklady asymetrických relací
 <, >, 
 být matkou, být otcem, ...
Teoretické základy informatiky. ZS 2008/09 34
Relace úplná
 Řekneme, že relace   A  A je úplná právě
tehdy, když
(aA, bA) (ab  ba)
 Tedy každé dva prvky lze uspořádat do takové
dvojice, která je prvkem relace
 Úplná relace je zřejmě reflexivní
 Pro každou dvojici polí symetrických podle hlavní
diagonály platí, že alespoň na jednom z nich je 1
 Příklady úplných relací:
 
 být vyšší, být starší, ...
Teoretické základy informatiky. ZS 2008/09 35
Relace ekvivalence
 Relaci  nazveme relací ekvivalence právě
tehdy, když je zároveň reflexivní, symetrická,
tranzitivní
 Ekvivalence je jistým zobecněním rovnosti
 Příklady relace ekvivalence
 =, dávat po dělení n stejný zbytek
 mít nějakou vlastnost stejnou
 Ekvivalence na množině jednoznačně definuje
rozklad na disjunktní podmnožiny, jejichž
sjednocením je celá množina
 V každé třídě rozkladu jsou prvky, které jsou
spolu v relaci
Teoretické základy informatiky. ZS 2008/09 36
Relace uspořádání
 Relaci  nazveme relací uspořádání právě
tehdy, když je zároveň reflexivní, antisymetrická
a tranzitivní.
 Uspořádání nazýváme úplné, jestliže pro
a,bA platí ab  ba
 Tedy jestliže lze každé dva prvky srovnat
 Kromě zmíněných tří vlastností musí být relace i
úplná
 Prvky úplně uspořádané množiny tvoří jeden
řetězec
 Příklady uspořádání
 Úplné uspořádání , 
 Neúplné uspořádání: | (na N)
Teoretické základy informatiky. ZS 2008/09 37
Zobrazení
 Def.: Jsou dány množiny A a B a relace  
A  B. Relaci  nazveme zobrazení právě
tehdy, když
(aA)(bB)(ab)
 Zobrazením tedy nazveme takovou relaci,
kde ke každému prvku z množiny A
existuje jediný prvek z množiny B, který je
s ním v relaci.
 Zobrazení mezi číselnými množinami
nazýváme funkce.
Teoretické základy informatiky. ZS 2008/09 38
Vzor, obraz
 Vzhledem k tomu, že ke každému prvku
aA je prvek bB určen jednoznačně, lze
namísto ab nebo (a,b) psát (a) = b
 Def.: Je dáno zobrazení f takové, že f(a) =
b.
 Prvek b nazýváme obraz prvku a
 Prvek a nazýváme vzor prvku b
 Pozn.: Definice zobrazení vyžaduje, aby
každý prvek množiny A měl jediný obraz.
Naopak to však neplatí, jeden prvek
množiny B může mít více vzorů.
Teoretické základy informatiky. ZS 2008/09 39
Definiční obor. Obor hodnot
 Def.: Je dáno zobrazení f  A  B . Množinu
A nazýváme definiční obor zobrazení f a
značíme jej D(f) nebo Dom(f)
 Def.: Je dáno zobrazení f  A  B. Množinu
H(f) = {bB | aA: f(a) = b} nazveme
obor hodnot zobrazení f.
 Namísto značení H(f) se někdy používá
Im(f).
 Obor hodnot zobrazení je tedy množina
takových prvků, které mají svůj vzor.
 Skutečnost, že f  A  B je zobrazení,
častěji zapisujeme jako f: A  B
Teoretické základy informatiky. ZS 2008/09 40
Poznámky k definici zobrazení
 Někdy se místo ,,existuje právě jeden" říká
,,existuje maximálně jeden"
 V množině A tak mohou existovat prvky,
které nemají svůj obraz v množině B
 Definiční obor zobrazení je pak
podmnožinou množiny A
 Rozlišujeme zobrazení ,,množiny A" a ,,z
množiny A"
 My se budeme držet uvedené definice, v níž
je definiční obor celá množina A
Teoretické základy informatiky. ZS 2008/09 41
Surjekce
 Def.: Je dáno zobrazení f: A  B. Jestliže
Im(f) = B, zobrazení f nazýváme
zobrazením na množinu, nebo též
surjekce.
 U surjektivního zobrazení je tedy oborem
hodnot celá množina B. každý prvek má
tedy svůj vzor v množině A.
 Formální zápis surjektivního zobrazení:
(bB)(aA)(f(a) = b)
Teoretické základy informatiky. ZS 2008/09 42
Injekce
 Def.: Je dáno zobrazení f: A  B. Toto
zobrazení nazveme injekce, nebo též
prosté zobrazení, jestliže
(a1,a2  A)(f(a1) = f(a2)  a1 = a2)
 Tedy pokud každé dva různé prvky mají
různé obrazy
 Připomeňme, že žádný prvek nemůže mít
dva různé obrazy (nebylo by to zobrazení),
definice zobrazení však nevylučovala
případ, kdy mají dva prvky stejný obraz.
Teoretické základy informatiky. ZS 2008/09 43
Bijekce
 Def.: Je dáno zobrazení f: A  B. Zobrazení
f nazveme bijekce právě tehdy, když je
zároveň injekce a surjekce
 Tedy když je zároveň na množinu a prosté.
 Bijekce se též nazývá párování 1:1
 Věta: Nechť A, B jsou množiny a f: A  B
je bijekce. Pak |A| = |B|.
 Existence bijekce tedy dokazuje stejnou
mohutnost množin
Teoretické základy informatiky. ZS 2008/09 44
Skládání zobrazení
 Def.: Jsou dány množiny A, B, C a
zobrazení f: A  B a g: B  C. Složeným
zobrazením gf nazveme složenou relaci
gf
 Pozn.: Je zřejmé, že relace vzniklá složením
dvou zobrazení je opět zobrazení.
 gf: A  C a platí, že gf(x) = g(f(x))
 Skládání zobrazení není komutativní
 Skládání zobrazení je asociativní
Teoretické základy informatiky. ZS 2008/09 45
Inverzní zobrazení
 Def.: Je dáno prosté zobrazení f: A  B.
Inverzním zobrazením k zobrazení f
nazveme zobrazení f-1: Im(f)  A takové,
že pro aA a bB platí, že f-1(b) = a 
f(a) = b.
 Požadavek prostosti zobrazení zaručuje, že
inverzní relace bude zobrazením.
 Zřejmě f-1(f(x)) = x
 Tedy f-1  f = id
Teoretické základy informatiky. ZS 2008/09 46
Inverze složeného zobrazení
 Věta.: Jsou dány množiny A, B, C a
zobrazení f: A  B a g: B  C. Pak
platí: (gf)-1 = f-1g-1
 Příklad: A = B = C = R
f(x) = 3x g(x) = x­8
 (gf)(x) = 3x-8, (gf)-1(x) = (x+8)/3
f-1(x) = x/3, g-1(x) = x+8
f-1g-1(x) = (x+8)/3
Teoretické základy informatiky. ZS 2008/09 47
Operace
 Nechť A je množina a n přirozené číslo.
Zobrazení An  A nazýváme n-ární operací
na množině A. Číslo n nazýváme arita
(četnost) operace.
 Pro n=0 hovoříme o nulární operaci
 výběr konstanty
 Pro n=1 hovoříme o unární operaci
 např logzx, x2, -x
 Pro n=2 hovoříme o binární operaci
 např x+y, x*y, ...
Teoretické základy informatiky. ZS 2008/09 48
Vztah relací, zobrazení a operací
 Operace je zobrazení. Zobrazení je
relace. Tudíž operace je relace.
 Binární operace sčítání je tedy ve
skutečnosti ternární relace obsahující
právě prvky typu (a, b, a+b)
 Unární operace mínus je ve
skutečnosti binární relace obsahující
právě prvky typu (x, -x)
Teoretické základy informatiky. ZS 2008/09 49
Vlastnosti operací
 Uzavřenost množiny vzhledem k operaci
 Výsledek operace náleží do dané množiny
 Plyne přímo z definice operace
 Např. množina N není uzavřená vzhledem k
operaci odčítání
 Řekneme, že operace @: A2A je
komutativní, právě tehdy, když (x,yA)
x@y = y@x.
 Řekneme, že operace @: A2A je
asociativní, právě tehdy, když (x,y,zA)
(x@y)@z = x@(y@z)
Teoretické základy informatiky. ZS 2008/09 50
Neutrální a inverzní prvek
 Je dána operace @ : A2A. Prvek eA nazýváme
neutrálním prvkem operace @ právě tehdy, když
(aA)(e@a=a@e=a)
 Například 0 je neutrální prvek vzhledem k +, 1 je
neutrální prvek vzhledem k *
 Je dána operace @ : A2A s neutrálním prvkem e.
Prvek qA nazýváme inverzním prvkem k prvku p
vzhledem k operaci @ právě tehdy, když
(p@q=q@p=e)
 Například -5 je inverzní (opačný) prvek k 5 vzhledem
k +, 1/3 je inverzní prvek k 3 vzhledem k *
Teoretické základy informatiky. ZS 2008/09 51
K zamyšlení...
 Na množině všech řetězců nad abecedou 
je dána operace zřetězení.
 Zdůvodněte, proč se jedná o operaci
 Rozhodněte, zda je operace zřetězení
komutativní
 Rozhodněte, zda je operace zřetězení
asociativní
 Nalezněte neutrální prvek
 Jak je to s inverzním prvkem?
Teoretické základy informatiky. ZS 2008/09 52
Shrnutí teorie množin
Pojem množina, podmnožina
 Množina je (v naivní teorii množin) souhrn objektů.
 Množinu lze zadat výčtem nebo danou vlastností
 Příslušnost prvku do množiny značíme 
 Dvě množiny jsou si rovny právě tehdy, když mají
stejné prvky
 Prázdná množina  nemá žádné prvky
 A  B  (x)((xA)  (xB))
 Prázdná množina je podmnožinou každé množiny
 Množina všech množin dané množiny se nazývá
potenční množina
 Počet prvků potenční množiny n-prvkové množiny je
2n
Teoretické základy informatiky. ZS 2008/09 54
Množinové operace
 A B = {x | (xA)  (xB)}
 A  B = {x | (xA)  (xB)}
 Sjednocení a průnik jsou komutativní a
asociativní
 A ­ B = {x | (xA)  (xB)}
 A'M = M ­ A (za předpokladu A  M)
 Platí distributivní zákony, idempotentní
zákony, deMorganovy zákony, zákony
jednotky a zákony negace
Teoretické základy informatiky. ZS 2008/09 55
Kartézský součin, relace
 A  B = {(a,b)| aA, bB}
 Platí distributivní zákony vzhledem ke
sjednocení a průniku
 Kartézská mocnina: A1 = A, An = An-1  A
 Kartézský součin více množin: A1A2...An
= {(a1, a2, ..., an)| aiAi i{1, 2, ..., n}}
 Jakoukoliv podmnožinu kartézského
součinu nazveme relací.
 Prázdná množina = prázdná relace
 Celý kartézský součin = plná relace
 Relace na množině:   A  A
Teoretické základy informatiky. ZS 2008/09 56
Vlastnosti relací
 Inverzní relace: (a,b)  (b,a)-1
 Složená relace:   A  B a   B  C,    = {(a,c) |
bB: (ab  bc)}
 Reflexivní relace: (aA)(aa)
 Symetrická relace: (a,bA)(ab  ba)
 Antisymetrická relace: (a,bA)(ab  ba  a = b)
 Tranzitivní relace: (a,b,cA)((ab  bc)  ac)
 Asymetrická relace: (a,bA)(ab  ba)
 Úplná relace: (a,bA) (ab  ba)
 Ekvivalence: reflexivní, symetrická, tranzitivní
 Uspořádání: reflexivní, antisymetrická, tranzitivní
Teoretické základy informatiky. ZS 2008/09 57