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 = {nN | 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 aA.
 Skutečnost, že a není prvkem
množiny A, značíme aA.
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)((xA)(xB)) 
(x)((xB)(xA))(
 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)((xA)  (xB))
 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 A≠B
 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 AB
 A B = {x | (xA)  (xB)}
 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 | (xA)  (xB)}
 Příklad
 A = {a, b, c, d}
 B = {a, c, e}
 AB = {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 | (xA)  (xB)}
 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 a≠b
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)| aA, bB}
 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 |AB| = 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
 A1A2…An = {(a1, a2, …, an)| aiAi
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 aA a bB takové, že (a,b)
budeme binární relaci zapisovat pomocí
označení ab
 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) | bB: (ab  bc)}
 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 aA, bB
platí, že (a,b)  (b,a)-1
 Inverzní relace tedy obsahuje právě opačné
uspořádané dvojice
 Platí tedy b-1a  ab
 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ž (aA)(aa)
 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,bA)(ab  ba)
 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,bA)(ab  ba  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,cA)((ab  bc)  ac)
 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,bA)(ab  ba)
 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ž
(aA, bA) (ab  ba)
 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,bA platí ab  ba
 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ž
(aA)(bB)(ab)
 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
aA je prvek bB určen jednoznačně, lze
namísto ab 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) = {bB | aA: 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í:
(bB)(aA)(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 g◦f nazveme složenou relaci
g◦f
 Pozn.: Je zřejmé, že relace vzniklá složením
dvou zobrazení je opět zobrazení.
 g◦f: A  C a platí, že g◦f(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 aA a bB 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í: (g◦f)-1 = f-1◦g-1
 Příklad: A = B = C = R
f(x) = 3x g(x) = x–8
 (g◦f)(x) = 3x-8, (g◦f)-1(x) = (x+8)/3
f-1(x) = x/3, g-1(x) = x+8
f-1◦g-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 @: A2A je
komutativní, právě tehdy, když (x,yA)
x@y = y@x.
 Řekneme, že operace @: A2A je
asociativní, právě tehdy, když (x,y,zA)
(x@y)@z = x@(y@z)
Teoretické základy informatiky. ZS 2008/09 50
Neutrální a inverzní prvek
 Je dána operace @ : A2A. Prvek eA nazýváme
neutrálním prvkem operace @ právě tehdy, když
(aA)(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 @ : A2A s neutrálním prvkem e.
Prvek qA 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)((xA)  (xB))
 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 | (xA)  (xB)}
 A  B = {x | (xA)  (xB)}
 Sjednocení a průnik jsou komutativní a
asociativní
 A – B = {x | (xA)  (xB)}
 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)| aA, bB}
 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: A1A2…An
= {(a1, a2, …, an)| aiAi 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) |
bB: (ab  bc)}
 Reflexivní relace: (aA)(aa)
 Symetrická relace: (a,bA)(ab  ba)
 Antisymetrická relace: (a,bA)(ab  ba  a = b)
 Tranzitivní relace: (a,b,cA)((ab  bc)  ac)
 Asymetrická relace: (a,bA)(ab  ba)
 Úplná relace: (a,bA) (ab  ba)
 Ekvivalence: reflexivní, symetrická, tranzitivní
 Uspořádání: reflexivní, antisymetrická, tranzitivní
Teoretické základy informatiky. ZS 2008/09 57