F U N K C E A
P O S L O U P N O S T I
F U N K C E
- funkce je speciální typ relace: funkce je taková (n- ární)
relace, kde prvních n - 1 hodnot v n-tici jednoznačně
určuje poslední hodnotu
(n-ární relace: množina uspořádaných n-tic)
- funkce je zobrazení: relace R z množiny A do množiny B
se nazývá zobrazením z A do B, právě když ke každému
prvku a EDA existuje nejvýše jeden prvek b GDB takový,
že platí (a, b)enR)
F U N K C E
alternativně se můžeme na relaci podívat jako na vstupněvýstupní
mechanismus:
- prvních n - 1 hodnot v n-tici můžeme pokládat za
argumenty
- relace (vstup), poslední hodnotu za její výsledek
- pokud má být taková relace funkcí, výstup musí být
jednoznačně určen argumenty
F U N K C E
formálně, binární relace / na množině A je funkce, pokud
platí:
Va, b, c E A ( ( a , b) G / A (a, c) G / => ů = c )
obdobně, ternární relace / na množině A je funkce, pokud
Va, b, c, d E A ((a, b, c) E f A (a, b, d) E f => c = d )...
F U N K C E
binární relaci /
mezi množinami A a B, která je funkcí,
říkáme „funkce z A do B" a zapisujeme
f\A^B
V L A S T N O S T I FUNKCÍ
injektivita. Funkce / : A —• B je injektivní (též prostá), pokud platí
Va, b e A (/(a) = /(ô) => a = b ) neboli žádné dva prvky nemají stejný obraz
surjektivita. Funkce / : A —• B je surjektivní (též na), pokud platí
VbEB(3aEA(b = f (a))
neboli každý prvek oboru hodnot má nějaký vzor, případně můžeme říci, že celý obor
hodnot je pokrytý
úplnost. Funkce / : A —• B je úplná, pokud platí
Va e A ( 3b e B (b = f (a))
neboli celý definiční obor je pokrytý. Často se můžete setkat s tím, že pojmem funkce je
myšlena úplná funkce.
řekneme, že funkce je bijekce právě tehdy, je-li současně injektivní, surjektivní a úplná
P O S L O U P N O S T I
- posloupnosti jsou množiny prvků, v níž (na rozdíl od
množin) záleží na pořadí
- prvky se v posloupnosti také mohou opakovat
- konečné posloupnosti můžeme považovat za uspořádané
n-tice
- konečná posloupnost délky n je úplná funkce, jejímž
definičním oborem je množina n
P O S L O U P N O S T I
posloupnosti typicky zapisujeme jako aO, a 1 , a n , c o ž považujeme jen za jiný
druh zápisu pro /(O), /(1),f{n),....
v případě nekonečných posloupností často pracujeme s induktivními definicemi
v případě posloupností tyto definice vypadají tak, že vypíšeme první člen (případně
prvních několik členů), což je analogie báze indukce, a poté určíme předpis, podle
kterého dostaneme n-íý prvek pomocí jednoho, případně několika předchozích
prvků (analogie indukčního kroku)
podle takovéto definice jsme schopni zkonstruovat libovolný prvek posloupnosti
Příkladem nekonečné posloupnosti je tzv. Fibonacciho posloupnost, kde každý další
člen je součtem dvou předchozích členů: 0,1,1, 2, 3, 5, 8,13, 21, 34,...
induktivní definice Fibonacciho posloupnosti vypadá takto:
• aO = 0
• a1 = 1
• an= an-1 + an-2