Společná matematika

1. Základy diferenciálního a integrálního počtu 2. Algebra a lineární algebra 3. Diskrétní matematika 4. Teorie grafů 5. Pravděpodobnost a statistika 6. Logika

1. Základy diferenciálního a integrálního počtu

Posloupnosti reálných čísel a jejich limity (definice)
- posloupnost s hodnotami v množině $M$ je zobrazení z $\mathbb N$ do $M$
- nechť $(a_n)$ je reálná posloupnost a $L \in \mathbb R^*$
- pokud $(\forall\varepsilon\gt 0)(\exists n_0\in\mathbb N):(n\geq n_0\implies |a_n-L|\lt\varepsilon)$ , píšeme, že $\lim a_n=L$ nebo $\lim_{n\to\infty}a_n=L$ nebo $a_n\to L$ , a řekneme, že posloupnost $(a_n)$ má limitu $L$
- pro $L\in \mathbb R$ mluvíme o vlastní limitě a pro $L=\pm\infty$ o limitě nevlastní
- posloupnost, která má vlastní limitu, konverguje (pokud ji nemá, tak diverguje)
- každá posloupnost reálných čísel má nejvýše jednu limitu
Aritmetika limit
- nechť $(a_n),(b_n)$ jsou posloupnosti reálných čísel takové, že $\lim a_n=a$ a $\lim b_n=b$
- pak…
  - $\lim\,(a_n+b_n)=a+b$
  - $\lim\,(a_nb_n)=ab$
  - pokud $b_n\neq 0$ pro každé $n\gt 0$ , pak $\lim\,(a_n/b_n)=a/b$
- to vše platí za předpokladu, že je výraz na pravé straně definován
  - neurčité výrazy (nejsou definované): součet nekonečen s různými znaménky, součin nekonečna s nulou, podíl nekonečen, dělení reálného čísla nulou
- pokud je $(a_n)$ $(a_{n})$ omezená a $(b_n)$ $(b_{n})$ konverguje k nule, pak $\lim\,(a_nb_n)=0$ $lim (a_{n} b_{n}) = 0$
  - tzn. limita $(a_n)$ nemusí existovat
Limity a uspořádání
- nechť $(a_n),(b_n)$ jsou posloupnosti reálných čísel takové, že mají limity $\lim a_n=a$ a $\lim b_n=b$
- když $a\lt b$ , tak existuje $n_0$ , že $n\gt n_0\implies a_n\lt b_n$
- a naopak, když $a_n\leq b_n$ pro každé $n\gt n_0$ , pak $a\leq b$
- poznámka: může se stát, že $\forall n:a_n\lt b_n$ $\forall n : a_{n} < b_{n}$ , ale $\lim a_n=\lim b_n$ $lim a_{n} = lim b_{n}$
  - např. uvažujme $a_n=1-\frac1n\lt b_n=1$ , přičemž $\lim a_n=\lim b_n=1$
Věta o dvou policajtech
- nechť posloupnosti $(a_n),(b_n),(c_n)\subseteq\mathbb R$ $(a_{n}), (b_{n}), (c_{n}) \subseteq R$ splňují
  - $\lim a_n=\lim b_n=a\in\mathbb R$
  - $\forall n\gt n_0:a_n\leq c_n\leq b_n$
- pak $(c_n)$ konverguje a $\lim c_n=a$
- platí to i pro nevlastní limity – tam nám stačí jeden policajt
Součet řady a částečný součet řady
- nekonečná řada (reálných čísel) je výraz $\sum_{n=1}^\infty a_n=a_1+a_2+a_3+\dots$
  - kde $(a_n)_{n\geq 1}$ je posloupnost reálných čísel
- ( $n$ -tý) částečný součet řady se značí $s_n$ a je to součet jejích prvních $n$ členů ( $s_n=a_1+a_2+\dots+a_n$ )
- pokud existuje vlastní limita posloupnosti $(s_n)$ částečných součtů dané řady, mluvíme o konvergentní řadě a limita $\lim s_n$ je jejím součtem
- pokud $\lim s_n$ neexistuje nebo je nevlastní, je daná řada divergentní
Geometrická řada, harmonická řada
- geometrická řada
  - $\sum_{n=0}^\infty q^n=1+q+q^2+q^3+\dots$
  - $q\in\mathbb R$ je parametr zvaný kvocient
  - pro součet geometrické řady platí $\sum_{n=0}^\infty q^n=\begin{cases}\frac1{1-q} &-1\lt q\lt1\\ +\infty &q\geq 1\\\text{neexistuje}&q\leq -1\end{cases}$
  - vyplývá to ze vzorce pro částečný součet $s_n=\frac{q^n-1}{q-1}$
- harmonická řada
  - $\sum_{n=1}^\infty\frac 1n=1+\frac12+\frac13+\dots$
  - diverguje, přestože její prvky konvergují k nule
- pro řady tvaru $\sum_{n=1}^\infty\frac1{n^s}$ obecně platí, že konvergují pro $s\gt 1$ a divergují pro $s\leq 1$
Limita funkce v bodě: definice, aritmetika limit
- okolí bodu je interval $U(a,\delta)=(a-\delta,a+\delta)$ $U (a, δ) = (a - δ, a + δ)$
  - okolí nekonečen definujeme jako $U(+\infty,\delta)=(1/\delta,+\infty)$ , podobně pro $-\infty$
  - definujeme také pravé okolí bodu $U^+(a,\delta)=[a,a+\delta)$ , podobně levé okolí $U^-$
  - prstencová okolí bodu $a\in\mathbb R$ definujeme jako obyčejná okolí s vyjmutým bodem $a$ , značí se jako $P(a,\delta)$ apod.
- řekneme, že funkce $f$ $f$ má v bodě $a\in\mathbb R^*$ $a \in R^{*}$ limitu $A\in\mathbb R$ $A \in R$ , když $(\forall\varepsilon\gt 0)(\exists\delta\gt 0):x\in P(a,\delta)\implies f(x)\in U(A,\varepsilon)$ $(\forall ε > 0) (\exists δ > 0) : x \in P (a, δ) ⟹ f (x) \in U (A, ε)$
  - zapisujeme $\lim_{x\to a}f(x)=A$
  - poznámka: limita funkce $f$ v bodě $a$ nezávisí na její hodnota v $a$ , funkce $f$ dokonce ani nemusí být v $a$ definovaná
  - pokud místo prstencového okolí $P$ $P$ použijeme pravé prstencové okolí $P^+$ $P^{+}$ , dostaneme definici limity zprava, značí se $\lim_{x\to a^+}f(x)$ $lim_{x \to a^{+}} f (x)$
    - obdobně lze definovat limitu zleva
    - pokud $\lim_{x\to a^+}f(x)=\lim_{x\to a^-}f(x)=A$ , pak $\lim_{x\to a}f(x)=A$
    - naopak pokud jsou limity zprava a zleva různé, limita neexistuje
  - podobně jako u posloupnosti – pokud limita funkce existuje, je jednoznačně určena
  - limitu funkce lze rovněž definovat pomocí posloupnosti
- aritmetika limit
  - nechť $a,A,B\in\mathbb R^*$ , nechť $f,g$ jsou funkce definované na nějakém prstencovém okolí $P(a,\delta)$ bodu $a$ , nechť platí $\lim_{x\to a}f(x)=A$ a $\lim_{x\to a}g(x)=B$
  - pak platí $\lim_{x\to a}f(x)+g(x)=A+B$ , je-li tento součet definován
  - $\lim_{x\to a}f(x)g(x)=AB$ , je-li tento součin definován
  - pokud je $g(x)$ nenulová na nějakém prstencovém okolí bodu $a$ , pak $\lim_{x\to a}f(x)/g(x)=A/B$ , je-li tento podíl definován
Limita funkce v bodě: vztah s uspořádáním
- nechť $c\in\mathbb R^*$ a funkce $f,g,h$ jsou definované na prstencovém okolí bodu $c$
- mají-li $f,g$ v bodě $c$ limitu a $\lim_{x\to c}f(x)\gt\lim_{x\to c}g(x)$ , pak existuje $\delta\gt 0$ takové, že $f(x)\gt g(x)$ pro každé $x\in P(c,\delta)$
- existuje-li $\delta\gt 0$ takové, že $f(x)\geq g(x)$ pro každé $x\in P(c,\delta)$ , a mají-li funkce $f,g$ limitu v bodě $c$ , potom $\lim_{x\to c}f(x)\geq g(x)$
- existuje-li $\delta\gt 0$ $δ > 0$ takové, že $f(x)\leq h(x)\leq g(x)$ $f (x) \leq h (x) \leq g (x)$ pro každé $x\in P(c,\delta)$ $x \in P (c, δ)$ a $\lim_{x\to c}f(x)=\lim_{x\to c}g(x)=A\in\mathbb R^*$ $lim_{x \to c} f (x) = lim_{x \to c} g (x) = A \in R^{*}$ potom i $\lim_{x\to c}h(x)=A$ $lim_{x \to c} h (x) = A$
  - v podstatě dva policajti
Limita funkce v bodě: limita složené funkce
- nechť $A,B,C\in\mathbb R^*$ , nechť $g(x)$ je funkce splňující $\lim_{x\to A}g(x)=B$ a nechť $f(x)$ je funkce splňující $\lim_{x\to B}f(x)=C$
- navíc nechť je splněna aspoň jedna z následujících podmínek
  - $f(x)$ je spojitá v $B$
  - na nějakém prstencovém okolí bodu $A$ funkce $g(x)$ nenabývá hodnotu $B$
- potom $\lim_{x\to A}f(g(x))=C$
Spojitost a spojitost na intervalu
- řekneme, že funkce $f$ $f$ je v bodě $a\in\mathbb R$ $a \in R$ spojitá, pokud $\lim_{x\to a}f(x)=f(a)$ $lim_{x \to a} f (x) = f (a)$
  - spojitost zprava/zleva definujeme pomocí jednostranných limit
- funkce je spojitá na intervalu, pokud je spojitá v každém vnitřním bodu a pokud je (odpovídajícím způsobem) jednostranně spojitá v každém krajním bodu
- funkce může být v daném bodě buď spojitá, nebo nespojitá, nebo nedefinovaná
Funkce spojité na intervalu: nabývání mezihodnot
- nechť $a\lt b$ jsou reálná čísla
- nechť $f:[a,b]\to\mathbb R$ je na intervalu $[a,b]$ spojitá
- označme $m=\min\set{f(a),f(b)}$ a $M=\max\set{f(a),f(b)}$
- pak každé reálné číslo z intervalu $[m,M]$ je hodnotou funkce $f$ (pro každé $y\in[m,M]$ existuje $x\in[a,b]$ takové, že $f(x)=y$ )
Funkce spojité na intervalu: nabývání maxima
- nechť $a\leq b$ jsou reálná čísla
- nechť $f:[a,b]\to\mathbb R$ je spojitá funkce
- potom $f$ nabývá na intervalu $[a,b]$ svého maxima (i minima)
Derivace – definice a základní pravidla pro výpočet
- nechť $f:M\to\mathbb R$ , $b\in M$ a $U(b,\delta)\subseteq M$ pro nějaké $\delta\gt 0$
- derivace funkce $f$ v bodě $b$ je limita $f'(b):=\lim_{h\to 0}\frac{f(b+h)-f(b)}{h}=\lim_{x\to b}\frac{f(x)-f(b)}{x-b}$
- také můžeme mít derivaci zprava/zleva, pak je limita jednostranná
- derivace buď existuje vlastní, nebo existuje nevlastní, nebo neexistuje
- pokud má $f$ v $b$ vlastní derivaci, říkáme, že $f$ je v $b$ diferencovatelná
- pro pravidla derivací viz libovolnou vhodnou tabulku, některá složitější jsou v přípravě na zápočtový test
L'Hospitalovo pravidlo
- nechť $a\in\mathbb R^*$ , nechť funkce $f,g:P(a,\delta)\to\mathbb R$ mají na $P(a,\delta)$ vlastní derivaci a nechť $g'(x)\neq 0$ na $P(a,\delta)$
- pokud $\lim_{x\to a}f(x)=\lim_{x\to a}g(x)=0$ a $\lim_{x\to a}f'(x)/g'(x)=A\in\mathbb R^*$ , pak i $\lim_{x\to a}f(x)/g(x)=A$
- pokud $\lim_{x\to a} |g(x)|=+\infty$ a $\lim_{x\to a}f'(x)/g'(x)=A\in\mathbb R^*$ , pak i $\lim_{x\to a}f(x)/g(x)=A$
Vyšetření průběhu funkcí: extrémy, monotonie a konvexita/konkavita
- extrémy
  - pokud má funkce $f$ v bodě $a$ nenulovou derivaci $f'(a)\neq 0$ , pak $f$ v $a$ nenabývá lokální extrém
  - tedy pokud má $f$ lokální extrém bodě $a$ , tak buď $f'(a)=0$ , nebo $f'(a)$ neexistuje
  - pozor, funkce může mít globální extrém v krajním bodě uzavřeného intervalu
- monotonie
  - uvažujeme interval s kladnou délkou a spojitou funkci $f$ s derivací v každém vnitřním bodě intervalu
  - pokud na vnitřku intervalu platí $f'\gt 0$ , je $f$ na daném intervalu rostoucí
  - pokud $f'\geq 0$ , pak je neklesající
  - pokud $f'\lt 0$ , pak je klesající
  - pokud $f'\leq 0$ , pak je nerostoucí
  - pokud $f'=0$ , pak je konstantní
- konvexita/konkavita
  - zjednodušená definice: funkce $f$ $f$ je na intervalu $(a,b)$ $(a, b)$ konvexní, pokud graf funkce na intervalu $(a,b)$ $(a, b)$ leží pod úsečkou spojující body $(a,f(a))$ $(a, f (a))$ a $(b,f(b))$ $(b, f (b))$
    - respektive pokud leží pod nebo na úsečce, tak je konvexní, pokud leží ostře pod úsečkou, tak je ryze konvexní
    - podobně konkávnost
  - pokud je druhá derivace funkce kladná, je ryze konvexní (pokud je nezáporná, je konvexní)
  - pokud je druhá derivace funkce záporná, je ryze konkávní (pokud je nekladná, je konkávní)
Taylorův polynom (limitní forma)
- Taylorův polynom řádu $n$ $n$ funkce $f$ $f$ v bodě $a$ $a$ : $T_n^{f,a}(x)=\sum_{i=0}^n\frac{f^{(i)}(a)}{i!}(x-a)^i$
  - poznámka: nultý člen součtu bude vždy $f(a)$
- má-li funkce $f$ $f$ v bodě $a\in\mathbb R$ $a \in R$ derivace všech řádů, rozumíme pro $x\in\mathbb R$ $x \in R$ její taylorovou řadou se středem v $a$ $a$ řadu $T^{f,a}(x)=\sum_{n=0}^\infty \frac{f^{(n)}(a)}{n!}(x-a)^n$
  - součet Taylorovy řady je $f(x)$
Primitivní funkce: definice a metody výpočtu (substituce, per-partes)
- nechť $-\infty\leq a\lt b\leq +\infty$ a $f:(a,b)\to\mathbb R$ je daná funkce
- pokud má funkce $F:(a,b)\to\mathbb R$ na $(a,b)$ derivaci a ta se rovná $f(x)$ , řekneme, že $F$ je na intervalu $(a,b)$ primitivní funkcí k funkci $f$
- primitivní funkce je jednoznačná až na konstantu
- Newtonův integrál funkce $f$ $f$ na intervalu $(a,b)$ $(a, b)$ definujeme jako $(N)\int_a^bf(x)\,dx:=[F]_a^b=F(b^-)-F(a^+)=\lim_{x\to b^-}F(x)-\lim_{x\to a^+}F(x)$
  - poznámka: konstanta $c$ se odečte
- substituci a per-partes je nutné nastudovat (i pro určitý integrál)
- vzorec pro per-partes: $\int u'v=uv-\int uv'$
Riemannův integrál: definice, souvislost s primitivní funkcí (Newtonovým integrálem)
- uvažujeme dělení $D=(a_0,a_1,\dots,a_k)$ $D = (a_{0}, a_{1}, \dots, a_{k})$ intervalu $[a,b]$ $[a, b]$
  - tzn. $a=a_0\lt a_1\lt a_2\lt \dots\lt a_k=b$
- definujeme dolní Riemannovu sumu $s(f,D)=\sum_{i=0}^{k-1} |I_i|m_i$ $s (f, D) = \sum_{i = 0}^{k - 1} ∣ I_{i} ∣ m_{i}$
  - $I_i=[a_i,a_{i+1}]$
  - $m_i$ je supremum funkce $f$ v intervalu $I_i$
- také definujeme horní Riemannovu sumu $S(f,D)=\sum_{i=0}^{k-1}|I_i|M_i$ $S (f, D) = \sum_{i = 0}^{k - 1} ∣ I_{i} ∣ M_{i}$
  - $M_i$ … infimum
- dolní Riemannův integrál na intervalu $[a,b]$ $[a, b]$ definujeme jako supremum z $s(f,D)$ $s (f, D)$ pro všechna dělení $D$ $D$ intervalu $[a,b]$ $[a, b]$
  - značí se $\underline{\int_a^b f}$
- horní Riemannův integrál je infimum z $S(f,D)$ $S (f, D)$
  - $\overline{\int_a^bf}$
- funkce má Riemannův integrál, pokud se horní a dolní R. integrály rovnají (pak tuhle společnou hodnotu nazveme Riemannovým integrálem)
  - $\int_a^b f$
- 1. základní věta analýzy: pokud Riemannův a Newtonův integrál existují, pak jsou si rovny
Aplikace integrálů: odhady součtu řad (konečných i nekonečných)
- pro přirozené $n$ a neklesající funkci $f$ na intervalu $[1,n]$ platí $\sum_{k=1}^{n-1}f(k)\leq\int_1^n f\leq\sum_{k=2}^n f(k)$
- integrální kritérium konvergence
  - uvažujme nerostoucí nezápornou funkci $f$
  - řada $\sum_{k=1}^\infty f(k)$ konverguje $\iff\lim_{b\to+\infty}\int_1^b f\lt +\infty$
- přesný postup pro odhad součtu řady je potřeba nacvičit
Aplikace integrálů: obsahy rovinných útvarů
- plocha rovinného útvaru $U(a,b,f)$ pod grafem funkce $f$ … $\int_a^b f$
Aplikace integrálů: objemy a povrchy rotačních útvarů v prostoru
- $V$ … rotační těleso vzniklé rotací rovinného útvaru $U(a,b,f)$ pod grafem funkce $f$ kolem osy $x$
- $\mathrm{objem}(V)=\pi\int_a^b f(t)^2\,dt$
- $\mathrm{povrch}(V)=2\pi\int_a^b f(t)\sqrt{1+(f'(t))^2}\,dt$
Aplikace integrálů: délka křivky
- uvažujeme křivku z bodu $a$ do bodu $b$ popsanou funkcí $f$
- $\int_a^b\sqrt{1+(f'(t))^2}\,dt$

2. Algebra a lineární algebra

Grupy a podgrupy, permutace
- binární operace na množině $X$ je zobrazení $X \times X \to X$
- neutrální prvek: $(\exists e \in G)(\forall a \in G): a\circ e = e\circ a = a$
- inverzní prvek: $(\forall a \in G)(\exists b \in G): a\circ b = b\circ a = e$
- grupa $(G,\circ)$ je množina $G$ spolu s binární operací $\circ$ na $G$ splňující asociativitu operace $\circ$ , existenci neutrálního prvku a existenci inverzních prvků
- pokud je navíc operace $\circ$ komutativní, pak se jedná o abelovskou grupu
- grupa $(H,\bullet)$ $(H, ∙)$ je podgrupou grupy $(G,\circ)$ $(G, \circ)$ , pokud $H\subseteq G$ $H \subseteq G$ a $\forall a,b\in H:a\bullet b=a\circ b$ $\forall a, b \in H : a ∙ b = a \circ b$
  - píšeme $(H,\bullet)\leq (G,\circ)$
- permutace na množině $\lbrace1,2,\dots,n\rbrace$ ${1, 2, \dots, n}$ je bijektivní zobrazení $p:\lbrace1,2,\dots,n\rbrace\rightarrow \lbrace1,2,\dots,n\rbrace$ $p : {1, 2, \dots, n} \to {1, 2, \dots, n}$
  - skládání permutací … $(q\circ p)(i)=q(p(i))$
  - permutační matice
    - $(P)_{i,j} = \begin{cases} 1 &\text{pokud } p(i)=j \\ 0 &\text{jinak}\end{cases}$
  - cyklus … např. $(1,2,3,4)$ $(1, 2, 3, 4)$
    - odpovídá zobrazení, které mapuje 1→2, 2→3, 3→4, 4→1
  - transpozice … permutace, která má pouze jeden netriviální cyklus o délce 2, tedy např. $(1,3)$
  - jakoukoliv permutaci lze rozložit na transpozice
    - cyklus $(1,2,3,4)$ lze rozložit na $(1,4)\circ(1,3)\circ(1,2)$ nebo na $(1,2)\circ(2,3)\circ(3,4)$
  - znaménko permutace $p$ $p$ je $\text{sgn}(p)=(-1)^{\text{počet inverzí v}\ p}$ $sgn (p) = (- 1)^{po \overset{c}{ˇ} et inverz \overset{ı}{ˊ} v p}$
    - inverze v $p$ je dvojice prvků $(i,j):i \lt j \land p(i) \gt p(j)$
    - nebo také $\text{sgn}(p)=(-1)^{\text{počet transpozic v}\ p}$
Tělesa a speciálně konečná tělesa
- těleso je množina $\mathbb K$ spolu se dvěma komutativními binárními operacemi $+$ a $\cdot$ , kde $(\mathbb K, +)$ a $(\mathbb K \setminus \lbrace0\rbrace, \cdot)$ jsou abelovské grupy a navíc platí distributivita $\forall a,b,c \in \mathbb K : a\cdot (b+c)=(a\cdot b)+(a\cdot c)$
- charakteristika tělesa
  - v tělese $\mathbb K$ , pokud $\exists n \in \mathbb N: \underbrace{1+1+\dots+1}_{n}=0$ , pak nejmenší takové $n$ je charakteristika tělesa $\mathbb K$
  - jinak má těleso $\mathbb K$ charakteristiku 0
  - značí se $\text{char}(\mathbb K)$
  - lze dokázat, že u konečných těles musí být prvočíselná
- $\mathbb Z_p$ je těleso, právě když je $p$ prvočíslo
- ale existují i konečná tělesa s neprvočíselným řádem (počtem prvků) – např. Galois field $GF(4)$ $GF (4)$
  - řád musí být kladná celá mocnina prvočísla
Soustavy lineárních rovnic – maticový zápis, elementární řádkové úpravy, odstupňovaný tvar matice
- maticový zápis soustavy rovnic
  - soustava $m$ lineárních rovnic o $n$ neznámých … $Ax = b$
  - rozšířená matice soustavy … $(A|b) \in \mathbb{R}^{m×(n+1)}$
  - matice soustavy … $A \in \mathbb{R}^{m×n}$
  - vektor pravých stran … $b \in \mathbb{R}^m$
  - vektor neznámých … $x = (x_1,\dots,x_n)^T$
  - vektor $x \in \mathbb{R}^n$ je řešení soustavy $Ax = b$ , pokud splňuje všechny její rovnice
  - soustavy $Ax = 0$ se nazývají homogenní a vždy umožňují $x = 0$
- elementární řádkové operace
  - definujeme základní dvě elementární řádkové úpravy
    - vynásobení $i$ -tého řádku nenulovým $t \in \mathbb R \setminus \lbrace0\rbrace$
    - přičtení $j$ -tého řádku k $i$ -tému řádku
  - z těch lze odvodit další dvě úpravy
    - přičtení $t$ -násobku $j$ -tého řádku k $i$ -tému řádku ( $t$ může být i nulové)
    - záměna dvou řádků
  - provedení jedné elementární úpravy značíme $A\sim A'$
  - provedení posloupnosti úprav značíme $A\sim\sim A'$
  - elementárními úpravami soustavy $(A|b)$ se nemění množina řešení
- odstupňovaný tvar matice
  - matice je v řádkově odstupňovaném tvaru (REF = row echelon form), pokud jsou nenulové řádky (ostře) seřazeny podle počtu počátečních nul a nulové řádky jsou pod nenulovými
    - k formální definici bychom zavedli notaci $j(i)$ pro pozici prvního nenulového prvku v $i$ -tém řádku
  - první nenulový prvek nenulového řádku se nazývá pivot, pod pivotem jsou v REF všechny prvky nulové
  - pro soustavu $A'x = b'$ s $A'$ v REF jsou proměnné odpovídající sloupcům s pivoty bázické, ostatní jsou volné
- redukovaný odstupňovaný tvar (RREF)
  - pivoty jsou jednotkové
  - nad i pod pivoty jsou nuly
Gaussova a Gaussova-Jordanova eliminace, popis množiny řešení
- Gaussova eliminace = převod do odstupňovaného tvaru pomocí elementárních úprav, to se dá popsat algoritmicky:
  - seřadíme řádky podle počtu počátečních nul
  - najdeme první dva řádky, co mají stejně počátečních nul
  - od toho druhého (a všech dalších, co mají stejně nul) odečteme vhodný násobek toho prvního, abychom mu první nenulu vynulovali
  - tohle opakujeme, dokud se nedostaneme do REF
- Gaussova-Jordanova eliminace = převod do RREF
  - z pivotů se jedničky dělají snadno – stačí řádek vydělit pivotem
  - nad pivoty se jedničky také dostávají snadno – stačí od řádku odečíst vhodný násobek řádku s pivotem v daném sloupci (dává smysl postupovat odspodu)
- množina řešení
  - pokud je pivot v posledním sloupci rozšířené matice soustavy, soustava rovnic nemá řešení
  - existuje bijekce $\bar x \mapsto \bar x + x^0$ $\overset{x}{ˉ} \mapsto \overset{x}{ˉ} + x^{0}$ mezi množinami $\lbrace \bar x: A\bar x=0\rbrace$ ${\overset{x}{ˉ} : A \overset{x}{ˉ} = 0}$ a $\lbrace x: Ax=b\rbrace$ ${x : A x = b}$
    - pokud $x^0$ splňuje $Ax^0=b$
  - množinu řešení soustavy $Ax=b$ popíšeme jako $x=y+p_1\overline x_1+p_2\overline x_2+\dots+p_{n-r}\overline x_{n-r}$
  - $y$ $y$ … libovolné řešení soustavy $Ax=b$ $A x = b$
    - u homogenní soustavy to typicky bude nulový vektor
    - je to člen, který odpovídá tomu $x^0$ výše
  - $p_i\overline x_i$ $p_{i} \overline{x}_{i}$
    - takový člen tam bude za každou volnou proměnnou (bude jich $n-r$ , tedy počet řádků – hodnost matice)
    - $p_i$ je libovolný reálný parametr
    - tyhle členy můžeme získat tak, že řešíme soustavu $A\overline x=0$ a řešení vyjádříme pomocí parametrů (a pak je vytkneme)
    - nebo je lze vyčíst z RREF matice
    - ve vektoru $\overline x_i$ bude typicky jednička na místě odpovídající volné proměnné a nuly u všech ostatních volných proměnných (protože je to vlastně složka, která se stará o konkrétní volnou proměnnou)
Operace s maticemi a základní typy matic, hodnost matice
- hodnost matice
  - hodnost matice A, značená jako rank(A), je počet pivotů v libovolné A' v REF takové, že $A\sim\sim A'$
- jednotková matice
  - pro $n \in \mathbb{N}$ je jednotková matice $I_n \in \mathbb{R}^{n×n}$ definovaná tak, že $(I_n)_{i,j} = 1 \iff i=j$ , ostatní prvky jsou nulové
- transponovaná matice
  - transponovaná matice k matici $A \in \mathbb{R}^{m×n}$ je matice $A^T \in \mathbb R^{n×m}$ splňující $(A^T)_{i,j}=a_{j,i}$
- symetrická matice
  - čtvercová matice A je symetrická, pokud $A^T =A$ , tedy $a_{i,j}=a_{j,i}$
- maticový součin
  - pro $A \in \mathbb R^{m\times n},B\in \mathbb R^{n\times p}$ je součin $(AB) \in \mathbb R^{m×p}$ definován $(AB)_{i,j}=\sum^{n}_{k=1}a_{i,k}b_{k,j}$
Regulární a inverzní matice
- inverzní matice
  - pokud pro čtvercovou matici $A \in \mathbb R^{n\times n}$ existuje $B \in \mathbb R^{n\times n}$ taková, že $AB=I_n$ , pak se $B$ nazývá inverzní matice a značí se $A^{-1}$
  - výpočet: $(A|I_n)\sim\sim (I_n|A^{-1})$
- regulární/singulární matice
  - pokud má matice $A$ inverzi, pak se nazývá regulární, jinak je singulární
- věta: pro čtvercovou matici $A \in \mathbb R^{n\times n}$ $A \in R^{n \times n}$ jsou následující podmínky ekvivalentní
  1. matice A je regulární, tedy k ní existuje inverzní matice … $\exists B: AB=I_n$
  2. $\text{rank}(A) = n$
  3. $A\sim\sim I_n$
  4. systém $Ax = 0$ má pouze triviální řešení $x = 0$
- inverzní matici k matici $A$ $A$ lze najít pomocí Gaussovy-Jordanovy eliminace $(A|I_n)\sim\sim(I_n|A^{-1})$ $(A ∣ I_{n}) \sim\sim (I_{n} ∣ A^{- 1})$
  - pokud tento proces selže, tak je $A$ singulární
Vektorový prostor, lineární kombinace, lineární závislost a nezávislost, lineární obal, systém generátorů
- vektorový prostor
  - vektorový prostor $(V,+,\cdot)$ nad tělesem $(\mathbb K, +,\cdot)$ je množina spolu s binární operací $+$ na $V$ a binární operací skalárního násobku $\cdot: \mathbb K \times V \rightarrow V$
  - $(V,+)$ je abelovská grupa
  - $\forall \alpha,\beta \in \mathbb K, \forall u,v \in V$ $\forall α, β \in K, \forall u, v \in V$
    - asociativita … $(\alpha \cdot \beta) \cdot u = \alpha \cdot (\beta \cdot u)$
    - neutrální prvek (skalár) vůči násobení skalárem … $1 \cdot u = u$
    - distributivita … $(\alpha + \beta) \cdot u = (\alpha \cdot u) + (\beta \cdot u)$
    - distributivita … $\alpha \cdot (u+v)=(\alpha \cdot u)+(\alpha \cdot v)$
  - prvky $\mathbb K$ se nazývají skaláry, prvky $V$ vektory
  - rozlišujeme nulový skalár $0$ a nulový vektor $o$
- podprostor vektorového prostoru
  - nechť $V$ je vektorový prostor na $\mathbb K$ , potom podprostor $U$ je neprázdná podmnožina $V$ splňující uzavřenost na součet vektorů a uzavřenost na násobení skalárem (z $\mathbb K$ ) – z toho nutně vyplývá $o \in U$
- lineární kombinace
  - lineární kombinace vektorů $v_1,\dots,v_k \in V$ nad $\mathbb K$ je libovolný vektor $u = \alpha_1v_1+\dots+\alpha_kv_k$ , kde $\alpha_1,\dots,\alpha_k \in \mathbb K$
- lineárně nezávislé vektory
  - množina vektorů $X$ je lineárně nezávislá, pokud nulový vektor nelze získat netriviální lineární kombinací vektorů z $X$ ; v ostatních případech je množina $X$ lineárně závislá
  - vektory $v_1,\dots,v_n$ jsou lineárně nezávislé $\equiv$ $\sum_{i=1}^n \alpha_iv_i=o \iff \alpha_1=\dots=\alpha_n=0$
- lineární obal (podprostor generovaný množinou)
  - lineární obal $\mathcal L(X)$ podmnožiny $X$ vektorového prostoru $V$ je průnik všech podprostorů $U$ z $V$ , které obsahují $X$
  - alternativní značení: $\mathrm{span}(X)$
  - pro $X \subseteq V$ platí $\text{span}(X)=\bigcap U:U\Subset V, X\subseteq U$
  - jde o podprostor generovaný $X$ , vektory v množině $X$ se označují jako generátory podprostoru
- věta: průnik podprostorů je taky podprostor
- věta: $\mathcal L(X)$ je množina všech lineárních kombinací vektorů z $X$
Steinitzova věta o výměně, báze, dimenze, souřadnice
- lemma o výměně
  - buď $y_1,\dots,y_n$ systém generátorů vektorového prostoru $V$
  - nechť vektor $x \in V$ má vyjádření $x = \sum_{i=1}^n\alpha_iy_i$
  - pak pro libovolné $k$ takové, že $\alpha_k \neq 0$ , je $y_1,\dots,y_{k-1},x,y_{k+1},\dots,y_n$ systém generátorů prostoru $V$
- Steinitzova věta o výměně
  - buď $V$ vektorový prostor
  - buď $x_1,\dots,x_m$ lineárně nezávislý systém ve $V$
  - nechť $y_1,\dots,y_n$ je systém generátorů $V$
  - pak platí $m\leq n$ a existují navzájem různé indexy $k_1,\dots,k_{n-m}$ takové, že $x_1,\dots,x_m,y_{k_1},\dots,y_{k_{n-m}}$ tvoří systém generátorů $V$
- báze vektorového prostoru
  - báze vektorového prostoru $V$ je lineárně nezávislá množina $X$ , která generuje $V$ (tedy $\text{span}(X)=V$ )
- dimenze vektorového prostoru
  - dimenze konečně generovaného vektorového prostoru $V$ je mohutnost (kardinalita / počet prvků) kterékoli z jeho bází; značí se $\mathrm{dim}(V)$
- vektor souřadnic
  - nechť $X=(v_1,\dots,v_n)$ je uspořádaná báze vektorového prostoru $V$ nad $\mathbb K$ , potom vektor souřadnic $u \in V$ vzhledem k bázi $X$ je $[u]_x=(\alpha_1,\dots,\alpha_n)^T \in \mathbb K^n$ , kde $u=\sum_{i=1}^n\alpha_iv_i$
Vektorové podprostory, zejména maticové (řádkový, sloupcový, jádro) a jejich dimenze
- řádkový a sloupcový prostor matice $A \in \mathbb K^{m\times n}$ $A \in K^{m \times n}$
  - sloupcový prostor $\mathcal S(A) \subseteq \mathbb K^m$ je lineární obal sloupců $A$
  - řádkový prostor $\mathcal R(A) \subseteq \mathbb K^n$ je lineární obal řádků $A$
  - $\mathcal S(A)=\lbrace u \in \mathbb K^m:u=Ax,\,x\in \mathbb K^n \rbrace$
  - $\mathcal R(A)=\lbrace v \in \mathbb K^n:v=A^Ty,\,y\in \mathbb K^m \rbrace$
- jádro matice $A \in \mathbb K^{m\times n}$ $A \in K^{m \times n}$
  - $\text{ker}(A) = \lbrace x \in \mathbb K^n: Ax=0\rbrace$
- věta: $\forall A \in \mathbb K^{m\times n}:\text{dim}(\text{ker}(A))+\text{rank}(A)=n$
- pozorování: dimenze řádkového a sloupcového prostoru se shodují (a rovnají se hodnosti)
Lineární zobrazení – definice, maticová reprezentace lineárního zobrazení, matice složeného zobrazení
- lineární zobrazení
  - nechť $U$ a $V$ jsou vektorové prostory nad stejným tělesem $\mathbb K$
  - zobrazení $f:U\rightarrow V$ $f : U \to V$ nazveme lineární, pokud splňuje $\forall u,v \in U, \forall \alpha \in \mathbb K:$ $\forall u, v \in U, \forall α \in K :$
    - $f(u+v)=f(u)+f(v)$
    - $f(\alpha\cdot u)=\alpha \cdot f(u)$ $f (α \cdot u) = α \cdot f (u)$
      - z toho vyplývá, že pro lineární zobrazení obecně platí $f(o) = o$
  - věta: lineární zobrazení je jednoznačně definováno tím, kam zobrazí vektory báze (proto můžeme definovat matici lineárního zobrazení)
- matice lineárního zobrazení
  - nechť $U$ a $V$ jsou vektorové prostory nad stejným tělesem $\mathbb K$ s bázemi $X=(u_1,\dots,u_n)$ a $Y=(v_1,\dots,v_m)$
  - matice lineárního zobrazení $f:U\rightarrow V$ vzhledem k bázím $X$ a $Y$ je $[f]_{X,Y} \in \mathbb K^{m\times n}$ , jejíž sloupce jsou vektory souřadnic obrazů vektorů báze $X$ vzhledem k bázi $Y$ , tedy $[f(u_1)]_Y,\dots,[f(u_n)]_Y$
  - pro $w \in U$ tedy platí, že $[f(w)]_Y=[f]_{X,Y}[w]_X$
- matice složeného zobrazení
  - mějme vektorové prostory $U,V,W$ s konečnými uspořádanými bázemi $B,C,D$
  - pro matice lineárních zobrazení $f:U\to V$ a $g:V\to W$ platí vztah $[g\circ f]_{B,D}=[g]_{C,D}[f]_{B,C}$
  - je to hezčí, když použijeme Hladíkovo značení: ${}_D[g\circ f]_B={}_D[g]_C\cdot{}_C[f]_B$
- matice přechodu
  - nechť $X$ a $Y$ jsou dvě konečné báze vektorového prostoru $U$
  - matice přechodu od $X$ k $Y$ je $[id]_{X,Y}$
  - pro $u \in U$ tedy platí, že $[u]_Y=[id(u)]_Y=[id]_{X,Y}[u]_X$
  - matice přechodu je regulární, platí $[id]_{Y,X}=([id]_{X,Y})^{-1}$
  - výpočet: $[id]_{X,Y}=Y^{-1}X$ nebo také $(Y|X)\sim\sim(I_n|[id]_{X,Y})$
Obraz a jádro lineárních zobrazení
- nechť $U$ a $V$ jsou vektorové prostory nad stejným tělesem $\mathbb K$
- jádro lineárního zobrazení
  - $\text{ker}(f)=\lbrace w \in U:f(w)=o\rbrace$
  - vektory v prostoru $U$ , které se zobrazí na nulový vektor v prostoru $V$
- obraz $f(U)$ podprostoru $U$ je podprostorem $V$
Isomorfismus prostorů
- vektorové prostory jsou isomorfní, pokud mezi nimi existuje isomorfismus, tedy bijektivní (vzájemně jednoznačné) lineární zobrazení
- pro isomorfismus $f$ platí, že existuje $f^{-1}$ a je také isomorfismem
- isomorfní prostory mají shodné dimenze
- věta: $f$ je isomorfismus, právě když $[f]_{X,Y}$ je regulární
Skalární součin, norma indukovaná skalárním součinem
- skalární součin pro vektorové prostory nad komplexními čísly
  - skalární součin na vektorovém prostoru $V$ $V$ nad $\mathbb C$ $C$ je zobrazení, které přiřadí každé dvojici vektorů $u,v\in V$ $u, v \in V$ skalár $\langle u|v\rangle\in\mathbb C$ $⟨ u ∣ v ⟩ \in C$ tak, že jsou splněny následující axiomy:
    - $\forall u\in V:\langle u|u\rangle\in\mathbb R^+_0$ (reálné číslo $\geq 0$ )
    - $\forall u\in V:\langle u|u\rangle=0\iff u=0$
    - $\forall u,v\in V: \langle v|u\rangle=\overline{\langle u|v\rangle}$ (komplexně sdružené)
    - $\forall u,v,w \in V: \langle u+v|w\rangle=\langle u|w\rangle+\langle v|w\rangle$
    - $\forall u,v\in V,\,\forall \alpha\in\mathbb C: \langle \alpha u|v\rangle=\alpha\langle u|v\rangle$
  - formálně je každý skalární součin zobrazení $V\times V\to\mathbb C$
  - skalární součin na $V$ nad $\mathbb R$ je zobrazení $V\times V\to\mathbb R$ , přičemž $\langle v|u\rangle = \langle u|v\rangle$ (ve třetím axiomu), $\alpha\in\mathbb R$ (v posledním axiomu)
  - standardní skalární součin na $\mathbb R^n$ : $\langle u|v\rangle=v^Tu$
  - standardní skalární součin na $\mathbb C^n$ : $\langle u|v\rangle=v^Hu$
- norma spojená se skalárním součinem
  - je-li $V$ prostor se skalárním součinem, pak norma odvozená ze skalárního součinu je zobrazení $V\to R^+_0$ přiřazující vektoru $u$ jeho normu $\|u\|=\sqrt{\langle u|u\rangle}$
  - geometrická interpretace v euklidovském prostoru $\mathbb R^n$ $R^{n}$
    - $\|u\|$ … délka (velikost) $u$
    - $\|u-v\|$ … vzdálenost bodů $u,v$
    - $\langle u|v\rangle$ $⟨ u ∣ v ⟩$ souvisí s „úhlem“ $\varphi$ $φ$ mezi $u,v$ $u, v$ a délkami $u,v$ $u, v$
      - $\langle u|v\rangle=\|u\|\cdot\|v\|\cos\varphi$
      - to vyplývá z kosinové věty, kde $a=\|u\|,\,b=\|v\|,\,c=\|u-v\|$
- kolmé vektory
  - vektory $u,v$ z prostoru se skalárním součinem jsou kolmé (ortogonální), pokud $\langle u|v\rangle=0$
  - kolmé vektory značíme $u\perp v$
Pythagorova věta, Cauchyho-Schwarzova nerovnost, trojúhelníková nerovnost
- Pythagoras: $\|a\|^2+\|b\|^2=\|c\|^2$ $∥ a ∥^{2} + ∥ b ∥^{2} = ∥ c ∥^{2}$
  - pokud $a,b$ jsou na sebe kolmé a $c=b-a$
  - ovšem taky platí $\|a+b\|^2=\|a\|^2+\|b\|^2$ , rovněž pro kolmé $a,b$
- Cauchy-Schwarz: $|\langle u|v\rangle|\leq\sqrt{\langle u|u\rangle\langle v|v\rangle}$
- trojúhelníková nerovnost: $\|u+v\|\leq\|u\|+\|v\|$
Ortonormální systémy vektorů, Fourierovy koeficienty, Gramova-Schmidtova ortogonalizace
- ortonormální báze
  - bázi $Z=\lbrace v_1,\dots,v_n \rbrace$ prostoru $V$ se skalárním součinem nazveme ortonormální, pokud platí $v_i\perp v_j$ pro každé $i\neq j$ a také $||v_i||=1$ pro každé $v_i\in Z$
  - pozorování: matice, jejichž sloupce tvoří vektory ortonormální báze $\mathbb C^n$ vzhledem ke std. skal. součinu, splňují $A^HA=I_n\implies$ jsou unitární
- Fourierovy koeficienty
  - nechť $Z=\lbrace v_1,\dots,v_n\rbrace$ je ortonormální báze prostoru $V$
  - tvrzení: pro každé $u\in V$ platí $u=\langle u|v_1\rangle v_1+\dots+\langle u|v_n\rangle v_n$
  - $\langle u|v_i\rangle$ … Fourierovy koeficienty
- algoritmus GS ortogonalizace
  - převede libovolnou bázi $(u_1,\dots,u_n)$ prostoru $V$ se skalárním součinem na ortonormální bázi $(v_1,\dots,v_n)$
  - for $i=1,\dots,n$ $i = 1, \dots, n$ do
    - $w_i\leftarrow u_i-\sum^{i-1}_{j=1}\langle u_i|v_j\rangle v_j$
    - $v_i\leftarrow \frac1{||w_i||}w_i$
  - end
Ortogonální doplněk, ortogonální projekce, projekce jako lineární zobrazení
- ortogonální doplněk
  - ortogonální doplněk podmnožiny $V$ prostoru se skalárním součinem $W$ je $V^\perp=\lbrace u\in W\mid\forall v\in V: u\perp v\rbrace$
- ortogonální projekce
  - nechť $W$ je prostor se skalárním součinem a $V$ je jeho podprostor s ortonormální bází $Z=(v_1,\dots,v_n)$
  - zobrazení $p_Z:W\to V$ definované $p_Z(u)=\sum^n_{i=1}\langle u|v_i \rangle v_i$ je ortogonální (kolmá) projekce $W$ na $V$
- pozorování: ortogonální projekce je lineární zobrazení
Ortogonální matice a jejich vlastnosti
- matice $Q\in\mathbb R^{n\times n}$ je ortogonální, pokud $Q^TQ=I_n$
- věta: $Q$ je ortogonální, právě když sloupce tvoří ortogonální bázi $\mathbb R^n$
- tvrzení: je-li $Q$ $Q$ ortogonální, pak…
  - $Q^T$ je rovněž ortogonální
  - $Q^{-1}$ existuje a je ortogonální
- součin ortogonálních matic je ortogonální matice
- další vlastnosti
  - $\braket{Qx|Qy}=\braket{x|y}$
  - $\|Qx\|=\|x\|$
  - zobrazení $x\mapsto Qx$ zachovává úhly a délky
  - platí to i naopak – matice zobrazení zachovávajícího skalární součin je ortogonální
  - $\forall i,j:|Q_{ij}|\leq 1$
  - $\begin{pmatrix}1 & o^T \\ o & Q\end{pmatrix}$ je ortogonální matice
Definice a základní vlastnosti determinantu (multiplikativnost, determinant transponované matice, vztah s regularitou a vlastními čísly)
- determinant matice $A\in\mathbb K^{n\times n}$ je dán výrazem $\text{det }A=\sum_{p\in S_n}\text{sgn}(p)\prod_{i=1}^na_{i,p(i)}$
- věta: $\forall A,B\in\mathbb K^{n\times n}:\text{det}(AB)=\text{det }A\cdot\text{det }B$
- transpozice nemění determinant, $\mathrm{det}\,A=\mathrm{det}\,A^T$
- matice je regulární, právě když má nenulový determinant
- pro regulární matici $A$ platí $\mathrm{det}(A^{-1})=\mathrm{det}(A)^{-1}$
- výpočet determinantu je nutné nastudovat
- $\mathrm{det}(A)=\lambda_1\cdot\lambda_2\cdot\ldots\cdot\lambda_n$
- $\lambda$ $λ$ je vlastním číslem $A$ $A$ , právě když $\mathrm{det}(A-\lambda I_n)=0$ $det (A - λ I_{n}) = 0$
  - tedy právě když je kořenem charakteristického polynomu $p_A(t)=\mathrm{det}(A-tI_n)$
Laplaceův rozvoj determinantu
- notace: $A^{ij}$ je podmatice získaná z $A$ odstraněním $i$ -tého řádku a $j$ -tého sloupce
- věta: pro libovolné $A\in\mathbb K^{n\times n}$ a jakékoli $i\in \lbrace 1,\dots,n\rbrace$ platí $\text{det }A=\sum^n_{j=1}a_{ij}(-1)^{i+j}\text{ det }A^{ij}$
Geometrická interpretace determinantu
- objem rovnoběžnostěnu určeného $k$ vektory je roven absolutní hodnotě determinantu matice, jejíž sloupce tyto vektory tvoří
- po provedení lineárního zobrazení se objemy těles změní úměrně absolutní hodnotě determinantu matice zobrazení
Definice, geometrický význam a základní vlastnosti vlastních čísel, charakteristický polynom, násobnost vlastních čísel
- definice
  - mějme matici $A\in\mathbb C^{n\times n}$
  - vlastní číslo matice $A$ je jakékoliv $\lambda\in\mathbb C$ , pro které existuje vektor $x\in\mathbb C^n\setminus \lbrace o\rbrace$ takový, že $Ax=\lambda x$
  - $x$ je pak vlastní vektor příslušný vlastnímu číslu $\lambda$
- geometrie
  - vlastní vektor reprezentuje invariantní směr při zobrazení $x\mapsto Ax$ , tedy směr, který se zobrazí opět na ten samý směr
  - vlastní číslo odpovídá škálování v tomto invariantním směru
- základní vlastnosti
  - determinant matice je roven součinu vlastních čísel
  - stopa matice (součet diagonály) je roven součtu vlastních čísel
  - matice je regulární, právě když nula není její vlastní číslo
  - $A^T$ má stejná vlastní čísla jako $A$ , ale vlastní vektory obecně jiné
  - uvažujeme matici $A\in\mathbb C^{n\times n}$ $A \in C^{n \times n}$ s vlastními čísly $\lambda_1,\dots,\lambda_n$ $λ_{1}, \dots, λ_{n}$ a jim odpovídajícími vlastními vektory $x_1,\dots,x_n$ $x_{1}, \dots, x_{n}$
    - je-li $A$ regulární, pak $A^{-1}$ má vlastní čísla $\lambda_1^{-1},\dots,\lambda_n^{-1}$ a vlastní vektory $x_1,\dots,x_n$
    - $A^2$ má vlastní čísla $\lambda_1^{2},\dots,\lambda_n^{2}$ a vlastní vektory $x_1,\dots,x_n$
    - podobně pro $\alpha A$ a taky pro $A+\alpha I_n$
- charakteristický polynom … $p_A(t)=\mathrm{det}(A-tI_n)$ $p_{A} (t) = det (A - t I_{n})$
  - vlastní čísla matice $A$ jsou právě kořeny jejího charakteristického polynomu a je jich $n$ včetně násobností
- algebraická násobnost $\lambda$ je rovna násobnosti $\lambda$ jakožto kořene $p_A$
- geometrická násobnost $\lambda$ je rovna $n-\mathrm{rank}(A-\lambda I_n)$ , tj. počtu lineárně nezávislých vlastních vektorů, které odpovídají $\lambda$
- algebraická násobnost $\geq$ $\geq$ geometrická násobnost
  - obvykle se násobností myslí ta algebraická
Podobnost a diagonalizovatelnost matic, spektrální rozklad
- matice $A,B\in\mathbb C^{n\times n}$ jsou podobné, pokud existuje regulární $S\in\mathbb C^{n\times n}$ tak, že $A=SBS^{-1}$
- věta: podobné matice mají stejná vlastní čísla
  - počet vlastních vektorů pro konkrétní vlastní číslo je stejný u obou matic
- matice $A\in\mathbb C^{n\times n}$ je diagonalizovatelná, je-li podobná nějaké diagonální matici
- diagonalizovatelná matice $A$ $A$ jde tedy vyjádřit ve tvaru $A=S\Lambda S^{-1}$ $A = S Λ S^{- 1}$ , kde $S$ $S$ je regulární a $\Lambda$ $Λ$ diagonální
  - tomuto se říká spektrální rozklad
  - sloupce matice $S$ odpovídají vlastním vektorům (v pořadí, v němž jsou vlastní čísla na diagonále $\Lambda$ )
- věta: matice $A\in\mathbb C^{n\times n}$ je diagonalizovatelná, právě když má $n$ lineárně nezávislých vlastních vektorů
- věta: pokud má matice $n$ navzájem různých vlastních čísel, pak je diagonalizovatelná
- $A^2=S\Lambda^2 S^{-1}$
Symetrické matice, jejich vlastní čísla a spektrální rozklad
- matice je symetrická, pokud $A=A^T$
- vlastní čísla reálných symetrických matic jsou reálná
- věta: pro každou symetrickou matici $A\in\mathbb R^{n\times n}$ existuje ortogonální $Q\in\mathbb R^{n\times n}$ a diagonální $\Lambda\in\mathbb R^{n\times n}$ takové, že $A=Q\Lambda Q^T$
Positivně semidefinitní a positivně definitní matice – charakterizace a vlastnosti, vztah se skalárním součinem, vlastními čísly
- definice
  - buď $A\in\mathbb R^{n\times n}$ symetrická
  - pak $A$ je positivně semidefinitní, pokud $x^TAx\geq 0$ pro všechna $x\in\mathbb R^n$
  - $A$ je positivně definitní, pokud $x^TAx\gt 0$ pro všechna $x\neq o$
- poznámka: nesymetrické matice můžeme symetrizovat úpravou $\frac12(A+A^T)$
- následující tří vlastnosti jsou ekvivalentní
  - $A$ je positivně semidefinitní (nebo definitní)
  - vlastní čísla $A$ $A$ jsou nezáporná
    - pro definitní musí být kladná
  - existuje matice $U\in\mathbb R^{m\times n}$ $U \in R^{m \times n}$ taková, že $A=U^TU$ $A = U^{T} U$
    - pro definitní musí mít matice $U$ hodnost $n$
- vlastnosti
  - jsou-li $A,B$ positivně definitní, pak i $A+B$ je p. d.
  - je-li $A$ positivně definitní a $\alpha\gt 0$ , pak i $\alpha A$ je p. d.
  - je-li $A$ positivně definitní, pak je regulární a $A^{-1}$ je p. d.
- operace $\braket{x|y}$ je skalárním součinem v $\mathbb R^n$ , právě když má tvar $\braket{x|y}=x^TAy$ pro nějakou positivně definitní matici $A\in\mathbb R^{n\times n}$
- testování p. d. pomocí Gaussovy eliminace
  - používáme pouze úpravu přičtení násobku řádku s pivotem k jinému řádku pod ním
  - pokud nám vyjde odstupňovaný tvar s kladnou diagonálou, byla původní matice positivně definitní
Choleského rozklad (znění věty a praktické použití)
- pro každou positivně definitní matici $A\in\mathbb R^{n\times n}$ existuje jediná dolní trojúhelníková matice $L\in\mathbb R^{n\times n}$ s kladnou diagonálou taková, že $A=LL^T$
- algoritmus vypadá složitě, ale dá se to vymyslet intuitivně (je vhodné začít tím, že první prvek matice $A$ je druhou mocninou čísla, které je v obou trojúhelníkových maticích vlevo nahoře)
- praktické použití
  - řešíme soustavu $Ax=b$
  - máme Choleského rozklad $A=LL^T$
  - snadno najdeme řešení soustavy $Ly=b$ (díky nulám v trojúhelníkové matici stačí substituovat)
  - pak najdeme řešení soustavy $L^Tx=y$
  - proč to funguje?
    - $L(\underbrace{L^Tx}_{=y})=b$

3. Diskrétní matematika

Relace, vlastnosti binárních relací (reflexivita, symetrie, antisymetrie, tranzitivita)
- (binární) relace mezi množinami $X,Y$ je podmnožina $X\times Y$
- relace na množině $X$ je podmnožina $X^2$
- značení – pro relaci $R$ mezi $X,Y:xRy \equiv (x,y)\in R$
- příklady relací
  - prázdná $\emptyset$
  - univerzální $X\times Y$
  - diagonální $\Delta_X := \lbrace (x,x)\mid x\in X\rbrace$ , např. rovnost $x=y$
- operace s relacemi
  - inverze
    - k relaci $R$ mezi $X,Y$ lze definovat inverzní relaci $R^{-1}$ mezi $Y,X$ , přičemž $R^{-1} := \lbrace(y,x)\mid (x,y)\in R\rbrace$
  - skládání
    - pro relaci $R$ mezi $X,Y$ a relaci $S$ mezi $Y,Z$ lze definovat složenou relaci $T=R\circ S$ mezi $X,Z$
    - $xTz \equiv \exists y \in Y: xRy \land ySz$
    - $R\circ \Delta_Y =R,\quad \Delta_X\circ R = R$
    - značení skládání funkcí: $(f\circ g)(x)=g(f(x))$
- relace $R$ $R$ na $X$ $X$ je…
  - reflexivní $\equiv \forall x \in X: xRx$ $\equiv \forall x \in X : x R x$
    - $\Delta_X \subseteq R$
  - symetrická $\equiv \forall x,y \in X: xRy \implies yRx$ $\equiv \forall x, y \in X : x R y ⟹ y R x$
    - $R=R^{-1}$
  - antisymetrická $\equiv \forall x,y \in X: xRy \land yRx \implies x=y$ $\equiv \forall x, y \in X : x R y \land y R x ⟹ x = y$
    - $R\cap R^{-1}\subseteq \Delta_X$
  - tranzitivní $\equiv \forall x,y,z \in X: xRy \land yRz \implies xRz$ $\equiv \forall x, y, z \in X : x R y \land y R z ⟹ x R z$
    - $R\circ R \subseteq R$
Ekvivalence a rozkladové třídy
- relace $R$ $R$ na $X$ $X$ je ekvivalence $\equiv R$ $\equiv R$ je reflexivní & symetrická & tranzitivní
  - např. rovnost čísel, rovnost mod $K$ , geometrická podobnost
- ekvivalenční třída prvku $x \in X:R[x]=\lbrace y \in X \mid xRy\rbrace$
- množinový systém $\mathcal S\subseteq 2^X$ $S \subseteq 2^{X}$ je rozklad množiny $X \equiv$ $X \equiv$
  - $\forall A \in \mathcal S: A \neq \emptyset$
  - $\forall A,B\in \mathcal S: A\neq B \implies A \cap B = \emptyset$
  - $\bigcup_{A\in \mathcal S}A=X$
- věta (vztah mezi ekvivalencemi a rozklady)
  1. $\forall x \in X: R[x]\neq \emptyset$
  2. $\forall x,y \in X:$ buď $R[x]=R[y]$ , nebo $R[x] \cap R[y]=\emptyset$
  3. $\lbrace R[x] \mid x \in X\rbrace$ (množina všech ekvivalenčních tříd) určuje ekvivalenci R jednoznačně
Částečná uspořádání – základní pojmy (minimální a maximální prvky, nejmenší a největší prvky, řetězec, antiřetězec)
- relace $R$ na množině $X$ je (částečné) uspořádání $\equiv R$ je reflexivní & antisymetrická & tranzitivní
- (částečně) uspořádaná množina $(X,R)$ $(X, R)$
  - zkráceně ČUM
  - $R$ je (částečné) uspořádání na $X$
- prvky $x,y \in X$ jsou porovnatelné $\equiv xRy \lor yRx$
- uspořádání je lineární $\equiv \forall x,y\in X$ $\equiv \forall x, y \in X$ porovnatelné
  - (všechny prvky množiny jsou navzájem porovnatelné)
- částečné uspořádání (nebo pouze uspořádání) je obecný pojem, některá taková uspořádání jsou navíc lineární
- ostré uspořádání – každému uspořádání $\leq$ $\leq$ na X přiřadíme relaci $<$ $<$ na X: $a < b \equiv a \leq b \land a \neq b$ $a < b \equiv a \leq b \land a \neq = b$
  - pozor – ostré uspořádání není speciálním případem uspořádání (protože není reflexivní)
  - vlastnosti ostrého uspořádání – ireflexivní, antisymetrické, tranzitivní
- Hasseův diagram graficky zachycuje vztahy mezi prvky ČUM (porovnatelné prvky jsou spojeny, větší prvky jsou výše)
- prvek $x\in X$ je nejmenší $\equiv \forall y \in X: x\leq y$
- prvek $x\in X$ je minimální $\equiv \nexists y \in X: y\lt x$
- $x$ je nejmenší $\implies$ $x$ je minimální
- v Hassově diagramu
  - z minimálního prvku dolů nevede žádná spojnice
  - nejmenší prvek je nejníž v diagramu, existuje do něj cesta z libovolného jiného prvku
- věta: konečná neprázdná uspořádaná množina má minimální a maximální prvek
- pro $(X,\leq)$ $(X, \leq)$ ČUM:
  - $A\subseteq X$ je řetězec $\equiv \forall a,b \in A: a,b$ jsou porovnatelné
  - $A \subseteq X$ je antiřetězec (nezávislá množina) $\equiv \nexists a,b$ různé & porovnatelné
Výška a šířka částečně uspořádané množiny a věta o jejich vztahu (o dlouhém a širokém)
- $\omega(X,\leq)$ je délka nejdelšího řetězce = maximum z délek řetězců (výška uspořádání)
- $\alpha(X,\leq)$ je délka nejdelšího antiřetězce (šířka uspořádání)
- věta: pro každou konečnou ČUM $(X,\leq)$ platí $\alpha(X,\leq)\cdot \omega(X,\leq)\geq |X|$
- důsledek: $\text{max}(\alpha,\omega)\geq\sqrt{|X|}$
Funkce, typy funkcí (prostá, na, bijekce)
- funkce z množiny $X$ do množiny $Y$ je relace $A$ mezi $X$ a $Y$ t. ž. $(\forall x\in X)(\exists! y\in Y):xAy$
- funkce $f:X\to Y$ $f : X \to Y$ je…
  - prostá (injektivní) $\equiv \nexists x,x' \in X: x \neq x' \land f(x)=f(x')$
  - na $Y$ (surjektivní) $\equiv (\forall y \in Y)(\exists x \in X): f(x)=y$
  - vzájemně jednoznačná (bijektivní) $\equiv (\forall y \in Y)(\exists! x \in X):f(x)=y$ $\equiv (\forall y \in Y) (\exists! x \in X) : f (x) = y$
    - taková funkce je tedy prostá i „na“
    - k takové funkci existuje inverzní funkce $f^{-1}$ z $Y$ do $X$
Počty různých typů funkcí mezi dvěma konečnými množinami
- věta: počet $f:N\to M=m^n$ $f : N \to M = m^{n}$
  - pro $|N|=n, |M|=m;\quad m,n\gt 0$
- definice: klesající mocnina
  - $m^{\underline n}=\underbrace{m\cdot (m-1)\cdot (m-2)\cdot\ldots\cdot(m-n+1)}_n$
  - tedy $m^{\underline n}=\frac{m!}{(m-n)!}$
- věta: počet prostých $f:N\to M=m^{\underline{n}}$
- počet surjektivních zobrazení lze určit pomocí principu inkluze a exkluze
- bijekcí je $n!$
- počet uspořádaných $k$ -tic $|X^k|=|X|^k$ , lze jej totiž vyjádřit jako počet funkcí $f:[k]\to X$
Permutace a jejich základní vlastnosti (počet a pevný bod)
- definice: $[n]=\lbrace1,2,\dots,n\rbrace$
- věta: na množině $[n]$ existuje $n!$ permutací (podobně na každé n-prvkové množině)
- pevný bod permutace je prvek, který se zobrazí sám na sebe
Kombinační čísla a vztahy mezi nimi, binomická věta a její aplikace
- kombinační číslo (binomický koeficient) ${n\choose k}:={n^{\underline k} \over k!}={n!\over k!(n-k)!}$
- Pascalův trojúhelník – n roste shora dolů, k zleva doprava
- $X\choose k$ … množina všech k-prvkových podmnožin množiny $X$
- ${n\choose k} = {n\choose n-k}$ $(k n) = (n - k n)$ … každé k-prvkové podmnožině přiřadíme její doplněk
  - Pascalův trojúhelník je symetrický
- ${n-1\choose k-1}+{n-1\choose k}={n\choose k}$ $(k - 1 n - 1) + (k n - 1) = (k n)$
  - zvolíme jeden prvek $a$ a rozdělíme všechny k-prvkové podmnožiny podle toho, zda obsahují $a$ , nebo ne
  - buňka v Pascalově trojúhelníku je součtem dvou buněk nad ní (pokud není na kraji)
- Binomická věta: $(x+y)^n=\sum_{i=0}^n{n\choose i}x^{n-i}y^i$
- aplikace
  - řádek Pascalova trojúhelníku se sečte na $2^n=(1+1)^n=\sum_{k=0}^n\binom{n}{k}$
  - důkaz $(x^n)'=nx^{n-1}$ $(x^{n})^{'} = n x^{n - 1}$
    - použijeme $f(x+h)=(x+h)^n=x^n+nx^{n-1}h+\binom n2 x^{n-2}h^2+\dots+h^n$
    - dosadíme do $\lim_{h\to 0}\frac{f(x+h)-f(x)}{h}$
  - $e=\lim\,(1+\frac1n)^n$
Princip inkluze a exkluze: obecná formulace (a důkaz)
- konkrétní ukázky principu inkluze a exkluze (PIE)
  - $|A\cup B|=|A|+|B|-|A\cap B|$
  - $|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$
- věta: pro konečné množiny $A_1,\dots,A_n$ platí $|\bigcup_{i=1}^nA_i|=\sum_{k=1}^n(-1)^{k+1}\sum_{I\in{[n]\choose k}}|\bigcap_{i\in I}A_i|$
- důkaz
  - pro prvek $x$ ve sjednocení spočítáme příspěvky k levé (vždy 1) a pravé straně
  - nechť $x$ patří do právě $t$ množin
  - průniky $k$ $k$ -tic
    - $k \gt t$ … přispěje $0$
    - $k\leq t$ $k \leq t$ … přispěje $(-1)^{k+1}{t\choose k}$ $(- 1)^{k + 1} (k t)$
      - vybíráme $k$ -tice množin z $t$ -množin, do kterých prvek patří
      - minus jednička vychází ze vzorce
    - chceme $\sum_{k=1}^t(-1)^{k+1}{t\choose k}=1$
    - lze upravit na $\sum_{k=1}^t(-1)^{k}{t\choose k}=-1$
    - z binomické věty $0=(1-1)^t=\sum_{k=0}^t{t\choose k}(-1)^{k}$
    - tedy bez prvního členu se součet rovná $-1\quad \square$
Princip inkluze a exkluze: použití (problém šatnářky, Eulerova funkce pro počet dělitelů, počet surjekcí)
- problém šatnářky
  - Šatnářka $n$ pánům vydá náhodně $n$ klobouků (které si předtím odložili v šatně). Jaká je pravděpodobnost, že žádný pán nedostane od šatnářky zpět svůj klobouk?
  - jaká je pravděpodobnost, že náhodně zvolená permutace nebude mít žádný pevný bod
    - každá z $n!$ permutací je stejně pravděpodobná
    - $š(n)$ … počet permutací bez pevného bodu
    - pravděpodobnost je rovna $š(n)/n!$
  - $S_n$ … množina všech permutací
  - $A_i=\lbrace \pi \in S_n \mid \pi(i)=i\rbrace$ $A_{i} = {π \in S_{n} ∣ π (i) = i}$
    - množina permutací s pevným bodem v $i$ -tém prvku (jedna permutace může patřit do více takových množin)
  - $A=\bigcup_{i=1}^n A_i$ … (množina všech „špatných“ permutací)
  - musíme vyjádřit velikosti průniků
    - permutací s (konkrétními) $k$ pevnými body je $(n-k)!$ , protože permutuji všechny prvky kromě těch pevných
  - dosazením do principu inkluze a exkluze vyjde $|A|=\sum_{k=1}^n(-1)^{k+1}{n\choose k}(n-k)!$ $∣ A ∣ = \sum_{k = 1}^{n} (- 1)^{k + 1} (k n) (n - k)!$
    - $n\choose k$ vyplývá z počtu prvků druhé sumy
    - ${n\choose k}(n-k)!={n!\over k!}$
  - $|A|=\sum_{k=1}^n(-1)^{k+1}\frac{n!}{k!}=n!\cdot\sum_{k=1}^n{(-1)^{k+1}\over k!}$
  - $|A|=n!({1\over 1!}-{1\over 2!}+{1\over 3!}-\dots+{(-1)^{n+1}\over n!})$
  - $š(n)=n!-|A|=n!\cdot(1-{1\over 1!}+{1\over 2!}-{1\over 3!}+\dots+{(-1)^n\over n!})$ $\overset{s}{ˇ} (n) = n! - ∣ A ∣ = n! \cdot (1 - \frac{1}{1 !} + \frac{1}{2 !} - \frac{1}{3 !} + \dots + \frac{( - 1 ) ^{n}}{n !})$
    - závorka konverguje k $e^{-1}$
    - závorka odpovídá pravděpodobnosti v problému šatnářky
  - $š(n)=n!\cdot\sum_{k=0}^n\frac{(-1)^k}{k!}$
  - pravděpodobnost … $\sum_{k=0}^n\frac{(-1)^k}{k!}\approx e^{-1}$
- Eulerova funkce $\varphi(n)$ $φ (n)$
  - je to počet čísel z $[n]$ $[n]$ nesoudělných s $n$ $n$
    - pro prvočíslo $p$ platí $\varphi(n)=p-1$ , protože je soudělné samo se sebou a protože podle definice nesoudělnosti (NSD = 1) není soudělné s jedničkou
  - tvrzení: nechť $n=p_1^{e_1}\cdot p_2^{e_2}\cdot\ldots\cdot p_k^{e_k}$ je prvočíselný rozklad, pak $\varphi(n)=n(1-\frac{1}{p_1})(1-\frac1{p_2})\dots(1-\frac1{p_k})$
  - důkaz
    - jako $A_i$ označím množinu čísel z $[n]$ soudělných $i$ -tým prvočíslem $p_i$
    - zjevně $\varphi(n)=n-|\bigcup_{i=1}^k A_i|$
    - $|A_i|=\frac n{p_i}$
    - pro různé $i,j\in[k]$ platí $|A_i\cap A_j|=\frac n{p_ip_j}$
    - to se dá zobecnit na průnik více množin
    - dle PIE $|\bigcup_{i=1}^kA_i|=\sum_{I\in 2^{[n]}\setminus\set\emptyset}(-1)^{|I|+1}\frac{n}{\prod_{i\in I} p_i}$
    - $=n(\frac1{p_1}+\dots+\frac1{p_k}-\frac1{p_1p_2}-\dots+\frac1{p_1p_2p_3}+\dots+(-1)^{k+1}\frac1{p_1\dots p_k})$
    - proto $\varphi(n)=n(1-\frac1{p_1}-\dots-\frac1{p_k}+\frac{1}{p_1p_2}+\dots+(-1)^k\frac1{p_1\dots p_k})$
    - tedy $\varphi(n)=n(1-\frac{1}{p_1})(1-\frac1{p_2})\dots(1-\frac1{p_k})\quad\square$ $φ (n) = n (1 - \frac{1}{p _{1}}) (1 - \frac{1}{p _{2}}) \dots (1 - \frac{1}{p _{k}}) □$
      - z každé závorky vždy vybíráme levý nebo pravý člen
- počet surjekcí
  - věta
    - nechť $X,Y$ jsou konečné množiny, $|X|=n$ , $|Y|=m$ , $n\geq m\gt 0$
    - potom počet zobrazení $f$ množiny $X$ na množinu $Y$ je $\sum_{k=0}^m(-1)^k\binom mk(m-k)^n$
  - důkaz
    - počet všech funkcí z $X$ do $Y$ je $m^n$
    - definujeme $F_i$ jako množinu zobrazení, že $i$ -tý prvek z množiny $Y$ není pokrytý (neexistuje $x\in X$ , aby $f(x)=y_i$ , kde $y_i$ je $i$ -tý prvek z $Y$ )
    - takže počet surjekcí bude $m^n-|\bigcup_{i=1}^m F_i|$
    - použijeme PIE: $|\bigcup_{i=1}^mF_i|=\sum_{k=1}^m(-1)^{k+1}\sum_{I\in{[m]\choose k}}|\bigcap_{i\in I}F_i|$
    - $=\sum_{k=1}^m(-1)^{k+1}\binom mk(m-k)^n$ $= \sum_{k = 1}^{m} (- 1)^{k + 1} (k m) (m - k)^{n}$
      - $(m-k)^n$ dostaneme tak, že uvažujeme funkce z $n$ -prvkové množiny do množiny s $m-k$ prvky (na vybraných $k$ bodů naše funkce nesmí směřovat)
    - počet surjekcí $m^n-|\bigcup_{i=1}^m F_i|=m^n-\sum_{k=1}^m(-1)^{k+1}\binom mk(m-k)^n$ pak ještě upravíme do finálního tvaru $\quad\square$
Hallova věta o systému různých reprezentantů a její vztah k párování v bipartitním grafu, princip důkazu a algoritmické aspekty (polynomiální algoritmus pro nalezení SRR)
- párování je taková množina hran, kde žádné dvě hrany nemají společný vrchol
  - maximální párování je takové párování, které má nejvíce hran
  - perfektní párování je takové párování, které pokrývá všechny vrcholy grafu
- systém různých reprezentantů v hypergrafu
  - systém různých reprezentantů (SRR) v hypergrafu $H=(V,E)$ $H = (V, E)$ je funkce $r:E\to V$ $r : E \to V$ taková, že
    - $\forall e\in E: r(e)\in e$
    - $\forall e,f\in E:e\neq f\implies r(e)\neq r(f)$ … tj. $r$ je prostá
  - $r(e)$ … „reprezentant hyperhrany $e$ “
  - analogie s předsedy spolků
- pozorování: v bipartitním grafu s partitami $A,B$ má každé párování velikost nejvýše $|A|$ (i nejvýše $|B|$ )
- definice: pro graf $G=(V,E)$ a množinu $X\subseteq V$ označím $N(X):=\set{y\in V\setminus X: (\exists x\in X)\set{x,y}\in E}$
- Hallova věta, bipartitní grafová verze
  - nechť $G$ je bipartitní graf s partitami $A,B$ , potom $G$ má párování velikosti $|A|$ $\iff\underbrace{\forall X\subseteq A:|N(X)|\geq |X|}_{\text{„Hallova podmínka“}}$
- důkaz
  - $\implies$ $⟹$
    - pokud existuje párování velikosti $|A|$ , tak pro každou $X\subseteq A$ existuje $|X|$ vrcholů spárovaných s $X$ , ty patří do $N(X)$ , tedy $|N(X)|\geq |X|$
  - $\impliedby$ $⟸$
    - nechť $M$ je největší párování v $G$
    - pro spor nechť $|M|\lt|A|$
    - dle Kőnigovy–Egerváryho věty existuje pokrytí $C$ , kde $|C|=|M|\lt |A|$
    - $C_A:= C\cap A$
    - $C_B:=C\cap B$
    - $X:=A\setminus C_A$
    - zjistím, že $N(X)\subseteq C_B$ $N (X) \subseteq C_{B}$
      - protože nepokryté hrany musí pokrývat vrcholy v $N(X)$
    - navíc $|X|=|A|-|C_A|\gt |C_B|\geq |N(X)|$ $∣ X ∣ = ∣ A ∣ - ∣ C_{A} ∣ > ∣ C_{B} ∣ \geq ∣ N (X) ∣$
      - jelikož $|C|\lt|A|\implies |A|\gt|C_A|+|C_B|$
    - to je spor s Hallovou podmínkou
  - idea $\impliedby$ $⟸$
    - uvažujeme ostře menší párování, tedy podle Kőnigovy–Egerváryho věty musí existovat i menší pokrytí
      - věta říká, že velikost maximální párování se rovná velikosti minimálního pokrytí (jako u toku a řezu)
    - prohlásíme, že vrcholy v $X$ nejsou v pokrytí, tak ty hrany mezi nimi a $N(X)$ musí pokrývat vrcholy v $N(X)$ , ale těch by pak bylo málo (méně než požaduje Hallova podmínka)
    - takže jsme dokázali obměnu implikace
- pozorování: jakmile uvnitř hypergrafu je množina čtyř hyperhran, které ve svém sjednocení mají tři vrcholy, tak nemůžu najít systém různých reprezentantů
  - platí to obecně pro množinu $k$ hyperhran – když budou mít ve sjednocení méně než $k$ vrcholů, tak nenajdu SRR
  - implikace platí i obráceně, lze vyslovit jako větu
- Hallova věta, hypergrafová verze
  - hypergraf $H=(V,E)$ má SRR, právě když $\forall F\subseteq E:\left|\bigcup_{e\in F} e\right|\geq |F|$
- důkaz
  - nechť $H=(V,E)$ je hypergraf, nechť $I_H$ je jeho graf incidence
  - $H$ má SRR $\iff$ $I_H$ má párování velikosti $|E|$
  - Hallova podmínka pro $H$ : $\forall F\subseteq E: \left|\bigcup_{e\in F}e\right|\geq |F|\iff$ bipartitní Hallova podmínka pro $I_H$ a partitu $E$
- algoritmické aspekty
  - maximální párování lze najít v polynomiálním čase
  - proto i SRR lze najít v polynomiálním čase

4. Teorie grafů

Základní pojmy teorie grafů – graf, vrcholy a hrany, izomorfismus grafů, podgraf, okolí vrcholu a stupeň vrcholu, doplněk grafu, bipartitní graf
- graf je $(V, E)$ $(V, E)$ , kde $V$ $V$ je konečná neprázdná množina vrcholů a $E \subseteq {V \choose 2}$ $E \subseteq (2 V)$ je množina hran
  - lze značit jako $G=(V,E)$ , potom $V(G)$ je množina vrcholů a $E(G)$ je množina hran
- izomorfismus
  - grafy jsou izomorfní $\equiv$ existuje bijekce, která zachovává vlastnost být spojen hranou
  - v podstatě stačí přejmenovat vrcholy a dostaneme dva stejné grafy
  - značení $\cong$
  - $\cong$ $≅$ je ekvivalence na libovolné množině grafů
    - neexistuje množina všech grafů (protože neexistuje množina všech množin)
- podgraf
  - graf $G'=(V',E')$ je podgrafem grafu $G=(V,E)$ (značíme $G'\subseteq G$ ), když $V'\subseteq V \land E'\subseteq E$
  - graf $G'=(V',E')$ $G^{'} = (V^{'}, E^{'})$ je indukovaným podgrafem grafu $G=(V,E)$ $G = (V, E)$ , když $V'\subseteq V \land E'= E\cap {V'\choose 2}$ $V^{'} \subseteq V \land E^{'} = E \cap (2 V ^{'})$
    - „podgraf indukovaný množinou vrcholů“
    - $G[A] := (A, E(G) \cap {A \choose 2})$ , kde $A\subseteq V(G)$
- okolí vrcholu
  - okolí vrcholu $v$ jsou ty vrcholy, které s vrcholem $v$ sousedí (sdílejí hranu)
  - $N_G(v)=\set{u\in V(G):\exists uv\in E(G)}$
- stupeň vrcholu
  - stupeň vrcholu – počet hran, kterých se účastní daný vrchol
  - graf je k-regulární, pokud je stupeň všech vrcholů grafu roven k
  - skóre grafu = posloupnost stupňů vrcholů (až na pořadí) → jakmile dvěma grafům vyjde jiné skóre, nemohou být izomorfní
- doplněk grafu
  - doplněk/komplement grafu $G$ je graf $G_0$ , který má stejné vrcholy jako $G$ , ale má právě ty hrany, které v grafu $G$ chybí
- bipartitní graf
  - graf (V, E) je bipartitní $\equiv \exists L,P\subseteq V$ $\equiv \exists L, P \subseteq V$ t. ž.:
    - $L \cup P = V$
    - $L \cap P = \emptyset$
    - $\forall e \in E: |e \cap L| = 1\quad (\land\ |e \cap P| = 1)$ $\forall e \in E : ∣ e \cap L ∣ = 1 (\land ∣ e \cap P ∣ = 1)$
      - nebo $E(G)\subseteq\lbrace\lbrace x,y\rbrace\mid x\in L,y\in P\rbrace$
  - partity grafu – jednotlivé „strany“
Základní příklady grafů – úplný graf a úplný bipartitní graf, cesty a kružnice
- úplný graf $K_n$ $K_{n}$
  - $V(K_n):=[n]$
  - $E(K_n):={V(K_n)\choose 2}$
- úplný bipartitní $K_{m,n}$ $K_{m, n}$
  - každý prvek nalevo je spojený s každým napravo
  - prvky na jedné straně mezi sebou nejsou spojeny
- prázdný graf $E_n$ $E_{n}$
  - $V(E_n):=[n]$
  - $E(E_n) =\emptyset$
- cesta $P_n$ $P_{n}$
  - $V(P_n):=\{0,\dots, n\}$
  - $E(P_n):=\{\{i,i+1\}\mid 0\leq i \lt n\}$
  - délka cesty se měří v počtu hran
- kružnice/cyklus $C_n$ $C_{n}$
  - $n\geq 3$
  - $V(C_n):=\{0,\dots, n–1\}$
  - $E(C_n):=\{\{i,(i+1)\bmod n\}\mid 0\leq i \lt n\}$
Souvislost grafů, komponenty souvislosti, vzdálenost v grafu
- graf $G$ je souvislý $\equiv\forall u,v\in V(G):$ existuje cesta v $G$ s krajními vrcholy $u,v$
- dosažitelnost v $G$ $G$ je relace $\sim$ $\sim$ na $V(G)$ $V (G)$ t. ž. $u\sim v\equiv$ $u \sim v \equiv$ existuje cesta v $G$ $G$ s krajními vrcholy $u,v$ $u, v$
  - relace $\sim$ je ekvivalence
  - tranzitivita se dokazuje pomocí dvou posloupností vrcholů $x \sim y$ a $y\sim z$ a následně zvolení nejzazšího vrcholu z posloupnosti $y\sim z$ , který je obsažen v posloupnosti $x\sim y$ a v tomto vrcholu se posloupnosti slepí (přičemž části za ním v první posloupnosti a před ním v druhé posloupnosti se ustřihnou)
- komponenty souvislosti jsou podgrafy indukované třídami ekvivalence $\sim$ $\sim$
  - komponenty jsou souvislé
  - graf je souvislý $\iff$ má 1 komponentu
- vzdálenost (grafová metrika) v souvislém grafu $G$ $G$
  - $d_G:V^2\to\mathbb R$
  - $d_G(u,v):=$ min. z délek (počtu hran) všech cest mezi $u,v$
- vlastnosti metriky (funkce je metrika = chová se jako vzdálenost)
  - $d_G(u,v)\geq 0$
  - $d_G(u,v) = 0 \iff u=v$
  - platí trojúhelníková nerovnost $d_G(u,w) \leq d_G(u,w) + d_G(w,v)$
  - $d_G(v,u)=d_G(u,v)$
- grafové operace: přidání/odebrání vrcholu/hrany, dělení hrany, kontrakce hrany
- sled v grafu (walk) – můžou se opakovat vrcholy i hrany
  - $(v_0,e_1,v_1,e_2,\dots,e_n,v_n)$
  - $\forall i: e_i=\lbrace v_{i-1},v_i\rbrace$
- tah v grafu – můžou se opakovat vrcholy, hrany ne
  - tah může být uzavřený (končí, kde začal), nebo otevřený
- eulerovský tah
  - eulerovský tah obsahuje všechny hrany a vrcholy grafu
    - někdy se eulerovský tah definuje bez nutnosti obsahovat všechny vrcholy
  - graf je eulerovský $\equiv$ existuje v něm uzavřený eulerovský tah
- věta: graf $G$ je eulerovský $\iff G$ je souvislý a každý jeho vrchol má sudý stupeň
Stromy – definice a základní vlastnosti (existence listů, počet hran stromu)
- strom je souvislý graf bez kružnic (= acyklický)
- les je acyklický graf
- list je vrchol stupně 1
  - strom o jednom vrcholu („pařez“) nemá žádný list
- lemma: každý strom s aspoň 2 vrcholy má aspoň 1 list (respektive aspoň dva listy)
- lemma: je-li $v$ list grafu $G$ , pak $G$ je strom, právě když $G-v$ je strom
- strom $G$ má $|V(G)|-1$ hran (Eulerova formule)
Ekvivalentní charakteristiky stromů
1. G je souvislý a acyklický (strom)
2. mezi vrcholy $u, v$ existuje právě jedna cesta (jednoznačně souvislý)
3. G je souvislý a po smazání libovolné jedné hrany už nebude souvislý (minimální souvislý)
4. G je acyklický a po přidání libovolné jedné hrany vznikne cyklus (maximální acyklický)
5. G je souvislý a platí pro něj Eulerova formule $|E(G)|=|V(G)|-1$
Rovinné grafy – definice a základní pojmy (rovinný graf a rovinné nakreslení grafu, stěny)
- rovinné nakreslení grafu = nakreslení grafu, aby se hrany nekřížily
  - vrcholy = body v rovině (navzájem různé)
  - hrany = křivky, které se neprotínají a jejich společnými body jsou jejich společné vrcholy
- stěny nakreslení
  - části, na které nakreslení grafu rozděluje rovinu
  - stěnou je i vnější stěna (zbytek roviny)
  - hranice stěny – skládá se z hran
  - hranice stěny je nakreslení uzavřeného sledu
- graf je rovinný, pokud má alespoň jedno rovinné nakreslení
- topologický graf je uspořádaná dvojice (graf, nakreslení)
- $K_5$ $K_{5}$ a $K_{3,3}$ $K_{3, 3}$ nejsou rovinné
  - graf je rovinný, právě když žádný jeho podgraf není izomorfní s nějakým dělením grafu $K_5$ nebo $K_{3,3}$ (tzn. podgraf může mít podrozdělené hrany – „ $K_5$ “ s libovolně podrozdělenými hranami pořád nebude rovinná)
Eulerova formule a maximální počet hran rovinného grafu (důkaz a použití)
- věta
  - nechť $G$ je souvislý graf nakreslený do roviny, $v:=|V(G)|, e:=|E(G)|, f:=$ počet stěn nakreslení
  - potom $v+f=e+2$ (Eulerova formule)
- důkaz: indukcí podle $e$ $e$
  - $e=v-1$ $e = v - 1$ (G je strom)
    - $f=1$
    - $v+1=v-1+2\quad\checkmark$
  - $e-1\to e$ $e - 1 \to e$
    - mějme graf $G$ s $e$ hranami
    - zvolím si libovolnou hranu $x$ na kružnici
    - $G':=G-x$
    - $v'=v,\quad e'=e-1,\quad f'=f-1$
    - z IP: $v'+f'=e'+2$
    - po dosazení: $v+f-1=e-1+2$
    - k oběma stranám přičteme jedničku
    - $v+f=e+2\quad\square$
- věta: maximální rovinný graf je triangulace
  - dokud hranice stěny není trojúhelník, je tam nějaká dvojice nespojených vrcholů
- počet hran maximálního rovinného grafu
  - každá stěna přispěje třemi hranami
  - každá hrana patří ke dvěma stěnám
  - počítáme „strany hran“: $3f=2e$
  - $f={2\over 3}e$
  - $v+{2\over 3}e=e+2$
  - $e=3v-6$
- věta: v každém rovinném grafu s aspoň 3 vrcholy je $|E|\leq 3|V|-6$
- důkaz
  - doplníme do $G$ hrany, až získáme maximální rovinný $G'$
  - $e'=3v-6$ (vrcholy nepřidáváme)
  - $e\leq e'=3v-6$
- důsledek
  - průměrný stupeň vrcholu v rovinném grafu je menší než 6
    - $\sum \text{deg}(\xi)=2e\leq 6v-12$
    - průměrný stupeň $\leq {6v-12\over v}\lt 6$
- počet hran a vrchol nízkého stupně v rovinných grafech bez trojúhelníků
  - maximální rovinné grafy bez trojúhelníků mají stěny čtvercové, pětiúhelníkové, nebo to může být strom ve tvaru hvězdy
  - pro čtvercově stěny platí $4f=2e$ , pro pětiúhelníkové $5f=2e$
  - obecně $4f\leq 2e\to f\leq \frac 12 e$
  - $v+\frac 12e\geq e+2$
  - $e\leq 2v-4$
  - průměrný stupeň $\leq {4v-8\over v} \lt$ 4
  - existuje vrchol stupně max. 3
Barevnost grafů – definice dobrého obarvení, vztah barevnosti a klikovosti grafu
- obarvení grafu $G$ $k$ barvami ( $k$ -obarvení) je $c:V(G)\to[k]$ t. ž. kdykoli $\lbrace x,y\rbrace\in E(G)$ , pak $c(x)\neq c(y)$
- barevnost $\chi(G)$ grafu $G:=\text{min }k:\exists$ k-obarvení grafu $G$
- pozorování: kdykoli $H\subseteq G$ , pak $\chi(H)\leq \chi(G)$
- barevnost některých grafů
  - úplné grafy … $\chi(K_n)=n$
  - cesty … $\chi(P_n)=2$ pro $n\geq 1$
  - sudé kružnice … $\chi(C_{2k})=2$
  - liché kružnice … $\chi(C_{2k+1})=3$
  - stromy jsou 2-obarvitelné
  - pro rovinné grafy existuje věta o čtyřech barvách (je to těsný horní odhad – existují rovinné grafy, které nelze obarvit třemi barvami, např. $K_4$ )
- věta: $\chi(G)\leq 2\iff G$ je bipartitní $\iff G$ neobsahuje lichou kružnici
- definice: klikovost grafu $\kappa(G)$ $κ (G)$ je maximální $k$ $k$ takové, že v grafu jako podgraf existuje úplný graf $K_k$ $K_{k}$
  - $\chi(G)\geq\kappa(G)$
- klika v grafu je množina vrcholů taková, že každé dva jsou spojené hranou
- nezávislá množina v grafu je množina vrcholů taková, že žádné dva vrcholy nejsou spojené hranou
Hranová a vrcholová souvislost grafů
- $F\subseteq E$ $F \subseteq E$ je hranový řez v $G$ $G$ , pokud $G-F$ $G - F$ je nesouvislý
  - kde $G-F\coloneqq(V,E\setminus F)$
- graf je hranově $k$ -souvislý, pokud neobsahuje žádný hranový řez velikosti menší než $k$
- stupeň hranové souvislosti (nebo jen hranová souvislost) grafu $G$ $G$ , značený $k_e(G)$ $k_{e} (G)$ , je největší $k$ $k$ takové, že $G$ $G$ je hranově $k$ $k$ -souvislý
  - pozorování: $k_e(G)=$ velikost nejmenšího hranového řezu v $G$
- $A\subseteq V$ $A \subseteq V$ je vrcholový řez, pokud $G-A$ $G - A$ je nesouvislý
  - kde $G-A=(V\setminus A,E\cap {V\setminus A\choose 2})$
- graf je vrcholově $k$ -souvislý, pokud má aspoň $k+1$ vrcholů a neobsahuje žádný vrcholový řez velikosti menší než $k$
- vrcholová souvislost grafu $G$ $G$ , značená $k_v(G)$ $k_{v} (G)$ , je největší $k$ $k$ takové, že $G$ $G$ je vrcholově $k$ $k$ -souvislý
  - pozorování: $k_v(K_n)=n-1$
  - pozorování: $G$ není úplný … $k_v(G)=$ velikost nejmenšího vrcholového řezu
Hranová a vrcholová verze Mengerovy věty
- Mengerova věta, hranová $xy$ $x y$ -verze
  - pro dva různé vrcholy $x,y$ grafu $G$ platí, že $G$ obsahuje $k$ hranově disjunktních cest z $x$ do $y$ $\iff G$ neobsahuje hranový $xy$ -řez velikosti menší než $k$
- Mengerova věta, globální hranová verze
  - graf $G$ je hranově $k$ -souvislý $\iff$ mezi každými dvěma různými vrcholy existuje $k$ hranově disjunktních cest
- definice: dvě cesty v $G$ z $x$ do $y$ jsou navzájem vnitřně vrcholově disjunktní (VVD), pokud nemají žádný společný vrchol kromě $x,y$
- Mengerova věta, vrcholová $xy$ $x y$ -verze
  - nechť $G=(V,E)$ je graf
  - nechť $x,y$ jsou různé nesousední vrcholy
  - nechť $k\in\mathbb N$
  - potom $G$ obsahuje $k$ navzájem VVD cest z $x$ do $y\iff G$ neobsahuje vrcholový $xy$ -řez velikosti $\lt k$
- Mengerova věta, globální vrcholová verze
  - $G$ je vrcholově $k$ -souvislý $\iff$ mezi každými dvěma různými vrcholy $x,y$ existuje $k$ navzájem VVD cest
Orientované grafy, silná a slabá souvislost
- orientovaný graf … $(V,E): E \subseteq V^2 \setminus \{(x,x)\mid x\in V\}$ $(V, E) : E \subseteq V^{2} ∖ {(x, x) ∣ x \in V}$
  - nepovolíme smyčky (v podstatě zakážeme diagonálu na relaci)
- podkladový graf je neorientovaný graf založený na tom původním orientovaném
  - pro orientovaný $G=(V,E)$ existuje podkladový $G^0=(V,E^0)$ , kde $\lbrace u,v\rbrace \in E^0\equiv (u,v)\in E\lor (v,u)\in E$
- vstupní a výstupní stupeň $\text{deg}^\text{in},\text{deg}^\text{out}$ (hrany vedoucí do vrcholu / z vrcholu)
- vrchol je vyvážený $\equiv \text{deg}^\text{in}(v)=\text{deg}^\text{out}(v)$
- graf je vyvážený $\equiv$ všechny vrcholy jsou vyvážené
- součet vstupních stupňů = součet výstupních stupňů = počet hran
- orientovaný graf je slabě souvislý $\equiv$ jeho podkladový graf je souvislý
- o. graf je silně souvislý $\equiv$ existuje orientovaná cesta mezi každými dvěma vrcholy
- silná souvislost $\implies$ slabá souvislost
- věta: pro orientovaný graf $G$ platí: $G$ je vyvážený a slabě souvislý $\iff$ $G$ je eulerovský $\iff$ $G$ je vyvážený a silně souvislý
Toky v sítích: definice sítě a toku v ní
- tokovou síť tvoří
  - $V$ … množina vrcholů
  - $E$ … množina orientovaných hran, $E\subseteq V\times V$
  - $z\in V$ … zdroj
  - $s\in V\setminus\set{z}$ … spotřebič / stok
  - $c:E\to [0,+\infty)$ … $c(e)$ je kapacita hrany $e$
- definice umožňuje mít hrany oběma směry, připouští také smyčky, ty však z hlediska toků v sítích nejsou nijak užitečné
- poznámka: ze stoku může vycházet orientovaná hrana, podobně do zdroje může vést hrana
- tok v síti $(V,E,z,s,c)$ $(V, E, z, s, c)$ je funkce $f:E\to[0,+\infty)$ $f : E \to [0, + \infty)$ splňující
  - $\forall e\in E:0\leq f(e)\leq c(e)$
  - $\forall x\in V\setminus \set{z,s}:$ součet toků do vrcholu $x$ se rovná součtu toků z vrcholu (formálně pomocí sum) … Kirchhoffův zákon
Existence maximálního toku (bez důkazu)
- velikost toku $f$ v síti $(V,E,z,s,c)$ je $w(f)\coloneqq f[\text{Out}(z)]-f[\text{In}(z)]$
- kde $\mathrm{Out}(z)$ a $\mathrm{In}(z)$ jsou množiny hran do, respektive ze zdroje a $f[A]\coloneqq\sum_{e\in A}f(e)$ pro $A\subseteq E$
- maximální tok je tok, který má největší velikost
- fakt: v každé tokové síti existuje maximální tok
- poznámka: obecně na přednášce uvažujeme konečné tokové sítě, grafy apod.
- idea důkazu
  - mějme síť, očíslujme hrany (od $1$ do $m$ )
  - tok $f$ reprezentujme jako uspořádanou $m$ -tici hodnot
  - množina všech toků je uzavřená a omezená podmnožina $\mathbb R^m$ , je tedy kompaktní
  - funkce, která toku $f$ přiřadí $w(f)$ , je spojitá
  - víme z analýzy, že spojitá funkce na kompaktní množině nabývá maxima
- řez v síti $(V,E,z,s,c)$ je množina hran $R\subseteq E$ taková, že každá orientovaná cesta ze $z$ do $s$ obsahuje aspoň jednu hranu $R$
- Minimaxová věta o toku a řezu: nechť $f_\text{max}$ je maximální tok a $R_\text{min}$ je minimální řez v $(V,E,z,s,c)$ , potom $w(f_\text{max})=c(R_\text{min})$
Princip hledání maximálního toku v síti s celočíselnými kapacitami (například pomocí Ford-Fulkersonova algoritmu)
- rezerva hrany $uv$ $uv$
  - $r(uv)\coloneqq c(uv)-f(uv)+f(vu)$
- hrana je nasycená $\equiv$ má nulovou rezervu
- hrana je nenasycená $\equiv$ má kladnou rezervu
- cesta je nenasycená $\equiv$ žádná její hrana není nasycená / všechny mají kladné rezervy
- algoritmus
  - iterujeme, dokud existuje nenasycená cesta ze zdroje do stoku
  - spočítáme rezervu celé cesty (minimum přes rezervy hran cesty)
  - pro každou hranu upravíme tok – v protisměru odečteme co nejvíc, zbytek přičteme po směru
- pro celočíselné kapacity vrátí celočíselný tok
- racionální kapacity převedeme na celočíselné
- pro iracionální kapacity se může rozbít

5. Pravděpodobnost a statistika

Pravděpodobnostní prostor, náhodné jevy, pravděpodobnost (definice, příklady)
- $\Omega$ … množina elementárních jevů
- $\mathcal F\subseteq\mathcal P(\Omega)$ $F \subseteq P (Ω)$ je prostor jevů, pokud…
  - $\emptyset,\Omega\in\mathcal F$
  - $A\in\mathcal F\implies A^c=\Omega\setminus A\in\mathcal F$
  - $A_1,A_2,\ldots\in\mathcal F\implies\bigcup A_i\in \mathcal F$
- $P:\mathcal F\to[0,1]$ $P : F \to [0, 1]$ je pravděpodobnost, pokud…
  - $P(\Omega)=1$
  - $P(\bigcup A_i)=\sum P(A_i)$ pro $A_1,A_2,\ldots\in \mathcal F$ po dvou disjunktní
- příklady pravděpodobnostních prostorů
  - klasický – tedy konečný s uniformní pravděpodobností, např. $\Omega=[6]$ $Ω = [6]$ (hod kostkou)
    - příklad elementárního jevu … padla šestka
    - příklad jevu … padlo sudé číslo
  - diskrétní – dovolíme cinknutou kostku (nevyžadujeme uniformní pravděpodobnost)
  - geometrický – např. „náhodně“ střílíme na terč, takže šance, že zasáhneme konkrétní oblast, je úměrná obsahu oblasti (ale může být i ve více než dvou dimenzích)
  - spojitý – schopný střelec se trefuje spíše do středu terče (opět dovolíme i jiné než uniformní rozdělení)
Základní pravidla pro počítání s pravděpodobností
- $P(A)+P(A^c)=1$
- $A\subseteq B\implies P(B\setminus A)=P(B)-P(A)\implies P(A)\leq P(B)$
- $P(A\cup B)=P(A)+P(B)-P(A\cap B)$
- $P(A_1\cup A_2\cup\dots)\leq\sum_i P(A_i)$ … subaditivita, Booleova nerovnost
Nezávislost náhodných jevů, podmíněná pravděpodobnost
- jevy $A,B\in\mathcal F$ jsou nezávislé, pokud $P(A\cap B)=P(A)\cdot P(B)$
- můžeme uvažovat i větší množiny jevů
  - jevy v množině jsou (vzájemně) nezávislé, pokud pro každou konečnou podmnožinu platí, že $P(\bigcap)=\prod P$
  - pokud podmínka platí jen pro dvouprvkové podmnožiny, jsou jevy po dvou nezávislé
- pokud $A,B\in\mathcal F$ a $P(B)\gt 0$ , definujeme podmíněnou pravděpodobnost $A$ při $B$ jako $P(A\mid B)=\frac{P(A\cap B)}{P(B)}$
- zjevně $P(A\cap B)=P(A)\cdot P(B\mid A)$
- $P(A_1\cap A_2\cap \dots\cap A_n)=P(A_1)P(A_2\mid A_1)P(A_3\mid A_1\cap A_2)\dots P(A_n\mid A_1\cap\dots\cap A_{n-1})$ $P (A_{1} \cap A_{2} \cap \dots \cap A_{n}) = P (A_{1}) P (A_{2} ∣ A_{1}) P (A_{3} ∣ A_{1} \cap A_{2}) \dots P (A_{n} ∣ A_{1} \cap \dots \cap A_{n - 1})$
  - lze ukázat indukcí (nebo neformálně rozepsáním členů vpravo a vykrácením)
- věta o úplné pravděpodobnosti
  - mějme $B_1,B_2,\dots$ rozklad $\Omega$
  - $P(A)=\sum_iP(B_i)\cdot P(A\mid B_i)$ $P (A) = \sum_{i} P (B_{i}) \cdot P (A ∣ B_{i})$
    - sčítance s $P(B_i)=0$ považujeme za nulové
Bayesův vzorec
- mějme $B_1,B_2,\dots$ rozklad $\Omega$
- $P(B_j\mid A)=\frac{P(B_j)\cdot P(A\mid B_j)}{\sum_i P(B_i)\cdot P(A\mid B_i)}$
Náhodné veličiny a jejich rozdělení
- náhodná veličina je funkce, která přiřazuje každému elementárnímu náhodnému jevu nějakou (obvykle číselnou) hodnotu
- pro diskrétní náhodnou veličinu $X$ definujeme pravděpodobnostní funkci $p_X(x)=P(\set{X=x})$
- spojité náhodné veličiny obvykle popisujeme pomocí distribuční funkce a hustoty
  - distribuční funkce náhodné veličiny $X$ je funkce $F_X:\mathbb R\to [0,1]$ definovaná předpisem $F_X(x):=P(X\leq x)$
  - zjevně $P(a\lt X\leq b)=F_X(b)-F_X(a)$
  - vlastnosti
    - $F_X$ je neklesající
    - $\lim_{x\to+\infty} F_X(x)=1$
    - $\lim_{x\to-\infty} F_X(x)=0$
    - $F_X$ je zprava spojitá
  - náhodná veličina $X$ se nazývá spojitá, pokud existuje nezáporná reálná funkce $f_X$ tak, že $F_X(x)=P(X\leq x)=\int_{-\infty}^x f_X(t)\text dt$
  - hustota $f_X$ … „limita histogramů“
  - zjevně $\int_{-\infty}^\infty f=1$
Střední hodnota – linearita střední hodnoty, střední hodnota součinu nezávislých veličin, Markovova nerovnost
- $\mathbb E(X)=\sum_{x\in\text{Im}(X)}x\cdot P(X=x)$ $E (X) = \sum_{x \in Im (X)} x \cdot P (X = x)$
  - nebo $\mathbb E(X)=\int_{-\infty}^{\infty} x f_X(x)\text dx$
- pozorování: $\mathbb E(X)=\sum_{\omega\in\Omega}X(\omega)\cdot P(\set{\omega})$
- pravidlo naivního statistika
  - $\mathbb E(g(X))=\sum_{x\in\text{Im}(X)}g(x)P(X=x)$
  - nebo $\mathbb E(g(X))=\int_{-\infty}^\infty g(x)f_X(x)\text dx$
- linearita $\mathbb E(aX+b)=a\mathbb E(X)+b$ plyne z PNS pro funkci $ax+b$
- podmíněná střední hodnota $\mathbb E(X\mid B)=\sum_{x\in\text{Im}(X)}x\cdot P(X=x\mid B)$
- věta o celkové střední hodnotě: $\mathbb E(X)=\sum_i P(B_i)\cdot \mathbb E(X\mid B_i)$
- $\mathbb E(g(X,Y))=\sum_x\sum_y g(x,y) P(X=x\land Y=y)$
- $\mathbb E(aX+bY)=a\mathbb E(X)+b\mathbb E(Y)$
- pro nezávislé $X,Y$ platí $\mathbb E(XY)=\mathbb E(X)\mathbb E(Y)$
- Markovova nerovnost
  - pro $X\geq 0$ a $a\gt0$ platí $P(X\geq a)\leq\frac{\mathbb E(X)}a$
Rozptyl – definice, vzorec pro rozptyl součtu (závislých či nezávislých veličin)
- rozptyl … $\text{var}(X)=\mathbb E((X-\mathbb EX)^2)$
- směrodatná odchylka … $\sigma_X=\sqrt{\text{var}(X)}$
- věta: $\text{var}(X)=\mathbb E(X^2)-\mathbb E(X)^2$
- počítání s rozptylem
  - $\mathrm{var}(aX+b)=a^2\mathrm{var}(X)$
- rozptyl součtu nezávislých veličin je součet rozptylů
  - $\mathrm{var}(X+Y)=\mathrm{var}(X)+\mathrm{var}(Y)$
- kovariance a její vlastnosti
  - definice: $\text{cov}(X,Y)=\mathbb E((X-\mathbb EX)(Y-\mathbb EY))$
  - věta: $\text{cov}(X,Y)=\mathbb E(XY)-\mathbb E(X)\mathbb E(Y)$
  - pro nezávislé $X,Y$ platí $\text{cov}(X,Y)=0$
  - zjevně $\text{cov}(X,X)=\text{var}(X)$
  - $\text{cov}(aX+bY,Z)=a\text{cov}(X,Z)+b\text{cov}(Y,Z)$
  - korelace
    - $\rho(X,Y)=\frac{\text{cov}(X,Y)}{\sigma_X\cdot\sigma_Y}$
- rozptyl součtu náhodných veličin (závislých i nezávislých)
  - nechť $X=\sum_{i=1}^n X_i$
  - pak $\text{var}(X)=\sum_{i=1}^n\sum_{j=1}^n\text{cov}(X_i,X_j)$
Práce s konkrétními rozděleními: geometrické, binomické, Poissonovo, normální, exponenciální
- Bernoulliho/alternativní rozdělení $\text{Ber}(p)$ $Ber (p)$
  - počet úspěchů při jednom pokusu (kde $p$ je pravděpodobnost úspěchu)
  - $p_X(1)=p$
  - $p_X(0)=1-p$
  - jinak $p_X(x)=0$
  - $\mathbb E(X)=p$
  - $\text{var}(X)=p(1-p)$
- geometrické rozdělení $\text{Geom}(p)$ $Geom (p)$
  - při kolikátém pokusu poprvé uspějeme
  - $p_X(k)=(1-p)^{k-1}\cdot p$
  - $\mathbb E(X)=1/p$
  - $\text{var}(X)=\frac{1-p}{p^2}$
- binomické rozdělení $\text{Bin}(n,p)$ $Bin (n, p)$
  - počet úspěchů při $n$ nezávislých pokusech
  - $p_X(k)={n\choose k}p^k(1-p)^{n-k}$
  - $\mathbb E(X)=np$
  - $\text{var}(X)=np(1-p)$
- Poissonovo rozdělení $\text{Pois}(\lambda)$ $Pois (λ)$
  - počet doručených zpráv za časový úsek, $\lambda$ je průměrná hodnota
  - $p_X(k)=\frac{\lambda^k}{k!}e^{-\lambda}$
  - $\text{Pois}(\lambda)$ je limitou $\text{Bin}(n,\lambda/n)$ pro $n\to\infty$
  - $\mathbb E(X)=\lambda$
  - $\text{var}(X)=\lambda$
- uniformní $U(a,b)$ $U (a, b)$
  - $f_X(x)=\frac 1{b-a}$
  - $F_X(x)=\frac{x-a}{b-a}$
  - $\mathbb E(X)=\frac{a+b}2$
  - $\text{var}(X)=\frac{(b-a)^2}{12}$
- exponenciální $\text{Exp}(\lambda)$ $Exp (λ)$
  - $f_X(x)=\lambda e^{-\lambda x}$ pro $x\geq 0$
  - $F_X(x)=1-e^{-\lambda x}$ pro $x\geq 0$
  - $\mathbb E(X)=1/\lambda$
  - $\text{var}(X)=1/\lambda^2$
- standardní normální rozdělení
  - $N(0,1)$
  - $f_X(x)=\varphi(x)=\frac1{\sqrt{2\pi}} e^{-x^2/2}$
- obecné normální rozdělení
  - $N(\mu,\sigma^2)$
  - $f_X(x)=\frac 1{\sigma\sqrt{2\pi}}e^{-\frac12(\frac{x-\mu}{\sigma})^2}$
  - máme-li $X\sim N(\mu,\sigma^2)$ , pak pro $Z=\frac{X-\mu}\sigma$ platí $Z\sim N(0,1)$
  - pro normální nezávislé náhodné veličiny $X_i\sim N(\mu_i,\sigma_i^2)$ (nechť je jich konečně) je i součet normální náhodná veličina $\sum X_i\sim N(\sum\mu_i,\sum\sigma_i^2)$
  - pravidlo $3\sigma$ $3 σ$
    - $P(\mu-\sigma\lt X\lt\mu+\sigma)\doteq 0.68$
    - $P(\mu-2\sigma\lt X\lt\mu+2\sigma)\doteq 0.95$
    - $P(\mu-3\sigma\lt X\lt\mu+3\sigma)\doteq 0.997$
Limitní věty: zákon velkých čísel
- mějme $X_1,X_2,\dots$ stejně rozdělené nezávislé náhodné veličiny
- $\bar X_n=(X_1+\dots+X_n)/n$ … výběrový průměr
- silný zákon velkých čísel
  - $\lim_{n\to\infty}\bar X_n=\mu$ skoro jistě (s pravděpodobností 1)
  - použití: Monte Carlo integrování kruhu
- slabý zákon velkých čísel (zlepšení přesnosti opakovaným měřením)
  - $\forall\varepsilon\gt 0:\lim_{n\to\infty} P(|\bar X_n-\mu|\gt\varepsilon)=0$
  - říkáme, že $\bar X_n$ konverguje k $\mu$ v pravděpodobnosti, píšeme $\bar X_n\xrightarrow P\mu$
Limitní věty: centrální limitní věta
- nechť $X_1,X_2,\dots$ jsou stejně rozdělené se střední hodnotou $\mu$ a rozptylem $\sigma^2$
- označme $Y_n=\frac{(X_1+\dots+X_n)-n\mu}{\sigma\sqrt{n}}$
- pak $Y_n\xrightarrow d N(0,1)$ $Y_{n} d N (0, 1)$
  - $Y_n$ konverguje v distribuci k $N(0,1)$
  - tzn. $\lim_{n\to\infty} F_{Y_n}(x)=\Phi(x)$
- CLV se hodí k aproximaci distribuce součtu nebo průměru velkého počtu náhodných veličin normálním rozdělením
  - takže můžeme provádět bodové a intervalové odhady i tam, kde data nejsou normálně rozdělená, ale známe rozptyl
Bodové odhady – alespoň jedna metoda pro jejich tvorbu, vlastnosti
- pro náhodný výběr $X_1,\dots,X_n\sim F_\theta$ $X_{1}, \dots, X_{n} \sim F_{θ}$ a libovolnou funkci $g$ $g$ nazveme bodový odhad $\hat\theta_n$ $\hat{θ}_{n}$ …
  - nevychýlený/nestranný, pokud $\mathbb E(\hat\theta_n)=g(\theta)$
  - asymptoticky nevychýlený, pokud $\lim_{n\to\infty}\mathbb E(\hat\theta_n)=g(\theta)$
  - konzistentní, pokud $\hat\theta_n\xrightarrow P g(\theta)$
- dále definujeme
  - vychýlení … $\text{bias}(\hat\theta_n)=\mathbb E(\hat\theta_n)-\theta$
  - střední kvadratickou chybu … $\text{MSE}(\hat\theta_n)=\mathbb E((\hat\theta_n-\theta)^2)$
- věta: $\text{MSE}(\hat\theta_n)=\text{bias}(\hat\theta_n)^2+\text{var}(\hat\theta_n)$
- metoda momentů
  - $r$ -tý moment $X$ … $\mathbb EX^r=m_r(\theta)$
  - $r$ $r$ -tý výběrový moment … $\frac1n\sum_{i=1}^n X_i^r=\widehat{m_r}$ $\frac{1}{n} \sum_{i = 1}^{n} X_{i}^{r} = m_{r}$
    - konzistentní nevychýlený odhad pro $r$ -tý moment
  - nalezneme $\theta$ takové, že $m_r(\theta)=\widehat{m_r}$
  - typicky stačí použít první moment, dostaneme nějakou rovnici
  - $m_1=\mu$
  - $m_2=\mathbb E(X^2)=\text{var}(X)+(\mathbb EX)^2=\sigma^2+\mu^2$
- metoda maximální věrohodnosti
  - $\hat\theta_{ML}=\text{argmax}_\theta\;p(x;\theta)$ $\hat{θ}_{M L} = argmax_{θ} p (x; θ)$
    - $\text{argmax}_\theta\;f(x;\theta)$
    - abych se nemusel rozhodovat mezi $p$ a $f$ , budu používat $L$
  - výpočetně jednodušší bude používat logaritmus $L$ , který označíme $\ell$
  - příklad
    - ve vzorku $k$ leváků z $n$ lidí, hledáme pravděpodobnost $\theta$ , že je někdo levák
    - $L(x;\theta)=\theta^k(1-\theta)^{n-k}$
    - $\ell(x;\theta)=k\log\theta+(n-k)\log(1-\theta)$
    - $\ell'(x;\theta)=\frac k\theta-\frac{n-k}{1-\theta}$ $ℓ^{'} (x; θ) = \frac{k}{θ} - \frac{n - k}{1 - θ}$
      - hledáme maximum, položíme derivaci rovnou nule (a zkontrolujeme krajní hodnoty)
  - podobně pro spojitý případ – „maximalizujeme“ rovnici pro pravděpodobnost konkrétního výběru
Intervalové odhady: metoda založená na aproximaci normálním rozdělením
- statistiky $D\leq H$ $D \leq H$ určují konfidenční interval o spolehlivosti $1-\alpha$ $1 - α$ , pokud $P(D\leq\theta\leq H)=1-\alpha$ $P (D \leq θ \leq H) = 1 - α$
  - zkráceně $(1-\alpha)$ -CI
- interval budeme uvažovat ve tvaru $[x-\delta,x+\delta]$
- postup
  - máme nestranný bodový odhad $\hat\theta$ pro parametr $\theta$
  - $\hat\theta$ má normální rozdělení
  - $\hat\theta\pm z_{\alpha/2}\cdot\text{se}$ $\hat{θ} \pm z_{α /2} \cdot se$ je $(1-\alpha)$ $(1 - α)$ -CI
    - $z_{\alpha/2}:=\Phi^{-1}(1-\alpha/2)$
    - $\text{se}:=\sigma(\hat\theta)$
Testování hypotéz – základní přístup, chyby 1. a 2. druhu, hladina významnosti
- nulová hypotéza … defaultní, konzervativní model
- alternativní hypotéza … alternativní model, „zajímavost“
- nulovou hypotézu buď zamítneme, nebo nezamítneme
- chyba 1. druhu – chybné zamítnutí, „trapas“
- chyba 2. druhu – chybné přijetí, „promarněná příležitost“
- hladina významnosti $\alpha$ $α$ … pravděpodobnost chyby 1. druhu
  - typicky se volí $\alpha=0.05$
- $\beta$ … pravděpodobnost chyby 2. druhu
- kritický obor … je to množina, kterou určíme před provedením testu; pokud se výsledek našeho testu bude nacházet v kritickém oboru, zamítneme nulovou hypotézu
  - tedy $\alpha=P(h(X)\in W; H_0)$
- síla testu … $1-\beta$ $1 - β$
  - chceme co největší
- $p$ -hodnota … nejmenší $\alpha$ taková, že na hladině $\alpha$ zamítáme $H_0$

6. Logika

Znalost a práce se základními pojmy syntaxe výrokové a predikátové logiky (jazyk, otevřená a uzavřená formule, instance formule, apod.)
- výroková logika
  - jazyk je určený neprázdnou množinou výrokových proměnných $\mathbb P$ (také jim říkáme prvovýroky nebo atomické výroky)
  - množina $\mathbb P$ může být konečná nebo i nekonečná (ale obvykle bude spočetná) a bude mít dané uspořádání
- predikátová logika
  - signatura je dvojice $\braket{\mathcal {R,F}}$ , kde $\mathcal{R,F}$ jsou disjunktní množiny symbolů (relační a funkční, ty zahrnují konstantní) spolu s danými aritami a neobsahují symbol $=$
  - do jazyka patří…
    - spočetně mnoho proměnných
    - relační, funkční a konstantní symboly ze signatury a symbol $=$ , jde-li o jazyk s rovností
    - univerzální a existenční kvantifikátory pro každou proměnnou
    - symboly pro logické spojky a závorky
  - struktura v signatuře $\braket{\mathcal{R,F}}$ $⟨ R, F ⟩$ je trojice $\mathcal A=\braket{A,\mathcal{R^A,F^A}}$ $A = ⟨ A, R^{A}, F^{A} ⟩$ , kde…
    - $A$ je neprázdná množina, říkáme jí doména (také universum)
    - $\mathcal {R^A}$ je množina interpretací jednotlivých relačních symbolů (kde interpretace $n$ -árního relačního symbolu je množina uspořádaných $n$ -tic prvků z $A$ )
    - $\mathcal {F^A}$ $F^{A}$ je množina interpretací jednotlivých funkčních symbolů (kde intepretace $n$ $n$ -árního funkčního symbolu odpovídá funkci přiřazující $n$ $n$ -tici prvků z $A$ $A$ jeden prvek z $A$ $A$ )
      - speciálně pro konstantní symbol $c\in\mathcal F$ je $c^\mathcal A\in A$
  - termy jazyka $L$ $L$ jsou konečné nápisy definované induktivně
    - proměnná je term
    - konstantní symbol je term
    - pro $n$ -ární funkční symbol $f$ a termy $t_1,\dots,t_n$ je nápis $f(t_1,\dots,t_n)$ také term
  - atomická formule jazyka $L$ je nápis $R(t_1,\dots,t_n)$ , kde $R$ je $n$ -ární relační symbol z $L$ (v jazyce s rovností to může být i rovnost) a $t_i$ je $L$ -term
  - formule jazyka $L$ $L$ jsou konečné nápisy definované induktivně
    - atomická formule je formule
    - negace formule je formule
    - spojením dvou formulí binární logickou spojkou dostaneme formuli
    - přidáním kvantifikátoru před formuli dostaneme formuli
  - výskyt proměnné je vázaný, pokud jí odpovídá nějaký kvantifikátor, jinak je výskyt volný
  - proměnná je volná, pokud má volný výskyt, je vázaná, pokud má vázaný výskyt
  - formule je otevřená, neobsahuje-li žádný kvantifikátor
  - formule je uzavřená (= sentence), pokud nemá žádnou volnou proměnnou
  - term $t$ $t$ je substituovatelný za proměnnou $x$ $x$ ve formuli $\varphi$ $φ$ , pokud po simultánním nahrazení všech volných výskytů $x$ $x$ ve $\varphi$ $φ$ za $t$ $t$ nevznikne ve $\varphi$ $φ$ žádný vázaný výskyt proměnné z $t$ $t$
    - v tom případě říkáme vzniklé formuli instance $\varphi$ vzniklá substitucí $t$ za $x$ a označujeme ji $\varphi(x/t)$
Prenexní tvary formulí predikátové logiky
- PNF = kvantifikátory jsou před formulí, formule se dělí na kvantifikátorový prefix a otevřené jádro
- převod na PNF – postupně kvantifikátory vytahuju (podle pravidel), v případě potřeby přejmenuju proměnnou, tím vznikne varianta (pokud je v druhé části formule volná proměnná se stejným názvem)
- pravidlo převodu: pokud vytahujeme kvantifikátor z negace, musíme ho „přepnout“ (pozor: u implikace je levá strana jakoby negovaná)
Znalost základních normálních tvarů (CNF, DNF, PNF)
- PNF = kvantifikátory jsou před formulí, formule se dělí na kvantifikátorový prefix a otevřené jádro
- tvary výroků
  - literál je prvovýrok nebo negace prvovýroku
    - pro literál $\ell$ označuje $\overline\ell$ literál k němu opačný (tedy jeho negaci)
  - klauzule je disjunkce literálů
    - jednotková klauzule je samotný literál
    - prázdná klauzule je $\bot$
  - výrok je v konjunktivní normální formě (CNF), pokud je konjunkcí klauzulí
    - prázdný výrok v CNF je $\top$
  - elementární konjunkce je konjunkce literálů
    - jednotková elementární konjunkce je samotný literál
    - prázdná elementární konjunkce je $\top$
  - výrok je v disjunktivní normální formě (DNF), pokud je disjunkcí elementárních konjunkcí
    - prázdný výrok v DNF je $\bot$
  - výrok je hornovský (v Hornově tvaru), pokud je konjunkcí hornovských klauzulí, tj. klauzulí obsahujících nejvýše jeden pozitivní literál
- množinová reprezentace
  - klauzule je konečná množina literálů
    - prázdnou klauzuli označíme $\square$ , není nikdy splněna
  - CNF formule je (konečná nebo nekonečná) množina klauzulí
    - prázdná formule $\emptyset$ je vždy splněna
Převody na normální tvary
- sémantický převod
  - najdeme modely výroku
  - pro DNF budeme uvažovat disjunkci elementárních konjunkcí, přičemž každá elementární konjunkce popíše jeden model
  - pro CNF musíme najít nemodely formule, každá klauzule zakáže jeden nemodel
    - pokud je první nemodel $(0,0,0)$ , pak první klauzule bude $(p\lor q\lor r)$
- syntaktický převod
  - přepíšeme implikaci a ekvivalenci pomocí konjunkce, disjunkce a negace
  - přesuneme negace dovnitř (k literálům)
  - použijeme distributivitu konjunkce a disjunkce, abychom jednu přesunuli dovnitř (podle toho, jestli chceme CNF nebo DNF)
Použití normálních tvarů pro algoritmy (SAT, rezoluce)
- problém Horn-SAT
  - výrok je hornovský, pokud je konjunkcí hornovských klauzulí, tj. klauzulí obsahujících nejvýše jeden pozitivní literál
  - algoritmus
    - pokud $\varphi$ obsahuje dvojici opačných jednotkových klauzulí, není splnitelný
    - pokud $\varphi$ neobsahuje žádnou jednotkovou klauzuli, je splnitelný, ohodnotíme všechny zbývající proměnné nulou
    - pokud $\varphi$ obsahuje jednotkovou klauzuli $\ell$ , ohodnotíme literál $\ell$ hodnotou 1, provedeme jednotkovou propagaci a postup opakujeme
  - jednotková propagace pro $\ell=1$ $ℓ = 1$
    - každou klauzuli obsahující $\ell$ odstraníme (protože je takto splněna)
    - $\overline\ell$ odstraníme ze všech klauzulí, které ho obsahují (protože $\overline\ell$ nemůže zajistit splnění dané klauzule)
  - Horn-SAT lze řešit v lineárním čase
- algoritmus DPLL pro řešení SAT
  - literál $\ell$ $ℓ$ má čistý výskyt ve $\varphi$ $φ$ , pokud se $\ell$ $ℓ$ vyskytuje ve $\varphi$ $φ$ a opačný literál $\overline\ell$ $\overline{ℓ}$ se ve $\varphi$ $φ$ nevyskytuje
    - takový literál můžu nastavit na 1
    - to neovlivní splnitelnost výroku, ale zmenší to množinu modelů, které jsem schopen nalézt
  - algoritmus
    - dokud $\varphi$ obsahuje jednotkovou klauzuli $\ell$ , ohodnoť $\ell=1$ a proveď jednotkovou propagaci
    - dokud existuje literál $\ell$ , který má ve $\varphi$ čistý výskyt, ohodnoť $\ell=1$ a odstraň klauzule obsahující $\ell$
    - pokud $\varphi$ neobsahuje žádnou klauzuli, je splnitelný
    - pokud $\varphi$ obsahuje prázdnou klauzuli, není splnitelný
    - jinak zvol dosud neohodnocenou výrokovou proměnnou $p$ a zavolej algoritmus rekurzivně na $\varphi\land p$ a na $\varphi\land\neg p$
  - algoritmus běží v exponenciálním čase
- rezoluce
  - použitím rezolučního pravidla z klauzulí $\varphi\lor p$ a $\psi\lor\neg p$ dostaneme $\varphi\lor\psi$
  - takhle spolu můžeme postupně rezolvovat různé klauzule z teorie
  - pokud nám vyjde prázdná klauzule, je teorie sporná
  - k dokázání výroku $\varphi$ $φ$ v teorii $T$ $T$ hledáme rezoluční zamítnutí $T\cup\neg\varphi$ $T \cup \neg φ$
    - nebo přímo rezoluční důkaz výroku $\varphi$ (tzn. na konci rezoluce nám vyjde $\varphi$ )
Pojem modelu teorie
- model (jazyka) ve výrokové logice je pravdivostní ohodnocení proměnných
  - model $v$ je modelem teorie $T$ , pokud každý axiom z $T$ v modelu $v$ platí, píšeme $v\models T$
- v predikátové logice: model jazyka $L$ $L$ nebo také $L$ $L$ -struktura je libovolná struktura v signatuře jazyka $L$ $L$
  - model teorie $T$ je $L$ -struktura, ve které platí všechny axiomy teorie $T$
Pravdivost, lživost, nezávislost formule vzhledem k teorii, splnitelnost, tautologie, důsledek
- pravdivý výrok platí v každém modelu (jazyka/teorie)
  - je pravdivý v logice = platí v logice = je tautologie
  - je pravdivý v $T$ = platí v $T$ = je důsledek $T$
- lživý (sporný) výrok neplatí v žádném modelu
- nezávislý výrok platí v nějakém modelu a neplatí v jiném modelu
- splnitelný výrok platí v nějakém modelu (tedy není lživý, je pravdivý nebo nezávislý)
Analýza výrokových teorií nad konečně mnoha prvovýroky
- nechť $T$ $T$ je bezesporná teorie nad $\mathbb P$ $P$
  - $|\mathbb P|=n\in\mathbb N^+$ … počet proměnných v jazyce
  - $m=|M_{\mathbb P}(T)|$ … velikost množiny modelů teorie $T$
- neekvivalentních výroků nad $\mathbb P$ $P$ je $2^{2^n}$ $2^{2^{n}}$
  - každý výrok odpovídá jedné podmnožině množiny modelů (všech modelů je $2^n$ )
- neekvivalentních výroků nad $\mathbb P$ pravdivých/lživých v $T$ je $2^{2^n-m}$
- neekv. výroků nad $\mathbb P$ $P$ nezávislých v $T$ $T$ je $2^{2^n}-2\cdot 2^{2^n-m}$ $2^{2^{n}} - 2 \cdot 2^{2^{n} - m}$
  - vezmeme všechny a odečteme pravdivé a lživé
- neekv. jednoduchých extenzí teorie $T$ $T$ je $2^m$ $2^{m}$ , z toho sporná je jedna
  - podle toho, které modely ubereme
- neekv. kompletních jednoduchých extenzí teorie $T$ $T$ je $m$ $m$
  - každá odpovídá jednomu modelu
- $T$ -neekvivalentních výroků nad $\mathbb P$ je $2^m$
- $T$ -neekv. výroků nad $\mathbb P$ pravdivých/lživých (v $T$ ) je $1$
- $T$ -neekv. výroků nad $\mathbb P$ nezávislých (v $T$ ) je $2^m-2$
Extenze teorií – schopnost porovnat sílu teorií, konzervativnost, skolemizace
- extenze teorie $T$ $T$ je libovolná teorie $T'$ $T^{'}$ v jazyce $\mathbb P'\supseteq\mathbb P$ $P^{'} \supseteq P$ splňující $\text{Csq}_{\mathbb P}(T)\subseteq\text{Csq}_{\mathbb P'}(T')$ $Csq_{P} (T) \subseteq Csq_{P^{'}} (T^{'})$
  - kde $\text{Csq}_\mathbb P(T)$ je množina všech důsledků teorie (výroků/sentencí pravdivých v teorii $T$ v jazyce $\mathbb P$ )
- extenze je jednoduchá, pokud $\mathbb P'=\mathbb P$
- extenze je konzervativní, pokud $\text{Csq}_{\mathbb P}(T)=\text{Csq}_{\mathbb P}(T')=\text{Csq}_{\mathbb P'}(T')\cap\text{VF}_\mathbb P$
- sémantický význam (v řeči modelů)
  - mějme teorii $T$ v jazyce $\mathbb P$ a teorii $T'$ v jazyce $\mathbb P'$ , kde $\mathbb P\subseteq\mathbb P'$
  - $T'$ je jednoduchou extenzí $T$ , právě když $\mathbb P'=\mathbb P$ a $M_\mathbb P(T')\subseteq M_\mathbb P(T)$
  - $T'$ je extenzí $T$ , právě když $M_{\mathbb P'}(T')\subseteq M_{\mathbb P'}(T)$
  - $T'$ je konzervativní extenzí $T$ , pokud je extenzí a navíc platí, že každý model $T$ lze nějak expandovat na model $T'$
  - $T'$ je extenzí $T$ a zároveň $T$ je extenzí $T'$ , právě když $T'\sim T$ (jazyky a množiny modelů se rovnají)
  - kompletní jednoduché extenze $T$ jednoznačně až na ekvivalenci odpovídají modelům $T$
- $T'$ je extenzí $T$ o definice, pokud vznikla z $T$ postupnou extenzí o definice relačních a funkčních (případně konstantních) symbolů
- je-li $T'$ $T^{'}$ extenze teorie $T$ $T$ o definice, potom platí:
  - každý model teorie $T$ lze jednoznačně expandovat na model $T'$
  - $T'$ je konzervativní extenze $T$
  - pro každou $L'$ -formuli $\varphi'$ existuje $L$ -formule $\varphi$ taková, že $T'\models\varphi'\leftrightarrow\varphi$
- Skolemova varianta sentence vzniká z původní PNF sentence skolemizací
  - skolemizace spočívá v tom, že tyto kroky iterujeme přes všechny existenční kvantifikátory $(\exists y_i)$ $(\exists y_{i})$
    - odstraníme z prefixu existenční kvantifikátor $(\exists y_i$ )
    - za proměnnou $y_i$ substituujeme term $f_i(x_1,\dots,x_{n_i})$ , kde $x_1,\dots,x_{n_i}$ jsou proměnné, jejichž univerzální kvantifikátory předcházejí $(\exists y_i)$
  - začínáme s $L$ -sentencí v PNF, jejíž všechny vázané proměnné jsou různé
  - dostaneme $L'$ -sentenci v PNF, kde $L'$ je rozšíření $L$ o nové $n_i$ -ární funkční symboly
Dokazatelnost – pojem formálního důkazu, zamítnutí; schopnost práce v některém z formálních dokazovacích systémů (např. tablo)
- důkaz, zamítnutí
  - důkaz faktu, že v teorii $T$ platí výrok $\varphi$ je konečný syntaktický objekt vycházející z axiomů $T$ a výroku $\varphi$
  - důkaz konstruujeme syntakticky, aniž bychom se museli zabývat modely
  - po dokazovacím systému požadujeme dvě vlastnosti: korektnost (je-li výrok dokazatelný z $T$ , je pravdivý v $T$ ) a úplnost (je-li výrok pravdivý v $T$ , je dokazatelný z $T$ )
  - důkaz říká, že $\varphi$ $φ$ platí, zamítnutí říká, že $\varphi$ $φ$ neplatí
    - rezoluční důkaz $\varphi$ v teorii $S$ má v kořeni $\varphi$ , rezoluční zamítnutí teorie $S$ má v kořeni $\square$
- tablo důkaz
  - konečné tablo z teorie $T$ $T$ je uspořádaný, položkami označkovaný strom zkonstruovaný aplikací konečně mnoha následujících pravidel:
    - jednoprvkový strom označkovaný libovolnou položkou je tablo z teorie $T$
    - pro libovolnou položku $P$ na libovolné větvi $V$ můžeme na konec větve $V$ připojit atomické tablo pro položku $P$
    - na konec libovolné větve můžeme připojit položku $\text T\alpha$ pro libovolný axiom teorie $\alpha\in T$
  - tablo je konečné nebo nekonečné, každopádně vzniklo ve spočetně mnoha krocích
  - tablo pro položku $P$ je tablo s položkou $P$ v kořeni
  - tablo důkaz výroku $\varphi$ $φ$ z teorie $T$ $T$ je sporné tablo z teorie $T$ $T$ s položkou $\text F\varphi$ $F φ$ v kořeni
    - pokud existuje, je $\varphi$ tablo dokazatelný z $T$ , píšeme $T\vdash\varphi$
    - podobně definujeme tablo zamítnutí s $\text T\varphi$ v kořeni, tablo zamítnutelnost se značí $T\vdash \neg\varphi$
  - tablo je sporné, pokud je každá jeho větev sporná
  - větev je sporná, pokud obsahuje položky $\text T\psi$ a $\text F\psi$ pro nějaký výrok $\psi$ , jinak je bezesporná
  - tablo je dokončené, pokud je každá jeho větev dokončená
  - větev je dokončená…
    - pokud je sporná
    - nebo pokud je každá její položka na této větvi redukovaná a pokud větev zároveň obsahuje položku s T pro každý axiom teorie
  - položka je redukovaná na dané větvi, pokud obsahuje pouze výrokovou proměnnou nebo se na dané větvi vyskytuje jako kořen atomického tabla (tedy došlo k jejímu rozvoji na dané větvi)
  - v predikátové logice navíc řešíme kvantifikátory – položky typu svědek a všichni
Věty o kompaktnosti a úplnosti výrokové a predikátové logiky – znění a porozumění významu; použití na příkladech, důsledky
- věta o kompaktnosti: teorie má model, právě když každá její konečná část má model
- aplikace
  - popíšeme požadovanou vlastnost nekonečného objektu pomocí (nekonečné) výrokové teorie
  - z konečné části teorie sestrojíme konečný podobjekt mající danou vlastnost
- příklady
  - spočetně nekonečný graf je bipartitní $\iff$ $⟺$ každý jeho konečný podgraf je bipartitní
    - $T=\set{p_u\to\neg p_v\mid\set{u,v}\in E(G)}$
  - nestandardní model přirozených čísel
    - vezmeme standardní model přirozených čísel (jeho teorii)
    - přidáme nový konstantní symbol
    - přidáme k teorii výrok, že je ta konstanta ostře větší než každý $n$ -tý numerál
    - každá konečná část této nové teorie má model, takže i celá ta nová teorie má
- První věta o neúplnosti: Pro každou bezespornou rekurzivně axiomatizovanou extenzi $T$ $T$ Robinsonovy aritmetiky existuje sentence, která je pravdivá v $\underline{\mathbb N}$ $\underline{N}$ , ale není dokazatelná v $T$ $T$ .
  - Robinsonova aritmetika je teorie jazyka aritmetiky $L=\braket{S,+,\cdot,0,\leq}$ $L = ⟨ S, +, \cdot, 0, \leq ⟩$ s rovností
    - má osm (tradičně spíše sedm) axiomů, některé z nich:
      - $S(x)\neq 0$
      - $S(x)=S(y)\to x=y$
      - $x+0=x$
      - $x+S(y)=S(x+y)$
  - $\underline{\mathbb N}=\braket{\mathbb N,S,+,\cdot,0,\leq}$ … standardní model přirozených čísel
- důsledek 1.1: je-li $T$ $T$ rekurzivně axiomatizovaná extenze Robinsonovy aritmetiky a je-li navíc $\underline{\mathbb N}$ $\underline{N}$ modelem teorie $T$ $T$ , potom $T$ $T$ není kompletní
  - pro sentenci, která není dokazatelná v $T$ , nemůže být dokazatelná ani její negace (byl by to spor s její pravdivostí v $\underline{\mathbb N}$ )
- důsledek 1.2: teorie $\text{Th}(\underline{\mathbb N})$ $Th (\underline{N})$ není rekurzivně axiomatizovatelná
  - kdyby byla, nemohla by být kompletní – ale ona kompletní je
  - značení: $\text{Th}(\underline{\mathbb N})$ … množina všech sentencí pravdivých v $\underline{\mathbb N}$ (tzv. teorie struktury $\underline{\mathbb N}$ )
- věta (Rosserův trik): v každé bezesporné rekurzivně axiomatizované extenzi Robinsonovy aritmetiky existuje nezávislá sentence – tedy taková není kompletní
  - v podstatě plyne z důsledku 1.1, jen se zbavuje $\underline{\mathbb N}$
- Druhá věta o neúplnosti: Pro každou bezespornou rekurzivně axiomatizovanou extenzi $T$ Peanovy aritmetiky platí, že $\mathit{Con_T}$ není dokazatelná v $T$ .
- $\mathit{Con_T}$ $Co n_{T}$ … sentence vyjadřující bezespornost (konzistence) teorie $T$ $T$
  - $\mathit{Con_T}=\neg(\exists y)\mathit{Prf_{T}}(\underline{0=S(0)},y)$
  - $\mathit{Prf_{T}}(x,y)$ … $y$ je důkaz $x$ v $T$
- důsledek 2.1: existuje model Peanovy aritmetiky (PA), ve kterém platí sentence $(\exists y)\mathit{Prf_{PA}}(\underline{0=S(0)},y)$
- důsledek 2.2: existuje bezesporná rekurzivně axiomatizovaná extenze $T$ Peanovy aritmetiky, která dokazuje svou spornost, tj. taková, že $T\vdash\neg \mathit{Con_T}$
- důsledek 2.3: je-li teorie množin ZFC bezesporná, nemůže být sentence $\mathit{Con_{ZFC}}$ v teorii ZFC dokazatelná
Rozhodnutelnost – pojem kompletnosti a její kritéria, význam pro rozhodnutelnost; příklady rozhodnutelných a nerozhodnutelných teorií
- teorie je sporná, jestliže… (ekvivalentně)
  - v ní platí spor
  - nemá žádný model
  - v ní platí všechny výroky
- teorie je bezesporná (splnitelná), pokud není sporná, tj. má nějaký model
- teorie je kompletní jestliže není sporná a každý výrok (respektive sentence) je v ní pravdivý nebo lživý (tj. nemá žádné nezávislé výroky), ekvivalentně, pokud má právě jeden model (až na elementární ekvivalenci v predikátové logice)
  - struktury $\mathcal{A,B}$ (v témž jazyce) jsou elementárně ekvivalentní, pokud v nich platí tytéž sentence (značíme $\mathcal A\equiv \mathcal B$ )
  - zjevně $\mathcal A\equiv \mathcal B\iff\text{Th}(\mathcal A)=\text{Th}(\mathcal B)$
- o teorii $T$ $T$ říkáme, že je…
  - rozhodnutelná, pokud existuje algoritmus, který pro každou vstupní formuli $\varphi$ doběhne a odpoví, zda $T\models\varphi$
  - částečně rozhodnutelná, pokud existuje algoritmus, který pro každou vstupní formuli $\varphi$ $φ$ …
    - pokud $T\vDash\varphi$ , doběhne a odpoví „ano“
    - pokud $T\nvDash\varphi$ , buď nedoběhne, nebo doběhne a odpoví „ne“
- „rekurzivní“ pojmy
  - teorie $T$ je rekurzivně axiomatizovaná, pokud existuje algoritmus, který pro každou vstupní formuli $\varphi$ doběhne a odpoví, zda $\varphi\in T$
  - třída $L$ -struktur $K\subseteq M_L$ je rekurzivně axiomatizovatelná, pokud existuje rekurzivně axiomatizovaná $L$ -teorie $T$ taková, že $K=M_L(T)$
  - teorie $T'$ je rekurzivně axiomatizovatelná, pokud je rekurzivně axiomatizovatelná třída jejích modelů, neboli pokud je $T'$ ekvivalentní nějaké rekurzivně axiomatizované teorii
  - řekneme, že teorie $T$ má rekurzivně spočetnou kompletaci, pokud (nějaká) množina (až na ekvivalenci) všech jednoduchých kompletních extenzí teorie $T$ je rekurzivně spočetná, tj. existuje algoritmus, který pro danou vstupní dvojici přirozených čísel $(i,j)$ vypíše na výstup $i$ -tý axiom $j$ -té extenze (v nějakém pevně daném uspořádání), nebo odpoví, že takový axiom už neexistuje
- tvrzení: je-li $T$ rekurzivně axiomatizovaná, potom je částečně rozhodnutelná, je-li navíc kompletní, je rozhodnutelná
- tvrzení: je-li $\mathcal A$ konečná struktura v konečném jazyce s rovností, potom je teorie $\text{Th}(\mathcal A)$ rekurzivně axiomatizovatelná
- tvrzení: pokud je teorie $T$ rekurzivně axiomatizovaná a má rekurzivně spočetnou kompletaci, potom je $T$ rozhodnutelná
- nerozhodnutelnost
  - mějme formuli $\varphi$ $φ$ ve tvaru $(\exists x_1)\dots(\exists x_n) \;p(x_1,\dots,x_n)=q(x_1,\dots,x_n)$ $(\exists x_{1}) \dots (\exists x_{n}) p (x_{1}, \dots, x_{n}) = q (x_{1}, \dots, x_{n})$
    - kde $p$ a $q$ jsou polynomy s přirozenými koeficienty
    - věta: neexistuje algoritmus, který by pro danou dvojici polynomů s přirozenými koeficienty rozhodl, zda mají přirozené řešení, tj. zda platí $\underline{\mathbb N}\vDash\varphi$
  - věta: neexistuje algoritmus, který by pro danou vstupní formuli $\varphi$ rozhodl, zda je logicky platná (tedy zda je tautologie)
- příklady rozhodnutelných teorií
  - teorie čisté rovnosti (bez axiomů, v jazyce $L=\braket{}$ s rovností)
  - teorie unárního predikátu (bez axiomů, v jazyce $L=\braket{U}$ s rovností, kde $U$ je unární relační symbol)
  - teorie hustých lineárních uspořádání DeLO*
  - teorie komutativních grup
  - teorie Booleových algeber
  - teorie následníka s nulou
  - Presburgerova aritmetika
- příklady nerozhodnutelných teorií
  - Robinsonova aritmetika (a také Peanova aritmetika a ZFC, což jsou její extenze)
  - teorie (obecných) grup