Společná matematika: kartičky

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

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

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

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

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$

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

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

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

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í

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

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$

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

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

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

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

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

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$

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

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á

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

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$ )

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

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)

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

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

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

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$

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

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í)

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

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)$

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

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'$

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

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

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

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

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

Aplikace integrálů: obsahy rovinných útvarů

plocha rovinného útvaru $U(a,b,f)$ pod grafem funkce $f$ … $\int_a^b f$

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

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$

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

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}$

2. Algebra a lineární algebra

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

2. Algebra a lineární algebra

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

2. Algebra a lineární algebra

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)

2. Algebra a lineární algebra

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}$

2. Algebra a lineární algebra

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í

2. Algebra a lineární algebra

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$

2. Algebra a lineární algebra

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$

2. Algebra a lineární algebra

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)

2. Algebra a lineární algebra

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})$

2. Algebra a lineární algebra

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$

2. Algebra a lineární algebra

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í

2. Algebra a lineární algebra

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$

2. Algebra a lineární algebra

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\|$

2. Algebra a lineární algebra

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

2. Algebra a lineární algebra

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í

2. Algebra a lineární algebra

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

2. Algebra a lineární algebra

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)$

2. Algebra a lineární algebra

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}$

2. Algebra a lineární algebra

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í

2. Algebra a lineární algebra

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á

2. Algebra a lineární algebra

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}$

2. Algebra a lineární algebra

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$

2. Algebra a lineární algebra

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í

2. Algebra a lineární algebra

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$

3. Diskrétní matematika

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ě

3. Diskrétní matematika

Čá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é

3. Diskrétní matematika

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|}$

3. Diskrétní matematika

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$

3. Diskrétní matematika

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$

3. Diskrétní matematika

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

3. Diskrétní matematika

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$

3. Diskrétní matematika

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$

3. Diskrétní matematika

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$

3. Diskrétní matematika

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“

4. Teorie grafů

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\}$

4. Teorie grafů

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ň

4. Teorie grafů

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)

4. Teorie grafů

Ekvivalentní charakteristiky stromů

G je souvislý a acyklický (strom)
mezi vrcholy $u, v$ existuje právě jedna cesta (jednoznačně souvislý)
G je souvislý a po smazání libovolné jedné hrany už nebude souvislý (minimální souvislý)
G je acyklický a po přidání libovolné jedné hrany vznikne cyklus (maximální acyklický)
G je souvislý a platí pro něj Eulerova formule $|E(G)|=|V(G)|-1$

4. Teorie grafů

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á)

4. Teorie grafů

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

4. Teorie grafů

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

4. Teorie grafů

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

4. Teorie grafů

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

4. Teorie grafů

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ý

4. Teorie grafů

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

4. Teorie grafů

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})$

4. Teorie grafů

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í)

5. Pravděpodobnost a statistika

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

5. Pravděpodobnost a statistika

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é

5. Pravděpodobnost a statistika

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)}$

5. Pravděpodobnost a statistika

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$

5. Pravděpodobnost a statistika

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$

5. Pravděpodobnost a statistika

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)$

5. Pravděpodobnost a statistika

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$

5. Pravděpodobnost a statistika

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$

5. Pravděpodobnost a statistika

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

5. Pravděpodobnost a statistika

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

5. Pravděpodobnost a statistika

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)$

5. Pravděpodobnost a statistika

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)$

6. Logika

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á)

6. Logika

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

6. Logika

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)

6. Logika

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$ )

6. Logika

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$

6. Logika

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ý)

6. Logika

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$

6. Logika

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

6. Logika

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

6. Logika

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á

6. Logika

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