Diskrétní matematika

Diskrétní matematika je zastřešující oblast matematiky, která se zabývá studiem diskrétních objektů – jasně oddělitelných částí. Například Lego kostky nebo karty jsou diskrétní. Můžeme je různě kombinovat či řadit, ale pracujeme s nimi vždy po jedné, nemá smysl je dělit. Naopak taková přímka je spojitá, můžeme ji dělit na stále jemnější části.

Pojem diskrétní matematika i názvy jednotlivých oblastí mohou znít abstraktně a složitě. Dají se však použít i v snadno představitelných případech jako jsou třeba různé hry.

Množiny jsou soubory prvků. Můžeme například uvážit množinu černých šachových figurek nebo množinu fotbalových útočníků. Práce s množinami představuje základ mnoha oblastí matematiky.

Logika zkoumá způsoby, jak vyvozujeme závěry z předpokladů. Pomocí logiky můžeme dokázat, že určitá pozice v šachu je vítězná pro jednoho z hráčů.

Kombinatorika se zabývá počítáním možností, jak můžeme objekty vzájemně kombinovat. Pomocí kombinatoriky můžeme určit počet způsobů, jak rozdělit skupinu hráčů do dvou fotbalových týmů.

Pravděpodobnost zkoumá pravidla, kterými se řídí náhodné události. Za využití pravděpodobnosti můžeme vypočítat, jak moc (ne)výhodné jsou sázky v hazardní hře s kostkami.

Popisná statistika se zabývá popisem jevů, které vykazují vliv náhody. Pomocí popisné statistiky můžeme srovnávat úspěšnost fotbalových útočníků v průběhu sezóny.

Množina je soubor prvků. Množiny využíváme jako dílčí prvek v mnoha oblastech matematiky. Příklad z geometrie: kružnice je množina bodů, které mají stejnou vzdálenost od středu. Množiny mají i mnoho praktických využití. Například při vývoji internetového obchodu program pracuje s množinou dostupných výrobků. Množiny jsou také důležité pro studium základů matematiky. Pomáhají nám například ujasnit si, co je to nekonečno.

Pro práci s množinami potřebujeme nejdříve ovládnout základní pojmy a značení a podívat se na různé způsoby, jak můžeme množiny zapsat (výčtem, charakteristickou vlastností, standardním značením).

S množinami můžeme provádět množinové operace jako je sjednocení a průnik. Tyto operace je vhodné si nejdříve procvičit na konkrétních příkladech. Když máme jasno v jednotlivých případech, přichází na řadu obecné vlastnosti množin a množinových operací. Pro získání vhledu a intuice se hodí zakreslovat si množiny pomocí Vennových diagramů.

Mezi pokročilejší témata patří množiny množin a potenční množina.

Množina je soubor prvků. U množiny není důležité pořadí prvků a nezohledňuje opakované výskyty prvků. Následující množiny jsou tady všechny stejné:

• \{\square, \bigcirc, \triangle\}
• \{\bigcirc, \triangle, \square\}
• \{\square, \square, \square, \bigcirc, \bigcirc, \triangle\}

Důležité číselné množiny mají v matematice svoje standardní označení:

Ostatní množiny zapisujeme dvěma hlavními způsoby:

Zápis výčtem. Prostě vyjmenujeme prvky množiny a zapíšeme je pomocí složené závorky. Například M = \{3, 7, 9\} je trojprvková množina obsahující čísla 3, 7 a 9.

Zápis pomocí charakteristické vlastnosti. Určíme, ze které množiny prvky vybíráme a jakou musí splňovat vlastnost. Například M = \{x \in \mathbb{N} \mid x < 10\} je množina přirozených čísel menších než 10.

Znázornění množinových operací pomocí Vennových diagramů:

• Každá množina je svou podmnožinou: A\subseteq A.
• Množina nemůže být svou vlastní podmnožinou.
• Prázdná množina je podmnožina jakékoliv množiny: \emptyset \subseteq A.
• Prázdná množina nemá žádnou vlastní podmnožinu.
• A \subseteq A \cup B
• A \cap B \subseteq A
• A \subseteq A \wedge B \subseteq A \Leftrightarrow A=B

Vennův diagram znázorňuje všechny možné vztahy několika množin. Vennův diagram znázorňuje prvky množin jako body v rovině a množiny jako plochy uvnitř křivek. Nejčastěji používané jsou Vennovy diagramy pro dvě a tři množiny, ve kterých jsou množiny znázorněny pomocí kruhů. Je možné ztvárnit Vennovy diagramy i pro více množin, ale k tomu již nevystačíme s kruhy (tyto diagramy nejsou přehledné a tudíž se příliš nevyužívají).

Typický Vennův diagram pro tři množiny:

Příklad s konkrétními prvky (množina A obsahuje červené útvary, množina B obsahuje kolečka, množina C obsahuje vyplněné útvary):

Vennovy diagramy využíváme například pro názornou ilustraci množinových operací. Následující obrázek ilustruje B \cap (A \cup C):

Množina prvkem množiny

Prvkem množiny může být i jiná množina. S takovým prvkem pracujeme stejně jako s jinými prvky, jen se nesmíme nechat zmást.

Příklad: Množina M = \{a, \{b, c, d, e\}, \emptyset\} obsahuje tři prvky:

• „obyčejný“ prvek a
• čtyřprvkovou množinu \{b, c, d, e\}
• prázdnou množinu \emptyset

Pozor na rozdíl mezi prázdnou množinou a množinou obsahující prázdnou množinu:

• \emptyset (též můžeme psát \{\}) je prázdná množina, její velikost je 0,
• \{\emptyset\} je množina obsahující prázdnou množinu, její velikost je 1.

Potenční množina

Potenční množina množiny M obsahuje všechny podmnožiny množiny M. Potenční množinu značíme \mathcal{P}(M) (existují i další značení, například 2^M).

Příklad: Pro množinu M = \{a, b, c\} jsou všechny její podmnožiny:

• \{\}
• \{a\}
• \{b\}
• \{c\}
• \{a, b\}
• \{a, c\}
• \{b, c\}
• \{a, b, c\}

Potenční množina je množina všech těchto množin, tj. \mathcal{P}(M)=\{\{\}, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}\}.

Potenční množina množiny M vždy obsahuje jako svůj prvek samotnou množinu M. Každá potenční množina také obsahuje jako svůj prvek prázdnou množinu.

Logika zkoumá způsoby, jak vyvozujeme závěry z předpokladů. Logika původně vznikla jako součást filosofie, později se výrazně rozvinula v matematice. Dnes má důležité uplatnění i v informatice.

Základ matematického pojetí logiky je výroková logika, ve které pracujeme s výroky (tvrzení, která jsou buď pravdivá, nebo nepravdivá) a logickými spojkami (a zároveň, nebo, negace). Rozšířením výrokové logiky je predikátová logika, ve které navíc používáme kvantifikátory (existuje, pro každý).

Přehled témat o logice dostupných na Umíme matiku:

V rámci systémů Umíme najdete logiku také na informatice: logika na Umíme informatiku. Tam je důraz kladen na logické spojky používané při programování a na řešení logických úloh.

Výroky

Výrok je sdělení, u kterého má smysl otázka, zda je pravdivý, nebo nepravdivý, přičemž může nastat jen jedna z těchto možností.

Příklady výroků:

• Město Brno leží v České republice. (pravdivý výrok)
• Brno je hlavní město České republiky. (nepravdivý výrok)
• Na Marsu je zakopán poklad. (výrok, jehož pravdivost neznáme)

Příklady vět, které nejsou výroky: Máš hlad? Běž do obchodu pro vajíčka.

Logické spojky

Tautologie a kontradikce

Tautologie je výroková formule, která je vždy pravdivá. Příklady:

• A \vee \neg A (zákon vyloučení třetího)
• (A \Rightarrow B) \Leftrightarrow (\neg B \Rightarrow \neg A)

Kontradikce je výroková formule, která je vždy nepravdivá. Příkladem je formule A \wedge \neg A (zákon sporu).

Formule je splnitelná pokud není kontradikcí.

Pravdivostní tabulka logických operací

Přepis implikace a ekvivalence

Negování složených výroků

Pravidla pro negaci disjunkce a konjunkce (2. a 3. řádek tabulky) se nazývají De Morganovy zákony.

Analogické zákony jako při počítání s čísly

Pro logické operace \wedge, \vee také platí komutativní (1. a 2. řádek následující tabulky), asociativní (3. a 4. řádek) a distributivní zákony (5. a 6. řádek):

Kvantifikátory

Příklady výroků s kvantifikátory

Vlastnost Číslo x je sudé. můžeme vyjádřit jako Existuje celé číslo k takové, že x = 2\cdot k. To můžeme zapsat jako \exists k \in \mathbb{Z}: x = 2\cdot k.

Výrok Ponorky (P) nemohou létat (L). můžeme zapsat jako \forall x: P(x) \Rightarrow \neg L(x).

U složitejších výroků s více kvantifikátory musíme dávat na pořadí kvantifikátorů:

• \exists x\in M\ \forall y \in M: y \leq x – existuje prvek v množině M, který je větší roven všem ostatním prvkům v M, tj. výrok říká, že množina má největší prvek.
• \forall x\in M\ \exists y \in M: y \leq x – pro každý prvek v množině M existuje prvek x, který je menší nebo roven X. Protože klidně můžeme vybrat y=x, je to splněno pro každou množinu (pro pokročilé: tedy pouze pokud uvažujeme množiny čísel a \leq jako běžné uspořádání na číslech).

Negace výroků s kvantifikátory

Při negování výroků s kvantifikátory měníme existenční kvantifikátor na obecný (a naopak) a posouváme negaci „dovnitř“. Příklad:

• Není pravda, že všechny kočky (K) jsou černé (C).
• \neg (\forall x: K(x) \Rightarrow C(x))
• Změníme obecný kvantifikátor na existenční a znegujeme výrok.
• \exists x: \neg(K(x) \Rightarrow C(x))
• Nyní znegujeme implikaci pomocí pravidla \neg(A \Rightarrow B) \Leftrightarrow (A \wedge \neg B).
• \exists x: K(x) \wedge \neg C(x)
• Existuje kočka, která není černá.

Pojmy

• Permutace je uspořádání prvků do fixního pořadí.
• Kombinace (k prvková) je výběr k prvků ze zadané množiny.
• Kombinace s opakováním (k prvková) je výběr k prvků ze zadané množiny, přičemž prvky se mohou opakovat.
• Variace (k prvková) je uspořádaný výběr k prvků ze zadané množiny.
• Variace s opakováním (k prvková) je uspořádaný výběr k prvků ze zadané množiny, přičemž prvky se mohou opakovat.

Příklady

Vzorce

Počty permutací, kombinací a variací udává následující tabulka:

Kombinační číslo udává počet kombinací, tj. způsobů, jak vybrat k prvků z n prvkové množiny. Kombinační čísla se vyskytují velmi často v kombinatorických výpočtech, a proto mají speciální značení \binom{n}{k} (čteme „n nad k“).

Pro n \geq k \geq 0 platí: \binom{n}{k} = \frac{n!}{k!(n-k)!}

Pro kombinační čísla platí řada dalších vztahů, například:

• \binom{n}{k} = \binom{n}{n-k}
• \binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}
• \sum_{k=0}^n \binom{n}{k} = 2^n

Příklady:

Náhodný jev je výsledek náhodného pokusu, o kterém lze po provedení pokusu rozhodnout, zda nastal nebo nenastal. Jeho typickým rysem je, že může, ale nemusí nastat. Pravděpodobnost jevu je míra očekávání, že jev nastane. Pravděpodobnost je číslo mezi 0 a 1. V běžném jazyce vyjadřujeme často pravděpodobnost v procentech, což je stonásobek pravděpodobnosti používané v matematice.

Pojmy a značení

Příklad

• V pytlíku mám pět koulí, z toho dvě jsou červené, dvě modré a jedna žlutá. Koule jsou stejné až na barvu. Pokus spočívá v tom, že z pytlíku poslepu vytáhnu kouli.
• „Vytáhnu červenou kouli.“ je náhodný jev. Jde o jev elementární. Jeho pravděpodobnost je 0,4 (v běžné řeči bychom mohli říct 40 %).
• „Vytáhnu červenou nebo žlutou kouli.“ je složený jev. Jeho pravděpodobnost je 0,6.
• „Vytáhnu kouli.“ je jev jistý.
• „Vytáhnu zelenou kouli.“ je jev nemožný.

Průměr a medián jsou míry centrální (střední) tendence, tj. vyjadřují „typickou“ hodnotu proměnných z určitého vzorku.

Průměr je součet hodnot vydělený jejich počtem. Přesněji řečeno jde o aritmetický průměr (existují i jiné druhy průměrů, např. harmonický či geometrický).

Medián je prostřední hodnota ze seřazené posloupnosti hodnot. Je definován jako hodnota větší nebo rovna polovině hodnot v souboru a menší nebo rovna polovině hodnot v souboru.

Příklad: Uvažme soubor hodnot 10, 3, 8, 4, 5. Průměr je součet dělený počtem, tj. 30:5=6. Pro určení mediánu hodnoty nejdříve seřadíme: 3, 4, 5, 8, 10. Medián je prostřední hodnota, tedy 5.

Pokud má soubor sudý počet prvků, většinou se za medián označuje průměr dvou prostředních hodnot. Například pro soubor hodnot 10, 2, 9, 4, 14, 5 je seřazená posloupnost 2, 4, 5, 9, 10, 14. Hodnoty uprostřed posloupnosti jsou 5 a 9, medián je tedy 7.

Někdy máme soubor hodnot, které lze uspořádat podle velikosti, ale není možné vypočítat aritmetický průměr dvou hodnot. Například pro soubor čtyř hodnot S, M, XL, XXL velikostí oblečení splňuje definici mediánu jakákoliv hodnota od M do XL, tedy M, L, i XL.

Kvantily jsou charakteristiky polohy statistického znaku podobně jako např. aritmetický průměr a medián. Kvantily lze určit pro ordinální, intervalové a poměrové typy dat.

Soubor n hodnot uspořádáme podle velikosti: x_1 \le x_2 \le \ldots \le x_{n-1} \le x_n

Mějme číslo \theta mezi nulou a jedničkou. Kvantil Q_{\theta} je hodnota, která dělí uspořádanou posloupnost hodnot v souboru na dolní a horní část tak, že dolní část obsahuje alespoň \theta \cdot n hodnot a horní část alespoň (1-\theta)\cdot n hodnot.

x_1 \le \ldots \le x_c \le Q_{\theta} \le x_{c+1} \le \ldots \le x_n

• Je-li \theta \cdot n necelé číslo, a nejbližší větší celé číslo je k, volíme obvykle Q_{\theta}=x_k.
• Je-li \theta \cdot n=m celé číslo, volíme Q_{\theta} = \frac{x_{m}+x_{m+1}}{2} (pokud je možné tento aritmetický průměr spočítat - tedy pro intervalové a poměrové znaky).

Například vezmeme soubor osmi čísel 0,0,0,0,1,2,3,4. Kvantil Q_{0{,}1} určíme takto: 0{,}1 \cdot 8 = 0{,}8, nejbližší větší celé číslo je 1, takže Q_{0{,}1}=x_1=0. Kvantil Q_{0{,}75} určíme takto: 0{,}75 \cdot 8 = 6, takže Q_{0{,}75}=\frac{x_6+x_7}{2}=\frac{2+3}{2}=2{,}5.

Pro ordinální znaky nemusí být možné spočítat aritmetický průměr. Jako kvantil Q_{\theta} pak zvolíme některou hodnotu, která vhodně dělí uspořádanou posloupnost hodnot souboru.

Například spočítejme kvantil Q_{0{,}8} pro hodnoty S, S, M, L, XXL znaku „velikost oblečení“. 5 \cdot 0{,}8=4, Q_{0{,}8} je jakákoliv hodnota mezi x_4 a x_5, tedy L,XL, nebo XXL.

p% kvantil Q_{\frac{p}{100}} se nazývá p. percentil.

Některé významné kvantily:

Mezikvartilové rozpětí je rozdíl horního a dolního kvartilu: Q_{0{,}75}-Q_{0{,}25} Mezikvartilové rozpětí (někdy označované jako IQR) lze spočítat pro intervalové a poměrové znaky.

Například, určeme mezikvartilové rozpětí pro soubor hodnot 0,0,0,0,1,2,3,4. Horní kvartil Q_{0{,}75} jsme už dříve spočítali, je to 2{,}5. Dolní kvartil Q_{0{,}25} je \frac{x_2+x_3}{2}=\frac{0+0}{2}=0. Mezikvartilové rozpětí je 2{,}5-0=2{,}5.

Statistický soubor má rozsah n, pokud obsahuje právě n jednotek. Například statistickým souborem s rozsahem 10 může být skupinka 10 dětí ze třetí třídy. Jednotliví žáci a žákyně jsou pak jednotky statistického souboru.

Příklady statistických znaků, které nás mohou zajímat: jméno, výška, známka z prvouky. Předpokládejme, že jména dětí z naší skupinky deseti žáků a žákyň jsou: Anna, Eva, Jan, Jan, Jan, Vanesa, Vanesa, Mirka, Tobiáš, Tomáš.

Znak jméno tedy v našem statistickém souboru nabývá sedmi různých hodnot – Anna, Eva, Jan, Vanesa, Mirka, Tobiáš, Tomáš. Některé děti se mohou jmenovat stejně.

Absolutní četnost hodnoty znaku v daném statistickém souboru je počet jednotek ze statistického souboru, které mají danou hodnotu znaku.

Například absolutní četnost hodnoty „Jan“ znaku jméno je 3, protože ve skupince jsou tři žáci jménem Jan. Absolutní četnost hodnoty „Eva“ znaku jméno je 1.

Relativní četnost hodnoty znaku v daném statistickém souboru vypočítáme jako podíl počtu jednotek s danou hodnotou znaku počtem všech jednotek statistického souboru. Také se dá říci, že relativní četnost hodnoty znaku je podíl absolutní četnosti této hodnoty znaku a rozsahu n statistického souboru. Relativní četnost se zadává jako číslo v intervalu [0,1] nebo v procentech.

Například relativní četnost hodnoty „Vanesa“ znaku jméno je \frac{2}{10}=0{,}2, protože ve skupince celkem deseti dětí jsou dvě žákyně jménem Vanesa. Relativní četnost hodnoty „Vanesa“ znaku jméno můžeme zapsat také jako 20\ \%.

Součet absolutních četností všech hodnot jednoho znaku je roven rozsahu n daného statistického souboru.

Součet relativních četností všech hodnot jednoho znaku je 1 neboli 100\ \%.

Korelace je vztah mezi dvěmi veličinami. Korelační koeficient je číslo, které vyjadřuje sílu tohoto vztahu.

Existuje více způsobů, jak korelaci měřit. Nejčastěji používaný je Pearsonův korelační koeficient. Ten se značí r a má následující vlastnosti:

• Nabývá hodnot z intervalu [-1, 1].
• Měří pouze lineární závislost mezi veličinami.
• Pokud je hodnota kladná, odpovídá zvětšení jedné veličiny zvětšení druhé.
• Pokud je hodnota záporná, odpovídá zvětšení jedné veličiny zmenšení druhé.
• Pokud je hodnota nulová, není mezi veličinami lineární závislost.
• Pokud je hodnota přesně 1 nebo -1, je mezi veličinami přesná lineární závislost.

Uvažujme statistický soubor zvířátek z Hrusic. Vezměme z něj tři jednotky na ukázku: kocourka Mikeše, kozla Bobeše a prasátko Pašíka. Budeme si u nich všímat různých typů znaků.

Nominální znak nabývá hodnot, u kterých můžeme testovat rovnost, tj. určit, jestli jsou stejné nebo různé. Například jméno, barva.

Ordinální znak nabývá hodnot, u kterých můžeme testovat rovnost a které navíc umíme porovnávat, tj. určit, která ze dvou různých hodnot je menší a která větší. Například známka z počtů, velikost oblečení (XS, S, M, L, XL), obliba brokolicové polívky („fuj“,„nic moc“,„mňam“).

Intervalový znak nabývá hodnot, u kterých můžeme testovat rovnost, porovnávat je a určit rozdíl dvou hodnot, tj. stejný interval mezi jednou a druhou dvojicí hodnot vyjadřuje i stejný rozdíl v intenzitě zkoumané vlastnosti. Například teplota ve stupních Celsia, rok narození.

Poměrový znak nabývá hodnot, u kterých můžeme testovat rovnost, porovnávat je, určit rozdíl dvou hodnot a určit poměr dvou hodnot, tj. spočítat jejich podíl, který smysluplně vyjadřuje kolikrát je jedna hodnota větší než druhá. Například teplota ve stupních Kelvina, hmotnost. Teplota ve stupních Celsia může jít i do záporných čísel a těleso o teplotě 10 °C nemá dvakrát větší kinetickou energii částic než těleso o teplotě 5 °C, takže teplota ve stupních Celsia není poměrový znak.

Alternativní znak je pojem mimo tuto hierarchii, znamená to, že znak nabývá pouze dvou hodnot. Například zdravý – nemocný, má boty – nemá boty.

Aritmetický průměr, medián a modus jsou charakteristiky polohy znaku. Používáme je k popisu typické hodnoty znaku.

Aritmetický průměr pro daný soubor se počítá jako podíl součtu hodnot znaku rozsahem souboru.

• Aritmetický průměr lze spočítat pro intervalové a poměrové znaky.
• Nejlépe se hodí k popisu typické hodnoty znaku, který nabývá v daném souboru podobných hodnot bez příliš odlišných extrémů, které by aritmetický průměr vychýlily mimo typické hodnoty.

Příklad použití aritmetického průměru – soubor hodnot 122, 116, 120, 118 znaku „výška dítěte v cm“ má aritmetický průměr 119.

Medián dělí řadu vzestupně seřazených hodnot na dvě stejně početné poloviny.

• Pro lichý počet hodnot je medián prostřední prvek.
• Pro sudý počet hodnot může definici mediánu odpovídat více hodnot, někdy se v takovém případě bere jako medián aritmetický průměr dvou prostředních hodnot (samozřejmě jen pokud lze pro daný znak aritmetický průměr spočítat).
• Medián lze určit pro ordinální, intervalové a poměrové znaky.
• Narozdíl od aritmetického průměru není ovlivněn extrémními hodnotami.

Příklad použití mediánu – soubor hodnot 1, 1000, 1002, 1003 znaku „hmotnost krokodýla v kg“ má medián 1001 (nebo jakékoli číslo od 1000 do 1002). Extrémní malá hodnota 1 způsobí, že aritmetický průměr je 751{,}5, což neodpovídá typické hodnotě „něco málo přes 1000 kg“.

Modus je hodnota znaku, která má v daném souboru největší relativní (i absolutní) četnost.

• Takových hodnot může být víc než jedna.
• Modus můžeme spočítat pro nominální, ordinální, intervalové a poměrové znaky.

Příklad použití – modus souboru hodnot 1, 1, 1, 1, 2, 2 znaku „počet hrbů velblouda“ je 1.