Diskrétní Matematika Témata

Created by Jan Hartman

Shrnutí témat předmětu diskrétní matematika na MFF UK. Barvy odpovídají hloubce zanoření od kořene (DISKRÉTNÍ MATEMATIKA). Jdou v pořadí: červená, fialová, zelená, modrá, žlutá. U některých buněk lze zobrazit i druhé okno, které obsahuje příklady definovaného pojmu.

#matematika

Vztahy mezi množinamy

$\subseteq$ inkluze (být podmnožinou)
$\in$ náležení (být prvkem)

Operace na množinách

$\cap$ ... průnik
$\cup$ ... sjednocení
$\setminus$ … rozdíl
doplněk

Jaké vlastnosti množiny splňují

máme-li množinu A, tak do ni každý prvek buď patří nebo nepatří, nic mezitím
axiom extenzionality: obsahují-li dvě množiny přesně ty samé prvky, tak se ty množiny rovnají (nezáleží na pořadí ani na násobnosti výskytu)

Funkce na množinách

… mohutnost množiny
$A \times B$ … kartézský součin
$2^{A}$ … mocnina

Množiny

Hromadné operátory

$\sum$ … suma
$\prod$ … produkt
$\bigcap$ … průnik
$\bigcup$ … sjednocení
jaké vlastnosti musí operace, ze které je hromadný operátor odvozený splňovat (a proč?)

Slabá

v indukčním kroku předpokládáme, že platí jen jediná bezprostředně předchozí instance dokazovaného tvrzení

Axiomatická definice

řekneme, jaké axiomy námi definovaný objekt splňuje
jakýkoliv objekt, který pak toto splňuje je považován za tu věc o které mluvíme

Příklady:

definice grupy
axiomy teorie množin

Matematická indukce

Axiom

tvrzení, které automaticky považujeme za pravdivé

Silná

v i.k. předpokládáme, že platí všechny předchozí instance dokazovaného tvrzení

Příklady:

lámání čokolády

Důkaz

přesná posloupnost kroků začínající od nějakého jasného pozorování až k cílovému tvrzení, které chceme dokázat
snažíme se přesvědčit nepřítele, který nám do toho může šťourat a nutit nás vysvětlit libovloný krok více do hloubky

Základy matematiky

Jak se buduje matematika

Využití v algoritmizaci

grafy

Lemma

pomocné tvrzení, které je použito jako mezikrok důkazu nějaké věty

Skládání

$R \circ S$ je nová relace pro kterou platí, že $x(R \circ S)z$ právě tehdy když existuje takový, že xRy a ySz

Strojové učení

pravděpodobnost a statistika

Věta

pravdivé tvrzení
pravdivost je ověřená důkazem, vyzkoušením všech možností atp.

Tvrzení

říká něco o nějakých matematických objektech
může být buď pravdivé nebo lživé, ale ne oboje

VYUŽITÍ

Definice

přesný popis nějakého matematického objektu nebo vlastnosti
abychom věděli, o čem se vůbec bavíme
např. dělitelnost, prvočíslo

Příklady:

dělitelnost
prvočíslo
být podmnožinou
ekvivalence, uspořádání

Inverze

$R^{-1}$ je relace pro kterou platí $xR^{-1}y$ právě tehdy když yRx

Jak se ověřuje platnost tvrzení?

dosadíme všechny možné případy, o kterých něco říkáme
dokážeme to

Operace na relacích

Prostá

pokud $x \neq y$ , tak nutně $f(x) \neq f(y)$

Příklady:

funkce zobrazující přirozené číslo na číslo o jedna větší

Protipříklady:

funkce z množiny všech lidí na světě do $\mathbb{N}$ , zobrazující člověka na jeho věk

DISKRÉTNÍ MATEMATIKA

Diskrétní množina je taková, že každý její prvek lze ohraničit okolím, ve kterém už nebude žádný jiný prvek množiny.

Z latiny: dis- (od sebe) + cerno (prosít)

Co je diskrétní: přirozená čísla, konečné množiny

Co není diskrétní: jednotlivé body na přímce (můžu najít okolí, ve kterém už není žádný další bod? kdo je nejbližší soused nějakého bodu?)

Funkce

relace $f \subseteq X \times Y$ taková, že pro každé $x \in X$ existuje právě jedno $y \in Y$ takové, že
zapisujeme (jaktože si tento zápis můžeme dovolit? nepokazí se něco?)

Příklady:

množina všech lidí a $v: M \rightarrow \mathbb{N}$ zobrazí člověka na jeho věk

Protipříklady:

je domácí mazlíček člověka (není funkce jelikož může mít více mazlíčků, nebo žádného)

Na

pro každý $y \in Y$ existuje $x \in X$ takové, že y = f(x)

Příklady:

projekce $\mathbb{R} \times \mathbb{R} \rightarrow \mathbb{R}$ , která zobrazí na

Protipříklady:

funkce z množiny všech lidí na světě do $\mathbb{N}$ , zobrazující člověka na jeho věk

Vzájemně jednoznačná

funkce, která je prostá a na

Příklady:

funkce z $\mathcal{P}(A) \rightarrow \{0,1\}^{|A|}$ , která každé podmnožině $X \subseteq A$ přidělí posloupnost nul a jedniček, kde nula odpovídá tomu, že množina neobsahuje daný prvek a obráceně

Relace

relace je libovolná podmožina kartézského součinu dvou množin, tedy $R \subseteq A \times B$
pokud , tak to znamená, že prvek je v relaci s prvek
- tuto skutečnost zapisujeme

Reflexivita

pro každé $x \in X$ platí xRx

Příklady:

člověk ví o existenci člověka (nemusí být symetrická ani tranzitivní)

Grafy

Vlastnosti relací

mějme množinu a relaci $R \subseteq X \times X$

Symetrie

pokud platí xRy tak nutně musí yRx

Příklady:

pokud si potřásl rukou s (nemusí být reflexivní, ani tranzitivní)

Pochopení, jak věc funguje

Antisymetrie

slabá: pokud a zároveň , tak nutně
silná: pokud tak nutně neplatí

Příklady:

je biologickou matkou (určitě není tranzitivní, ani reflexivní)

MOTIVACE

Proč se učit důkazy

Uspořádání

relace, která je:

reflexivní
antisymetrická
transitivní

Příklady:

pokud dělí
když je předkem nebo identický

Protipříklady:

když z tvrzení plyne tvrzení
když student má aspoň z jednoho předmětu horší známku než student nebo je identický s

Ekvivalence

relace, která je:

reflexivní
symetrická
tranzitivní

Příklady:

rovnost modulo nějaké číslo
symetrická dosažitelnost
isomorfismus grafů

Protipříklady:

když váží podobně jako $\pm$ 1 kg

Tranzitivita

pokud xRy a zároveň yRz , tak nutně xRz

Příklady:

dokazatelnost (nemusí být symetrická, ale je vždy reflexivní)
dosažitelnost (stejně jako výše)

Ověření korektnosti

když nějaké tvrzení dokážeme, můžeme si být jistí, že to bude platit už na věčnost a nic to nezmění
spoustu technologií má matematické základy - kryptografie, algoritmy atd.
bez matematického důkazu, že fungují bychom mohli dopadnout špatně

Rozklad na ekvivalenční třídy

máme-li ekvivalenci na množině , tak tato ekvivalence jednoznačně určuje rozklad množiny na podmnožiny
množiny tvoří rozklad pokud:
1. $A_1 \cup \ldots \cup A_n = X$
2. pro $i \neq j$ platí $A_i \cap A_j = \emptyset$
3. $A_i \neq \emptyset$

Kombinatorické počítání

Lexikografické uspořádání

$(x_1,\ldots,x_n) \preceq_{lex} (y_1,\ldots,x_n)$ pokud:

$(x_1, \ldots, x_n) = (y_1, \ldots ,y_n)$ nebo
existuje t.ž. $x_1 = y_1 , \ldots ,x_i = y_i$ a $x_{i+1} < y_{i+1}$

Řetězec a antiřetězec

množina $A \subseteq X$ je vůči uspořádání $\preceq$ :

řetězcem pokud pro každé $x,y \in A$ platí $x \preceq y$ nebo $y \preceq x$
antiřetězcem pokud pro každé $x,y \in A$ t.ž. $x \neq y$ máme $x \not \preceq y$

Nejmenší a největší prvky

je nejmenším prvkem vzhledem k relaci $\preceq$ pokud pro všechny $y \in X$ platí $x \preceq y$

Hasseův diagram

diagram pro uspořádání $\preceq$ na množině t.ž. je spojeno s právě tehdy když je bezprostředním předchůdcem

Minimální a maximální prvky

je minimálním prvkem vzhledem k relaci $\preceq$ pokud neexistuje $y \in X$ t.ž. $y \prec x$

Bezprostřední předchůdce

je bezprostředním předchůdcem v relaci $\preceq$ pokud:

$x \preceq y$ a zároveň
$x \neq y$ a zároveň
neexistuje různé od t.ž. $x \preceq z$ a $z \preceq y$