' $'
&
$
%Petr Hliněný, FI MU Brno 1 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3 Množiny, Relace a Funkce3 Množiny, Relace a Funkce
V přehledu matematických formalismů informatiky se v této lekci zaměříme na základní
,,datové typy matematiky, tj. na množiny, relace a funkce. O množinách jste sice
zajisté slyšeli už na základní škole, ale podstatou našeho předmětu je uvést povětšinou
neformálně známé pojmy na patřičnou formální úroveň nutnou pro teoretické základy
informatiky.
' $'
&
$
%Petr Hliněný, FI MU Brno 1 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3 Množiny, Relace a Funkce3 Množiny, Relace a Funkce
V přehledu matematických formalismů informatiky se v této lekci zaměříme na základní
,,datové typy matematiky, tj. na množiny, relace a funkce. O množinách jste sice
zajisté slyšeli už na základní škole, ale podstatou našeho předmětu je uvést povětšinou
neformálně známé pojmy na patřičnou formální úroveň nutnou pro teoretické základy
informatiky.
Stručný přehled lekce
* Uvedení množin a operací množinového kalkulu.
* Některé vlastnosti množin, princip inkluze a exkluze.
* Relace a definice funkcí, základní vlastnosti.
* Posloupnosti a rekurentní vztahy.
' $'
&
$
%Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.1 Pojem množiny3.1 Pojem množiny
* Co je vlastně množina?
' $'
&
$
%Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.1 Pojem množiny3.1 Pojem množiny
* Co je vlastně množina?
Na tuto otázku bohužel není zcela jednoduchá odpověď. . .
ˇ Naivní pohled: ,,Množina je soubor prvků a je svými prvky plně určena.
' $'
&
$
%Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.1 Pojem množiny3.1 Pojem množiny
* Co je vlastně množina?
Na tuto otázku bohužel není zcela jednoduchá odpověď. . .
ˇ Naivní pohled: ,,Množina je soubor prvků a je svými prvky plně určena.
ˇ Pozor, není skutečného rozdílu mezi ,,množinami a ,,prvky .
Množiny mohou být prvky jiných množin!
' $'
&
$
%Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.1 Pojem množiny3.1 Pojem množiny
* Co je vlastně množina?
Na tuto otázku bohužel není zcela jednoduchá odpověď. . .
ˇ Naivní pohled: ,,Množina je soubor prvků a je svými prvky plně určena.
ˇ Pozor, není skutečného rozdílu mezi ,,množinami a ,,prvky .
Množiny mohou být prvky jiných množin!
ˇ Příklady: , {a, b}, {b, a}, {a, b, a}, {{a, b}}, {, {}, {{}}},
{x | x je liché přirozené číslo}
' $'
&
$
%Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.1 Pojem množiny3.1 Pojem množiny
* Co je vlastně množina?
Na tuto otázku bohužel není zcela jednoduchá odpověď. . .
ˇ Naivní pohled: ,,Množina je soubor prvků a je svými prvky plně určena.
ˇ Pozor, není skutečného rozdílu mezi ,,množinami a ,,prvky .
Množiny mohou být prvky jiných množin!
ˇ Příklady: , {a, b}, {b, a}, {a, b, a}, {{a, b}}, {, {}, {{}}},
{x | x je liché přirozené číslo}
Značení: Počet prvků (mohutnost) množiny A zapisujeme |A|.
ˇ || = 0, |{}| = 1, |{a, b, c}| = 3, |{{a, b}, c}| = 2
' $'
&
$
%Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.1 Pojem množiny3.1 Pojem množiny
* Co je vlastně množina?
Na tuto otázku bohužel není zcela jednoduchá odpověď. . .
ˇ Naivní pohled: ,,Množina je soubor prvků a je svými prvky plně určena.
ˇ Pozor, není skutečného rozdílu mezi ,,množinami a ,,prvky .
Množiny mohou být prvky jiných množin!
ˇ Příklady: , {a, b}, {b, a}, {a, b, a}, {{a, b}}, {, {}, {{}}},
{x | x je liché přirozené číslo}
Značení: Počet prvků (mohutnost) množiny A zapisujeme |A|.
ˇ || = 0, |{}| = 1, |{a, b, c}| = 3, |{{a, b}, c}| = 2
Značení množin a jejich prvků:
ˇ x  M ,,x je prvkem množiny M .
' $'
&
$
%Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.1 Pojem množiny3.1 Pojem množiny
* Co je vlastně množina?
Na tuto otázku bohužel není zcela jednoduchá odpověď. . .
ˇ Naivní pohled: ,,Množina je soubor prvků a je svými prvky plně určena.
ˇ Pozor, není skutečného rozdílu mezi ,,množinami a ,,prvky .
Množiny mohou být prvky jiných množin!
ˇ Příklady: , {a, b}, {b, a}, {a, b, a}, {{a, b}}, {, {}, {{}}},
{x | x je liché přirozené číslo}
Značení: Počet prvků (mohutnost) množiny A zapisujeme |A|.
ˇ || = 0, |{}| = 1, |{a, b, c}| = 3, |{{a, b}, c}| = 2
Značení množin a jejich prvků:
ˇ x  M ,,x je prvkem množiny M .
ˇ některé vlastnosti a  {a, b}, a  {{a, b}}, {a, b}  {{a, b}},
ˇ prázdná množina , a  ,   {},   ,
ˇ rovnost množin {a, b} = {b, a} = {a, b, a}, {a, b} = {{a, b}}.
' $'
&
$
%Petr Hliněný, FI MU Brno 3 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Definice: Množina A je podmnožinou množiny B, právě když každý prvek A
je prvkem B. Píšeme A  B nebo také B  A; říkáme také, že se jedná o
inkluzi.
' $'
&
$
%Petr Hliněný, FI MU Brno 3 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Definice: Množina A je podmnožinou množiny B, právě když každý prvek A
je prvkem B. Píšeme A  B nebo také B  A; říkáme také, že se jedná o
inkluzi.
ˇ Platí {a}  {a}  {a, b}  {{a, b}},   {},
ˇ A  B právě když A  B a A = B (A je vlastní podmnožinou B).
' $'
&
$
%Petr Hliněný, FI MU Brno 3 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Definice: Množina A je podmnožinou množiny B, právě když každý prvek A
je prvkem B. Píšeme A  B nebo také B  A; říkáme také, že se jedná o
inkluzi.
ˇ Platí {a}  {a}  {a, b}  {{a, b}},   {},
ˇ A  B právě když A  B a A = B (A je vlastní podmnožinou B).
Definice: Dvě množiny jsou si rovny A = B právě když A  B a B  A.
ˇ Podle definice jsou množiny A a B stejné, mají-li stejné prvky.
' $'
&
$
%Petr Hliněný, FI MU Brno 3 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Definice: Množina A je podmnožinou množiny B, právě když každý prvek A
je prvkem B. Píšeme A  B nebo také B  A; říkáme také, že se jedná o
inkluzi.
ˇ Platí {a}  {a}  {a, b}  {{a, b}},   {},
ˇ A  B právě když A  B a A = B (A je vlastní podmnožinou B).
Definice: Dvě množiny jsou si rovny A = B právě když A  B a B  A.
ˇ Podle definice jsou množiny A a B stejné, mají-li stejné prvky.
ˇ Důkaz rovnosti množin A = B má obvykle dvě části:
Odděleně se dokáží inkluze A  B a B  A.
' $'
&
$
%Petr Hliněný, FI MU Brno 4 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Značení: Některé běžné množiny v matematice se značí
 N = {0, 1, 2, 3, . . .} je množina přirozených čísel,
 Z = {. . . , -2, -1, 0, 1, 2, 3, . . .} je množina celých čísel,
 Z+ = {1, 2, 3, . . .} je množina celých kladných čísel,
 Q je množina racionálních čísel (zlomků).
 R je množina reálných čísel.
' $'
&
$
%Petr Hliněný, FI MU Brno 4 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Značení: Některé běžné množiny v matematice se značí
 N = {0, 1, 2, 3, . . .} je množina přirozených čísel,
 Z = {. . . , -2, -1, 0, 1, 2, 3, . . .} je množina celých čísel,
 Z+ = {1, 2, 3, . . .} je množina celých kladných čísel,
 Q je množina racionálních čísel (zlomků).
 R je množina reálných čísel.
Poznámka: Tyto uvedené číselné množiny jsou vesměs nekonečné, na rozdíl od koneč-
ných množin uvažovaných v předchozím ,,naivním pohledu.
' $'
&
$
%Petr Hliněný, FI MU Brno 4 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Značení: Některé běžné množiny v matematice se značí
 N = {0, 1, 2, 3, . . .} je množina přirozených čísel,
 Z = {. . . , -2, -1, 0, 1, 2, 3, . . .} je množina celých čísel,
 Z+ = {1, 2, 3, . . .} je množina celých kladných čísel,
 Q je množina racionálních čísel (zlomků).
 R je množina reálných čísel.
Poznámka: Tyto uvedené číselné množiny jsou vesměs nekonečné, na rozdíl od koneč-
ných množin uvažovaných v předchozím ,,naivním pohledu.
Pojem nekonečné množiny se přímo v matematice objevil až teprve v 19. století a
bylo s ním spojeno několik paradoxů ukazujících, že naivní pohled na teorii množin pro
nekonečné množiny nedostačuje. My se k problematice nekonečných množin, Kantorově
větě a Russelově paradoxu vrátíme v závěru našeho předmětu.
' $'
&
$
%Petr Hliněný, FI MU Brno 5 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.2 Množinové operace3.2 Množinové operace
Definice: Sjednocení  a průnik  dvou množin A, B definujeme
A  B = {x | x  A nebo x  B}
' $'
&
$
%Petr Hliněný, FI MU Brno 5 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.2 Množinové operace3.2 Množinové operace
Definice: Sjednocení  a průnik  dvou množin A, B definujeme
A  B = {x | x  A nebo x  B} ,
A  B = {x | x  A a současně x  B} .
' $'
&
$
%Petr Hliněný, FI MU Brno 5 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.2 Množinové operace3.2 Množinové operace
Definice: Sjednocení  a průnik  dvou množin A, B definujeme
A  B = {x | x  A nebo x  B} ,
A  B = {x | x  A a současně x  B} .
ˇ Příklady {a, b, c}  {a, d} = {a, b, c, d}, {a, b, c}  {a, d} = {a}.
' $'
&
$
%Petr Hliněný, FI MU Brno 5 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.2 Množinové operace3.2 Množinové operace
Definice: Sjednocení  a průnik  dvou množin A, B definujeme
A  B = {x | x  A nebo x  B} ,
A  B = {x | x  A a současně x  B} .
ˇ Příklady {a, b, c}  {a, d} = {a, b, c, d}, {a, b, c}  {a, d} = {a}.
ˇ Vždy platí ,,distributivita A  (B  C) = (A  B)  (A  C)
a A  (B  C) = (A  B)  (A  C).
' $'
&
$
%Petr Hliněný, FI MU Brno 5 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.2 Množinové operace3.2 Množinové operace
Definice: Sjednocení  a průnik  dvou množin A, B definujeme
A  B = {x | x  A nebo x  B} ,
A  B = {x | x  A a současně x  B} .
ˇ Příklady {a, b, c}  {a, d} = {a, b, c, d}, {a, b, c}  {a, d} = {a}.
ˇ Vždy platí ,,distributivita A  (B  C) = (A  B)  (A  C)
a A  (B  C) = (A  B)  (A  C).
Definice: Pro libovolný počet množin indexovaných pomocí I rozšířeně
iI
Ai = {x | x  Ai pro nějaké i  I}
' $'
&
$
%Petr Hliněný, FI MU Brno 5 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.2 Množinové operace3.2 Množinové operace
Definice: Sjednocení  a průnik  dvou množin A, B definujeme
A  B = {x | x  A nebo x  B} ,
A  B = {x | x  A a současně x  B} .
ˇ Příklady {a, b, c}  {a, d} = {a, b, c, d}, {a, b, c}  {a, d} = {a}.
ˇ Vždy platí ,,distributivita A  (B  C) = (A  B)  (A  C)
a A  (B  C) = (A  B)  (A  C).
Definice: Pro libovolný počet množin indexovaných pomocí I rozšířeně
iI
Ai = {x | x  Ai pro nějaké i  I} ,
iI
Ai = {x | x  Ai pro každé i  I} .
' $'
&
$
%Petr Hliněný, FI MU Brno 5 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.2 Množinové operace3.2 Množinové operace
Definice: Sjednocení  a průnik  dvou množin A, B definujeme
A  B = {x | x  A nebo x  B} ,
A  B = {x | x  A a současně x  B} .
ˇ Příklady {a, b, c}  {a, d} = {a, b, c, d}, {a, b, c}  {a, d} = {a}.
ˇ Vždy platí ,,distributivita A  (B  C) = (A  B)  (A  C)
a A  (B  C) = (A  B)  (A  C).
Definice: Pro libovolný počet množin indexovaných pomocí I rozšířeně
iI
Ai = {x | x  Ai pro nějaké i  I} ,
iI
Ai = {x | x  Ai pro každé i  I} .
ˇ Nechť Ai = {2.i} pro každé i  N. Pak iN Ai je množina všech sudých
přirozených čísel.
' $'
&
$
%Petr Hliněný, FI MU Brno 5 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.2 Množinové operace3.2 Množinové operace
Definice: Sjednocení  a průnik  dvou množin A, B definujeme
A  B = {x | x  A nebo x  B} ,
A  B = {x | x  A a současně x  B} .
ˇ Příklady {a, b, c}  {a, d} = {a, b, c, d}, {a, b, c}  {a, d} = {a}.
ˇ Vždy platí ,,distributivita A  (B  C) = (A  B)  (A  C)
a A  (B  C) = (A  B)  (A  C).
Definice: Pro libovolný počet množin indexovaných pomocí I rozšířeně
iI
Ai = {x | x  Ai pro nějaké i  I} ,
iI
Ai = {x | x  Ai pro každé i  I} .
ˇ Nechť Ai = {2.i} pro každé i  N. Pak iN Ai je množina všech sudých
přirozených čísel.
ˇ Nechť Bi = {x | x  N,x  i} pro každé i  N. Pak iN Bi = .
' $'
&
$
%Petr Hliněný, FI MU Brno 6 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Definice: Rozdíl \ a symetrický rozdíl  dvou množin A, B definujeme
A \ B = {x | x  A a současně x  B}
' $'
&
$
%Petr Hliněný, FI MU Brno 6 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Definice: Rozdíl \ a symetrický rozdíl  dvou množin A, B definujeme
A \ B = {x | x  A a současně x  B} ,
AB = (A \ B)  (B \ A) .
' $'
&
$
%Petr Hliněný, FI MU Brno 6 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Definice: Rozdíl \ a symetrický rozdíl  dvou množin A, B definujeme
A \ B = {x | x  A a současně x  B} ,
AB = (A \ B)  (B \ A) .
ˇ Příklady {a, b, c} \ {a, b, d} = {c}, {a, b, c}{a, b, d} = {c, d}.
' $'
&
$
%Petr Hliněný, FI MU Brno 6 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Definice: Rozdíl \ a symetrický rozdíl  dvou množin A, B definujeme
A \ B = {x | x  A a současně x  B} ,
AB = (A \ B)  (B \ A) .
ˇ Příklady {a, b, c} \ {a, b, d} = {c}, {a, b, c}{a, b, d} = {c, d}.
ˇ Vždy platí například A \ (B  C) = (A \ B)  (A \ C) apod.
' $'
&
$
%Petr Hliněný, FI MU Brno 6 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Definice: Rozdíl \ a symetrický rozdíl  dvou množin A, B definujeme
A \ B = {x | x  A a současně x  B} ,
AB = (A \ B)  (B \ A) .
ˇ Příklady {a, b, c} \ {a, b, d} = {c}, {a, b, c}{a, b, d} = {c, d}.
ˇ Vždy platí například A \ (B  C) = (A \ B)  (A \ C) apod.
Definice: Nechť A  M. Doplněk A vzhledem k M je množina A = M \ A.
ˇ Jedná se o poněkud specifickou operaci, která musí být vztažena vzhledem
k nosné množině M !
' $'
&
$
%Petr Hliněný, FI MU Brno 6 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Definice: Rozdíl \ a symetrický rozdíl  dvou množin A, B definujeme
A \ B = {x | x  A a současně x  B} ,
AB = (A \ B)  (B \ A) .
ˇ Příklady {a, b, c} \ {a, b, d} = {c}, {a, b, c}{a, b, d} = {c, d}.
ˇ Vždy platí například A \ (B  C) = (A \ B)  (A \ C) apod.
Definice: Nechť A  M. Doplněk A vzhledem k M je množina A = M \ A.
ˇ Jedná se o poněkud specifickou operaci, která musí být vztažena vzhledem
k nosné množině M !
ˇ Je-li M = {a, b, c}, pak {a, b} = {c}. Je-li M = {a, b}, pak {a, b} = .
' $'
&
$
%Petr Hliněný, FI MU Brno 6 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Definice: Rozdíl \ a symetrický rozdíl  dvou množin A, B definujeme
A \ B = {x | x  A a současně x  B} ,
AB = (A \ B)  (B \ A) .
ˇ Příklady {a, b, c} \ {a, b, d} = {c}, {a, b, c}{a, b, d} = {c, d}.
ˇ Vždy platí například A \ (B  C) = (A \ B)  (A \ C) apod.
Definice: Nechť A  M. Doplněk A vzhledem k M je množina A = M \ A.
ˇ Jedná se o poněkud specifickou operaci, která musí být vztažena vzhledem
k nosné množině M !
ˇ Je-li M = {a, b, c}, pak {a, b} = {c}. Je-li M = {a, b}, pak {a, b} = .
ˇ Vždy pro A  M platí A = A (,,dvojí doplněk).
' $'
&
$
%Petr Hliněný, FI MU Brno 6 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Definice: Rozdíl \ a symetrický rozdíl  dvou množin A, B definujeme
A \ B = {x | x  A a současně x  B} ,
AB = (A \ B)  (B \ A) .
ˇ Příklady {a, b, c} \ {a, b, d} = {c}, {a, b, c}{a, b, d} = {c, d}.
ˇ Vždy platí například A \ (B  C) = (A \ B)  (A \ C) apod.
Definice: Nechť A  M. Doplněk A vzhledem k M je množina A = M \ A.
ˇ Jedná se o poněkud specifickou operaci, která musí být vztažena vzhledem
k nosné množině M !
ˇ Je-li M = {a, b, c}, pak {a, b} = {c}. Je-li M = {a, b}, pak {a, b} = .
ˇ Vždy pro A  M platí A = A (,,dvojí doplněk).
ˇ Vždy pro A, B  M platí A  B = A  B a A  B = A  B.
(Viz Vennovy diagramy.)
' $'
&
$
%Petr Hliněný, FI MU Brno 7 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Uspořádané dvojice a kartézský součin
Definice: Uspořádaná dvojice (a, b) je zadána množinou {{a}, {a, b}}.
' $'
&
$
%Petr Hliněný, FI MU Brno 7 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Uspořádané dvojice a kartézský součin
Definice: Uspořádaná dvojice (a, b) je zadána množinou {{a}, {a, b}}.
Fakt: Platí (a, b) = (c, d) právě když a = c a současně b = d.
' $'
&
$
%Petr Hliněný, FI MU Brno 7 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Uspořádané dvojice a kartézský součin
Definice: Uspořádaná dvojice (a, b) je zadána množinou {{a}, {a, b}}.
Fakt: Platí (a, b) = (c, d) právě když a = c a současně b = d.
Příklad 3.1. Co je podle definice (a, a)?
' $'
&
$
%Petr Hliněný, FI MU Brno 7 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Uspořádané dvojice a kartézský součin
Definice: Uspořádaná dvojice (a, b) je zadána množinou {{a}, {a, b}}.
Fakt: Platí (a, b) = (c, d) právě když a = c a současně b = d.
Příklad 3.1. Co je podle definice (a, a)?
(a, a) = {{a}, {a, a}} = {{a}, {a}} = {{a}}.
' $'
&
$
%Petr Hliněný, FI MU Brno 7 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Uspořádané dvojice a kartézský součin
Definice: Uspořádaná dvojice (a, b) je zadána množinou {{a}, {a, b}}.
Fakt: Platí (a, b) = (c, d) právě když a = c a současně b = d.
Příklad 3.1. Co je podle definice (a, a)?
(a, a) = {{a}, {a, a}} = {{a}, {a}} = {{a}}. 2
Definice 3.2. Kartézský součin dvou množin A, B definujeme jako
množinu všech uspořádaných dvojic ze složek z A a B
A × B = {(a, b) | a  A, b  B} .
' $'
&
$
%Petr Hliněný, FI MU Brno 7 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Uspořádané dvojice a kartézský součin
Definice: Uspořádaná dvojice (a, b) je zadána množinou {{a}, {a, b}}.
Fakt: Platí (a, b) = (c, d) právě když a = c a současně b = d.
Příklad 3.1. Co je podle definice (a, a)?
(a, a) = {{a}, {a, a}} = {{a}, {a}} = {{a}}. 2
Definice 3.2. Kartézský součin dvou množin A, B definujeme jako
množinu všech uspořádaných dvojic ze složek z A a B
A × B = {(a, b) | a  A, b  B} .
ˇ Příklady {a, b} × {a} = {(a, a), (b, a)}, {c} × {a, b} = {(c, a), (c, b)}.
' $'
&
$
%Petr Hliněný, FI MU Brno 7 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Uspořádané dvojice a kartézský součin
Definice: Uspořádaná dvojice (a, b) je zadána množinou {{a}, {a, b}}.
Fakt: Platí (a, b) = (c, d) právě když a = c a současně b = d.
Příklad 3.1. Co je podle definice (a, a)?
(a, a) = {{a}, {a, a}} = {{a}, {a}} = {{a}}. 2
Definice 3.2. Kartézský součin dvou množin A, B definujeme jako
množinu všech uspořádaných dvojic ze složek z A a B
A × B = {(a, b) | a  A, b  B} .
ˇ Příklady {a, b} × {a} = {(a, a), (b, a)}, {c} × {a, b} = {(c, a), (c, b)}.
ˇ Platí  × X =  pro každou množinu X.
' $'
&
$
%Petr Hliněný, FI MU Brno 7 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Uspořádané dvojice a kartézský součin
Definice: Uspořádaná dvojice (a, b) je zadána množinou {{a}, {a, b}}.
Fakt: Platí (a, b) = (c, d) právě když a = c a současně b = d.
Příklad 3.1. Co je podle definice (a, a)?
(a, a) = {{a}, {a, a}} = {{a}, {a}} = {{a}}. 2
Definice 3.2. Kartézský součin dvou množin A, B definujeme jako
množinu všech uspořádaných dvojic ze složek z A a B
A × B = {(a, b) | a  A, b  B} .
ˇ Příklady {a, b} × {a} = {(a, a), (b, a)}, {c} × {a, b} = {(c, a), (c, b)}.
ˇ Platí  × X =  pro každou množinu X.
ˇ Mnemotechnická pomůcka
|A × B| = |A|  |B| .
' $'
&
$
%Petr Hliněný, FI MU Brno 8 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Skládání součinu
Definice: Pro každé k  N,k > 0 definujeme uspořádanou k-tici (a1,    , ak)
induktivně takto
­ (a1) = a1,
­ (a1,    , ai, ai+1) = ((a1,    , ai), ai+1).
' $'
&
$
%Petr Hliněný, FI MU Brno 8 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Skládání součinu
Definice: Pro každé k  N,k > 0 definujeme uspořádanou k-tici (a1,    , ak)
induktivně takto
­ (a1) = a1,
­ (a1,    , ai, ai+1) = ((a1,    , ai), ai+1).
Fakt: Platí (a1,    , ak) = (b1,    , bk) právě když ai = bi pro každé 1  i  k.
' $'
&
$
%Petr Hliněný, FI MU Brno 8 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Skládání součinu
Definice: Pro každé k  N,k > 0 definujeme uspořádanou k-tici (a1,    , ak)
induktivně takto
­ (a1) = a1,
­ (a1,    , ai, ai+1) = ((a1,    , ai), ai+1).
Fakt: Platí (a1,    , ak) = (b1,    , bk) právě když ai = bi pro každé 1  i  k.
Definice kartézského součinu více množin: Pro každé k  N definujeme
A1 ×    × Ak = {(a1,    , ak) | ai  Ai pro každé 1  i  k} .
' $'
&
$
%Petr Hliněný, FI MU Brno 8 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Skládání součinu
Definice: Pro každé k  N,k > 0 definujeme uspořádanou k-tici (a1,    , ak)
induktivně takto
­ (a1) = a1,
­ (a1,    , ai, ai+1) = ((a1,    , ai), ai+1).
Fakt: Platí (a1,    , ak) = (b1,    , bk) právě když ai = bi pro každé 1  i  k.
Definice kartézského součinu více množin: Pro každé k  N definujeme
A1 ×    × Ak = {(a1,    , ak) | ai  Ai pro každé 1  i  k} .
ˇ Příklad Z3 = Z× Z× Z = {(i, j, k) | i, j, k  Z}.
ˇ Co je A0?
' $'
&
$
%Petr Hliněný, FI MU Brno 8 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Skládání součinu
Definice: Pro každé k  N,k > 0 definujeme uspořádanou k-tici (a1,    , ak)
induktivně takto
­ (a1) = a1,
­ (a1,    , ai, ai+1) = ((a1,    , ai), ai+1).
Fakt: Platí (a1,    , ak) = (b1,    , bk) právě když ai = bi pro každé 1  i  k.
Definice kartézského součinu více množin: Pro každé k  N definujeme
A1 ×    × Ak = {(a1,    , ak) | ai  Ai pro každé 1  i  k} .
ˇ Příklad Z3 = Z× Z× Z = {(i, j, k) | i, j, k  Z}.
ˇ Co je A0? {}, neboť jediná uspořádaná 0-tice je právě prázdná .
Poznámka: Podle uvedené definice není součin asociativní, tj. obecně nemusí platit,
že A × (B × C) = (A × B) × C.
' $'
&
$
%Petr Hliněný, FI MU Brno 8 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Skládání součinu
Definice: Pro každé k  N,k > 0 definujeme uspořádanou k-tici (a1,    , ak)
induktivně takto
­ (a1) = a1,
­ (a1,    , ai, ai+1) = ((a1,    , ai), ai+1).
Fakt: Platí (a1,    , ak) = (b1,    , bk) právě když ai = bi pro každé 1  i  k.
Definice kartézského součinu více množin: Pro každé k  N definujeme
A1 ×    × Ak = {(a1,    , ak) | ai  Ai pro každé 1  i  k} .
ˇ Příklad Z3 = Z× Z× Z = {(i, j, k) | i, j, k  Z}.
ˇ Co je A0? {}, neboť jediná uspořádaná 0-tice je právě prázdná .
Poznámka: Podle uvedené definice není součin asociativní, tj. obecně nemusí platit,
že A × (B × C) = (A × B) × C.
V matematické praxi je někdy výhodnější uvažovat ,,upravenou definici, podle níž sou-
čin asociativní je. Pro účely této přednášky není podstatné, k jaké definici se přikloníme.
Prezentované definice a věty ,,fungují pro obě varianty.
' $'
&
$
%Petr Hliněný, FI MU Brno 9 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Potenční množina
Definice 3.3. Potenční množina množiny A,
neboli množina všech podmnožin, je definovaná vztahem
2A
= {B | B  A} .
' $'
&
$
%Petr Hliněný, FI MU Brno 9 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Potenční množina
Definice 3.3. Potenční množina množiny A,
neboli množina všech podmnožin, je definovaná vztahem
2A
= {B | B  A} .
ˇ Platí například 2{a,b} = {, {a}, {b}, {a, b}},
ˇ 2 = {}, 2{,{}} = {, {}, {{}}, {, {}}},
ˇ 2{a}×{a,b} = {, {(a, a)}, {(a, b)}, {(a, a), (a, b)}}.
' $'
&
$
%Petr Hliněný, FI MU Brno 9 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Potenční množina
Definice 3.3. Potenční množina množiny A,
neboli množina všech podmnožin, je definovaná vztahem
2A
= {B | B  A} .
ˇ Platí například 2{a,b} = {, {a}, {b}, {a, b}},
ˇ 2 = {}, 2{,{}} = {, {}, {{}}, {, {}}},
ˇ 2{a}×{a,b} = {, {(a, a)}, {(a, b)}, {(a, a), (a, b)}}.
Věta 3.4. Počet prvků potenční množiny splňuje |2A| = 2|A|.
' $'
&
$
%Petr Hliněný, FI MU Brno 9 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Potenční množina
Definice 3.3. Potenční množina množiny A,
neboli množina všech podmnožin, je definovaná vztahem
2A
= {B | B  A} .
ˇ Platí například 2{a,b} = {, {a}, {b}, {a, b}},
ˇ 2 = {}, 2{,{}} = {, {}, {{}}, {, {}}},
ˇ 2{a}×{a,b} = {, {(a, a)}, {(a, b)}, {(a, a), (a, b)}}.
Věta 3.4. Počet prvků potenční množiny splňuje |2A| = 2|A|.
Důkaz: Stručně indukcí podle |A|: Pro A =  platí |2A| = |{}| = 1.
Pro každý další prvek b  A rozdělíme všechny podmnožiny A  {b} napolovic
na ty neobsahující b a na ty obsahující b, tudíž
|2A{b}
| = 2  |2A
| = 2|A|+1
.
2
' $'
&
$
%Petr Hliněný, FI MU Brno 10 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.3 Porovnávání a určení množin3.3 Porovnávání a určení množin
Věta 3.5. Pro každé dvě množiny A, B  M platí A  B = A  B.
' $'
&
$
%Petr Hliněný, FI MU Brno 10 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.3 Porovnávání a určení množin3.3 Porovnávání a určení množin
Věta 3.5. Pro každé dvě množiny A, B  M platí A  B = A  B.
Důkaz v obou směrech rovnosti.
ˇ A  B  A  B:
' $'
&
$
%Petr Hliněný, FI MU Brno 10 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.3 Porovnávání a určení množin3.3 Porovnávání a určení množin
Věta 3.5. Pro každé dvě množiny A, B  M platí A  B = A  B.
Důkaz v obou směrech rovnosti.
ˇ A  B  A  B:
 Pro x  M platí x  A  B, právě když x  A  B, neboli když zároveň
x  A a x  B.
 To znamená x  A a zároveň x  B, z čehož vyplývá požadované
x  A  B.
' $'
&
$
%Petr Hliněný, FI MU Brno 10 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.3 Porovnávání a určení množin3.3 Porovnávání a určení množin
Věta 3.5. Pro každé dvě množiny A, B  M platí A  B = A  B.
Důkaz v obou směrech rovnosti.
ˇ A  B  A  B:
 Pro x  M platí x  A  B, právě když x  A  B, neboli když zároveň
x  A a x  B.
 To znamená x  A a zároveň x  B, z čehož vyplývá požadované
x  A  B.
ˇ A  B  A  B:
 Pro x  M platí x  A  B, právě když x  A a zároveň x  B, neboli
když zároveň x  A a x  B.
' $'
&
$
%Petr Hliněný, FI MU Brno 10 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.3 Porovnávání a určení množin3.3 Porovnávání a určení množin
Věta 3.5. Pro každé dvě množiny A, B  M platí A  B = A  B.
Důkaz v obou směrech rovnosti.
ˇ A  B  A  B:
 Pro x  M platí x  A  B, právě když x  A  B, neboli když zároveň
x  A a x  B.
 To znamená x  A a zároveň x  B, z čehož vyplývá požadované
x  A  B.
ˇ A  B  A  B:
 Pro x  M platí x  A  B, právě když x  A a zároveň x  B, neboli
když zároveň x  A a x  B.
 To znamená x  A  B, z čehož vyplývá požadované x  A  B.
2
' $'
&
$
%Petr Hliněný, FI MU Brno 11 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Věta 3.6. Pro každé tři množiny A, B, C platí
A \ (B  C) = (A \ B)  (A \ C) .
' $'
&
$
%Petr Hliněný, FI MU Brno 11 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Věta 3.6. Pro každé tři množiny A, B, C platí
A \ (B  C) = (A \ B)  (A \ C) .
Důkaz.
ˇ A \ (B  C)  (A \ B)  (A \ C):
 Je-li x  A \ (B  C), pak x  A a zároveň x  (B  C),
neboli x  B nebo x  C.
 Pro první možnost máme x  (A \ B), pro druhou x  (A \ C).
' $'
&
$
%Petr Hliněný, FI MU Brno 11 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Věta 3.6. Pro každé tři množiny A, B, C platí
A \ (B  C) = (A \ B)  (A \ C) .
Důkaz.
ˇ A \ (B  C)  (A \ B)  (A \ C):
 Je-li x  A \ (B  C), pak x  A a zároveň x  (B  C),
neboli x  B nebo x  C.
 Pro první možnost máme x  (A \ B), pro druhou x  (A \ C).
ˇ Naopak A \ (B  C)  (A \ B)  (A \ C):
 Je-li x  (A \ B)  (A \ C), pak x  (A \ B) nebo x  (A \ C).
 Pro první možnost máme x  A a zároveň x  B,
z čehož plyne x  A a zároveň x  (B  C), a tudíž x  A \ (B  C).
' $'
&
$
%Petr Hliněný, FI MU Brno 11 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Věta 3.6. Pro každé tři množiny A, B, C platí
A \ (B  C) = (A \ B)  (A \ C) .
Důkaz.
ˇ A \ (B  C)  (A \ B)  (A \ C):
 Je-li x  A \ (B  C), pak x  A a zároveň x  (B  C),
neboli x  B nebo x  C.
 Pro první možnost máme x  (A \ B), pro druhou x  (A \ C).
ˇ Naopak A \ (B  C)  (A \ B)  (A \ C):
 Je-li x  (A \ B)  (A \ C), pak x  (A \ B) nebo x  (A \ C).
 Pro první možnost máme x  A a zároveň x  B,
z čehož plyne x  A a zároveň x  (B  C), a tudíž x  A \ (B  C).
 Druhá možnost je analogická.
2
' $'
&
$
%Petr Hliněný, FI MU Brno 12 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Charakteristický vektor (pod)množiny
V případech, kdy všechny uvažované množiny jsou podmnožinami nějaké nosné
množiny X, což není neobvyklé v programátorských aplikacích, s výhodou vy-
užijeme následující reprezentaci množin.
Definice: Mějme nosnou množinu X = {x1, x2, . . . , xn}. Pro A  X definu-
jeme charakteristický vektor A jako
A = (c1, c2, . . . , cn), kde ci = 1 pro xi  A a ci = 0 jinak.
' $'
&
$
%Petr Hliněný, FI MU Brno 12 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Charakteristický vektor (pod)množiny
V případech, kdy všechny uvažované množiny jsou podmnožinami nějaké nosné
množiny X, což není neobvyklé v programátorských aplikacích, s výhodou vy-
užijeme následující reprezentaci množin.
Definice: Mějme nosnou množinu X = {x1, x2, . . . , xn}. Pro A  X definu-
jeme charakteristický vektor A jako
A = (c1, c2, . . . , cn), kde ci = 1 pro xi  A a ci = 0 jinak.
ˇ Platí A = B právě když A = B.
ˇ Množinové operace jsou realizovány ,,bitovými funkcemi
sjednocení  OR, průnik  AND, symetrický rozdíl  XOR.
' $'
&
$
%Petr Hliněný, FI MU Brno 13 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Princip inkluze a exkluze
Tento důležitý a zajímavý kombinatorický princip je někdy také nazýván ,,princip
zapojení a vypojení .
A B
A B
C
Věta 3.7. Počet prvků ve sjednocení dvou či tří množin spočítáme:
|A  B| = |A| + |B| - |A  B|
|A  B  C| = |A| + |B| + |C| - |A  B| - |A  C| - |B  C| + |A  B  C|
' $'
&
$
%Petr Hliněný, FI MU Brno 13 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Princip inkluze a exkluze
Tento důležitý a zajímavý kombinatorický princip je někdy také nazýván ,,princip
zapojení a vypojení .
A B
A B
C
Věta 3.7. Počet prvků ve sjednocení dvou či tří množin spočítáme:
|A  B| = |A| + |B| - |A  B|
|A  B  C| = |A| + |B| + |C| - |A  B| - |A  C| - |B  C| + |A  B  C|
Všimněte si, že větu lze stejně tak využít k výpočtu počtu prvků v průniku množin. . .
' $'
&
$
%Petr Hliněný, FI MU Brno 14 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Příklad 3.8. Z 1000 televizí jich při první kontrole na výrobní lince má 5 vadnou
obrazovku, 10 je poškrábaných a 12 má jinou závadu. Přitom 3 televize mají
současně všechny tři vady a 4 jiné jsou poškrábané a mají jinou vadu.
Kolik televizí je celkem vadných?
' $'
&
$
%Petr Hliněný, FI MU Brno 14 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Příklad 3.8. Z 1000 televizí jich při první kontrole na výrobní lince má 5 vadnou
obrazovku, 10 je poškrábaných a 12 má jinou závadu. Přitom 3 televize mají
současně všechny tři vady a 4 jiné jsou poškrábané a mají jinou vadu.
Kolik televizí je celkem vadných?
Řešení: Dosazením do Věty 3.7 zjistíme výsledek 17.
' $'
&
$
%Petr Hliněný, FI MU Brno 14 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Příklad 3.8. Z 1000 televizí jich při první kontrole na výrobní lince má 5 vadnou
obrazovku, 10 je poškrábaných a 12 má jinou závadu. Přitom 3 televize mají
současně všechny tři vady a 4 jiné jsou poškrábané a mají jinou vadu.
Kolik televizí je celkem vadných?
Řešení: Dosazením do Věty 3.7 zjistíme výsledek 17. 2
Poznámka. Jen stručně, bez důkazu a bližšího vysvětlení, si uvedeme obecnou formu
principu inkluze a exkluze:
n
j=1
Aj =
=I{1,...,n}
(-1)|I|-1

iI
Ai
(Jeho znalost nebude v předmětu vyžadována.)
' $'
&
$
%Petr Hliněný, FI MU Brno 15 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.4 Relace a funkce mezi (nad) množinami3.4 Relace a funkce mezi (nad) množinami
Dalším důležitým základním ,,datovým typem matematiky jsou relace, kterým
vzhledem k jejich rozsáhlému použití v informatice věnujeme zvýšenou pozor-
nost.
Definice 3.9. Relace mezi množinami A1,    , Ak, pro k  N,
je libovolná podmnožina kartézského součinu
R  A1 ×    × Ak .
' $'
&
$
%Petr Hliněný, FI MU Brno 15 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.4 Relace a funkce mezi (nad) množinami3.4 Relace a funkce mezi (nad) množinami
Dalším důležitým základním ,,datovým typem matematiky jsou relace, kterým
vzhledem k jejich rozsáhlému použití v informatice věnujeme zvýšenou pozor-
nost.
Definice 3.9. Relace mezi množinami A1,    , Ak, pro k  N,
je libovolná podmnožina kartézského součinu
R  A1 ×    × Ak .
Pokud A1 =    = Ak = A, hovoříme o k-ární relaci R na A.
' $'
&
$
%Petr Hliněný, FI MU Brno 15 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.4 Relace a funkce mezi (nad) množinami3.4 Relace a funkce mezi (nad) množinami
Dalším důležitým základním ,,datovým typem matematiky jsou relace, kterým
vzhledem k jejich rozsáhlému použití v informatice věnujeme zvýšenou pozor-
nost.
Definice 3.9. Relace mezi množinami A1,    , Ak, pro k  N,
je libovolná podmnožina kartézského součinu
R  A1 ×    × Ak .
Pokud A1 =    = Ak = A, hovoříme o k-ární relaci R na A.
Příklady relací.
ˇ {(1, a), (2, a)} je relace mezi {1, 2, 3} a {a, b}.
ˇ {(i, 2.i) | i  N} je binární relace na N.
' $'
&
$
%Petr Hliněný, FI MU Brno 15 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.4 Relace a funkce mezi (nad) množinami3.4 Relace a funkce mezi (nad) množinami
Dalším důležitým základním ,,datovým typem matematiky jsou relace, kterým
vzhledem k jejich rozsáhlému použití v informatice věnujeme zvýšenou pozor-
nost.
Definice 3.9. Relace mezi množinami A1,    , Ak, pro k  N,
je libovolná podmnožina kartézského součinu
R  A1 ×    × Ak .
Pokud A1 =    = Ak = A, hovoříme o k-ární relaci R na A.
Příklady relací.
ˇ {(1, a), (2, a)} je relace mezi {1, 2, 3} a {a, b}.
ˇ {(i, 2.i) | i  N} je binární relace na N.
ˇ {(i, j, i + j) | i, j  N} je ternární relace na N.
ˇ {3.i | i  N} je unární relace na N.
' $'
&
$
%Petr Hliněný, FI MU Brno 15 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.4 Relace a funkce mezi (nad) množinami3.4 Relace a funkce mezi (nad) množinami
Dalším důležitým základním ,,datovým typem matematiky jsou relace, kterým
vzhledem k jejich rozsáhlému použití v informatice věnujeme zvýšenou pozor-
nost.
Definice 3.9. Relace mezi množinami A1,    , Ak, pro k  N,
je libovolná podmnožina kartézského součinu
R  A1 ×    × Ak .
Pokud A1 =    = Ak = A, hovoříme o k-ární relaci R na A.
Příklady relací.
ˇ {(1, a), (2, a)} je relace mezi {1, 2, 3} a {a, b}.
ˇ {(i, 2.i) | i  N} je binární relace na N.
ˇ {(i, j, i + j) | i, j  N} je ternární relace na N.
ˇ {3.i | i  N} je unární relace na N.
ˇ Jaký význam vlastně mají unární a nulární relace na A?
' $'
&
$
%Petr Hliněný, FI MU Brno 16 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Funkce mezi množinami
Definice 3.10. (Totální) funkce z množiny A do množiny B
je relace f mezi A a B taková, že pro každé x  A existuje právě jedno y  B
takové, že (x, y)  f.
' $'
&
$
%Petr Hliněný, FI MU Brno 16 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Funkce mezi množinami
Definice 3.10. (Totální) funkce z množiny A do množiny B
je relace f mezi A a B taková, že pro každé x  A existuje právě jedno y  B
takové, že (x, y)  f.
Množina A se nazývá definiční obor a množina B obor hodnot funkce f.
Neformálně řečeno, ve funkci f je každé ,,vstupní hodnotě x přiřazena jednoznačně
,,výstupní hodnota y.
(V obecné relaci počty ,,přiřazených dvojic neomezujeme. . . )
' $'
&
$
%Petr Hliněný, FI MU Brno 16 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Funkce mezi množinami
Definice 3.10. (Totální) funkce z množiny A do množiny B
je relace f mezi A a B taková, že pro každé x  A existuje právě jedno y  B
takové, že (x, y)  f.
Množina A se nazývá definiční obor a množina B obor hodnot funkce f.
Neformálně řečeno, ve funkci f je každé ,,vstupní hodnotě x přiřazena jednoznačně
,,výstupní hodnota y.
(V obecné relaci počty ,,přiřazených dvojic neomezujeme. . . )
Značení: Místo (x, y)  f píšeme obvykle f(x) = y.
Zápis f : A  B říká, že f je funkce s def. oborem A a oborem hodnot B.
' $'
&
$
%Petr Hliněný, FI MU Brno 16 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Funkce mezi množinami
Definice 3.10. (Totální) funkce z množiny A do množiny B
je relace f mezi A a B taková, že pro každé x  A existuje právě jedno y  B
takové, že (x, y)  f.
Množina A se nazývá definiční obor a množina B obor hodnot funkce f.
Neformálně řečeno, ve funkci f je každé ,,vstupní hodnotě x přiřazena jednoznačně
,,výstupní hodnota y.
(V obecné relaci počty ,,přiřazených dvojic neomezujeme. . . )
Značení: Místo (x, y)  f píšeme obvykle f(x) = y.
Zápis f : A  B říká, že f je funkce s def. oborem A a oborem hodnot B.
Funkcím se také říká zobrazení.
ˇ Definujeme funkci f : N  Npředpisem f(x) = x+8. Tj. f = {(x, x+8) |
x  N}.
' $'
&
$
%Petr Hliněný, FI MU Brno 16 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Funkce mezi množinami
Definice 3.10. (Totální) funkce z množiny A do množiny B
je relace f mezi A a B taková, že pro každé x  A existuje právě jedno y  B
takové, že (x, y)  f.
Množina A se nazývá definiční obor a množina B obor hodnot funkce f.
Neformálně řečeno, ve funkci f je každé ,,vstupní hodnotě x přiřazena jednoznačně
,,výstupní hodnota y.
(V obecné relaci počty ,,přiřazených dvojic neomezujeme. . . )
Značení: Místo (x, y)  f píšeme obvykle f(x) = y.
Zápis f : A  B říká, že f je funkce s def. oborem A a oborem hodnot B.
Funkcím se také říká zobrazení.
ˇ Definujeme funkci f : N  Npředpisem f(x) = x+8. Tj. f = {(x, x+8) |
x  N}.
ˇ Definujeme funkci plus : N × N  N předpisem plus(i, j) = i + j.
Tj. plus = {(i, j, i + j) | i, j  N}.
' $'
&
$
%Petr Hliněný, FI MU Brno 17 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Definice: Pokud naší definici funkce upravíme tak, že požadujeme pro každé
x  A nejvýše jedno y  B takové, že (x, y)  f, obdržíme definici parciální
funkce z A do B.
' $'
&
$
%Petr Hliněný, FI MU Brno 17 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Definice: Pokud naší definici funkce upravíme tak, že požadujeme pro každé
x  A nejvýše jedno y  B takové, že (x, y)  f, obdržíme definici parciální
funkce z A do B.
V parciální funkci p nemusí být pro některé ,,vstupní hodnoty x funkční hodnota
definována.
Pro nedefinovanou hodnotu používáme znak .
' $'
&
$
%Petr Hliněný, FI MU Brno 17 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Definice: Pokud naší definici funkce upravíme tak, že požadujeme pro každé
x  A nejvýše jedno y  B takové, že (x, y)  f, obdržíme definici parciální
funkce z A do B.
V parciální funkci p nemusí být pro některé ,,vstupní hodnoty x funkční hodnota
definována.
Pro nedefinovanou hodnotu používáme znak .
Další příklady funkcí.
ˇ Definujeme parciální funkci f : Z  N předpisem
f(x) =
3 + x jestliže x  0,
 jinak.
Tj. f = {(x, 3 + x) | x  N}.
' $'
&
$
%Petr Hliněný, FI MU Brno 17 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Definice: Pokud naší definici funkce upravíme tak, že požadujeme pro každé
x  A nejvýše jedno y  B takové, že (x, y)  f, obdržíme definici parciální
funkce z A do B.
V parciální funkci p nemusí být pro některé ,,vstupní hodnoty x funkční hodnota
definována.
Pro nedefinovanou hodnotu používáme znak .
Další příklady funkcí.
ˇ Definujeme parciální funkci f : Z  N předpisem
f(x) =
3 + x jestliže x  0,
 jinak.
Tj. f = {(x, 3 + x) | x  N}.
ˇ Také funkce f : R  R daná běžným analytickým předpisem
f(x) =

x
je jen parciální ­ není definována pro x < 0.
' $'
&
$
%Petr Hliněný, FI MU Brno 17 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Definice: Pokud naší definici funkce upravíme tak, že požadujeme pro každé
x  A nejvýše jedno y  B takové, že (x, y)  f, obdržíme definici parciální
funkce z A do B.
V parciální funkci p nemusí být pro některé ,,vstupní hodnoty x funkční hodnota
definována.
Pro nedefinovanou hodnotu používáme znak .
Další příklady funkcí.
ˇ Definujeme parciální funkci f : Z  N předpisem
f(x) =
3 + x jestliže x  0,
 jinak.
Tj. f = {(x, 3 + x) | x  N}.
ˇ Také funkce f : R  R daná běžným analytickým předpisem
f(x) =

x
je jen parciální ­ není definována pro x < 0.
ˇ Co je relace, přiřazující lidem v ČR jejich rodná čísla?
' $'
&
$
%Petr Hliněný, FI MU Brno 18 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.5 Posloupnosti a rekurentní vztahy3.5 Posloupnosti a rekurentní vztahy
Definice: Funkce p : N  R se nazývá posloupnost.
Mimo ,,funkčního zápisu p(n) často používáme ,,indexovou formu zápisu pn.
' $'
&
$
%Petr Hliněný, FI MU Brno 18 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.5 Posloupnosti a rekurentní vztahy3.5 Posloupnosti a rekurentní vztahy
Definice: Funkce p : N  R se nazývá posloupnost.
Mimo ,,funkčního zápisu p(n) často používáme ,,indexovou formu zápisu pn.
Poznámka: Obor hodnot posloupnosti může být i jiný než reálná čísla. Na posloup-
nost se také díváme jako na ,,seřazení vybraných prvků z oboru hodnot, s povoleným
opakováním hodnot (nemusí být prostá).
' $'
&
$
%Petr Hliněný, FI MU Brno 18 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.5 Posloupnosti a rekurentní vztahy3.5 Posloupnosti a rekurentní vztahy
Definice: Funkce p : N  R se nazývá posloupnost.
Mimo ,,funkčního zápisu p(n) často používáme ,,indexovou formu zápisu pn.
Poznámka: Obor hodnot posloupnosti může být i jiný než reálná čísla. Na posloup-
nost se také díváme jako na ,,seřazení vybraných prvků z oboru hodnot, s povoleným
opakováním hodnot (nemusí být prostá).
Také def. obor posl. může být od nuly nebo i od jedničky, jak je v aplikacích potřeba.
ˇ Příklady posloupností:
 p0 = 0, p1 = 2, . . . , pi = 2i, . . . je posloupnost sudých nezáporných čísel.
' $'
&
$
%Petr Hliněný, FI MU Brno 18 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.5 Posloupnosti a rekurentní vztahy3.5 Posloupnosti a rekurentní vztahy
Definice: Funkce p : N  R se nazývá posloupnost.
Mimo ,,funkčního zápisu p(n) často používáme ,,indexovou formu zápisu pn.
Poznámka: Obor hodnot posloupnosti může být i jiný než reálná čísla. Na posloup-
nost se také díváme jako na ,,seřazení vybraných prvků z oboru hodnot, s povoleným
opakováním hodnot (nemusí být prostá).
Také def. obor posl. může být od nuly nebo i od jedničky, jak je v aplikacích potřeba.
ˇ Příklady posloupností:
 p0 = 0, p1 = 2, . . . , pi = 2i, . . . je posloupnost sudých nezáporných čísel.
 3, 3.1, 3.14, 3.141, . . . je posloupnost postupných dekadických rozvojů .
 1, -1, 1, -1, . . . je posloupnost určená vztahem pi = (-1)i
, i  0.
' $'
&
$
%Petr Hliněný, FI MU Brno 18 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.5 Posloupnosti a rekurentní vztahy3.5 Posloupnosti a rekurentní vztahy
Definice: Funkce p : N  R se nazývá posloupnost.
Mimo ,,funkčního zápisu p(n) často používáme ,,indexovou formu zápisu pn.
Poznámka: Obor hodnot posloupnosti může být i jiný než reálná čísla. Na posloup-
nost se také díváme jako na ,,seřazení vybraných prvků z oboru hodnot, s povoleným
opakováním hodnot (nemusí být prostá).
Také def. obor posl. může být od nuly nebo i od jedničky, jak je v aplikacích potřeba.
ˇ Příklady posloupností:
 p0 = 0, p1 = 2, . . . , pi = 2i, . . . je posloupnost sudých nezáporných čísel.
 3, 3.1, 3.14, 3.141, . . . je posloupnost postupných dekadických rozvojů .
 1, -1, 1, -1, . . . je posloupnost určená vztahem pi = (-1)i
, i  0.
 Pokud chceme stejnou posloupnost 1, -1, 1, -1, . . . zadat jako qi, i  1, tak
ji určíme vzorcem qi = (-1)i-1
.
' $'
&
$
%Petr Hliněný, FI MU Brno 18 IB000 "Úv. Inf.": Množiny, Relace a Funkce
3.5 Posloupnosti a rekurentní vztahy3.5 Posloupnosti a rekurentní vztahy
Definice: Funkce p : N  R se nazývá posloupnost.
Mimo ,,funkčního zápisu p(n) často používáme ,,indexovou formu zápisu pn.
Poznámka: Obor hodnot posloupnosti může být i jiný než reálná čísla. Na posloup-
nost se také díváme jako na ,,seřazení vybraných prvků z oboru hodnot, s povoleným
opakováním hodnot (nemusí být prostá).
Také def. obor posl. může být od nuly nebo i od jedničky, jak je v aplikacích potřeba.
ˇ Příklady posloupností:
 p0 = 0, p1 = 2, . . . , pi = 2i, . . . je posloupnost sudých nezáporných čísel.
 3, 3.1, 3.14, 3.141, . . . je posloupnost postupných dekadických rozvojů .
 1, -1, 1, -1, . . . je posloupnost určená vztahem pi = (-1)i
, i  0.
 Pokud chceme stejnou posloupnost 1, -1, 1, -1, . . . zadat jako qi, i  1, tak
ji určíme vzorcem qi = (-1)i-1
.
ˇ Posloupnost je rostoucí či klesající, pokud pn+1 > pn či pn+1 < pn pro
všechna n.
' $'
&
$
%Petr Hliněný, FI MU Brno 19 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Rekurentní definice posloupnosti
Slovem rekurentní označujeme takové definice (či popisy), které se v jistých
bodech odvolávají samy na sebe.
(Už jste se setkali s ,,rekurzí při programování? A víte, co znamená?)
' $'
&
$
%Petr Hliněný, FI MU Brno 19 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Rekurentní definice posloupnosti
Slovem rekurentní označujeme takové definice (či popisy), které se v jistých
bodech odvolávají samy na sebe.
(Už jste se setkali s ,,rekurzí při programování? A víte, co znamená?)
Ukázky rekurentních vztahů:
ˇ Zadáme-li posloupnost pn vztahy p0 = 1 a pn = 2pn-1 pro n > 0, pak
platí pn = 2n pro všechna n.
' $'
&
$
%Petr Hliněný, FI MU Brno 19 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Rekurentní definice posloupnosti
Slovem rekurentní označujeme takové definice (či popisy), které se v jistých
bodech odvolávají samy na sebe.
(Už jste se setkali s ,,rekurzí při programování? A víte, co znamená?)
Ukázky rekurentních vztahů:
ˇ Zadáme-li posloupnost pn vztahy p0 = 1 a pn = 2pn-1 pro n > 0, pak
platí pn = 2n pro všechna n.
ˇ Obdobně můžeme zadat posloupnost qn vztahy q1 = 1 a qn = qn-1 + n
pro n > 1. Potom platí qn = 1
2 n(n + 1) pro všechna n.
Uměli byste toto dokázat indukcí?
' $'
&
$
%Petr Hliněný, FI MU Brno 19 IB000 "Úv. Inf.": Množiny, Relace a Funkce
Rekurentní definice posloupnosti
Slovem rekurentní označujeme takové definice (či popisy), které se v jistých
bodech odvolávají samy na sebe.
(Už jste se setkali s ,,rekurzí při programování? A víte, co znamená?)
Ukázky rekurentních vztahů:
ˇ Zadáme-li posloupnost pn vztahy p0 = 1 a pn = 2pn-1 pro n > 0, pak
platí pn = 2n pro všechna n.
ˇ Obdobně můžeme zadat posloupnost qn vztahy q1 = 1 a qn = qn-1 + n
pro n > 1. Potom platí qn = 1
2 n(n + 1) pro všechna n.
Uměli byste toto dokázat indukcí?
ˇ Známá Fibonacciho posloupnost je zadaná vztahy f1 = f2 = 1 a fn =
fn-1 + fn-2 pro n > 2.