%
% 04-diskretna-matematika.tex
%
% Developed by Ondrej Jombik <nepto@platon.sk>
% Copyright (c) 2005 Platon SDG, http://platon.sk/
% Licensed under terms of GNU General Public License.
% All rights reserved.
%
% Changelog:
% 2005-01-15 - created
%

% $Platon: doc/statnica-matematika/04-diskretna-matematika.tex,v 1.3 2005/01/18 10:24:47 nepto Exp $

\chapter{Diskrétna matematika}

\section{Výroky a dôkazy} % /*

\begin{defn}
	\underline{Výrok} je:
	\begin{itemize}
		\item tvrdenie, o ktorého pravdivosti alebo nepravdivosti má zmysel uvažovať
		\item {\it pravdivý} alebo {\it nepravdivý}
		\item oznamovacia veta
	\end{itemize}
\end{defn}

\begin{defn}
	\underline{Výroková forma} alebo formula je výrok, ktorý obsahuje premenné. Ak obsahuje
	kvantifikátory $\forall, \exists$ tak je to \underline{kvantifikovaná formula}.
\end{defn}

\begin{defn}
	\underline{Matematický dôkaz} tvrdenia $T$ je konečná postupnosť $a_1, a_2, ..., a_n$, kde $a_i$
	je výrok alebo formula a implikácie $a_1 \to a_2$, $a_2 \to a_3, ..., a_{n-1} \to a_n = T$ sú
	tautológie.
\end{defn}

\begin{defn}
	Základné typy dôkazov:
	\begin{enumerate}
		\item Priamy
		\item Nepriamy
		\item Obmenou ($a \to b \equiv \lnot b \to \lnot a$)
		\item Matematickou indukciou
	\end{enumerate}
\end{defn}

% */

\section{Relácie} % /*

\begin{defn}
	Relácia $\varphi$ je \underline{reláciou ekvivalencie} na $A$, ak spĺňa nasledujúce vlastnosti:
	\begin{enumerate}
		\item \underline{reflexívnosť}: $\forall a \in A: (a, a) \in \varphi$
		\item \underline{symetrickosť}: $\forall a, b \in A: (a, b) \in \varphi \Leftrightarrow (b, a)
			\in \varphi$
		\item \underline{tranzitívnosť}: $\forall a, b, c \in A: (a, b) \in \varphi \land (b, c)
			\in \varphi \Rightarrow (a, c) \in \varphi$
	\end{enumerate}
	Príslušnosť $(a, b) \in \varphi$ značíme $a \sim b$.
\end{defn}

\begin{defn}
	Majme nasledujúce vlastnosti relácie $\varphi$:
	\begin{enumerate}
		\item \underline{asymetrickosť}: $(a, b) \in \varphi \Rightarrow (b, a) \notin \varphi$
		\item \underline{trichotomickosť}: $a \ne b \Rightarrow (a, b) \in \varphi \lor (b, a) \in
			\varphi$
		\item \underline{zobrazenie}: $\varphi \subseteq A \times B$ je zobrazenie ak $(\forall a \in A)
			(\exists ! b \in B): (a, b) \in \varphi$
	\end{enumerate}
	Relácia sa nazýva \underline{čiastočné usporiadanie}, ak je tranzitívna a asymetrická.
	Relácia sa nazýva \underline{(lineárne) usporiadanie}, ak je tranzitívna, asymetrická a
	trichotomická.
\end{defn}

% */

\section{Množiny a mohutnosti} % /*

\begin{defn}
	Systém $\mathcal{S} \subseteq P(A)$ sa nazýva \underline{rozklad množiny $A$}, ak $\mathcal{S}$
	je systém po dvoch disjunktných neprázdnych množín s vlastnosťou $\bigcup_{M \in \mathcal{S}} M
	= A$.
\end{defn}

\begin{defn}
	Majme reláciu ekvivalencie a definujme množinu $A(x)$ tak, že $A(x) = \{ y \in A ~|~ x \sim y \}$.
	Potom $\mathcal{S} = \{ A(x) \in P(A) ~|~ x \in A \}$ je rozklad množiny $A$.
\end{defn}

\begin{defn}
	Množiny $A$ a $B$ majú \underline{rovnakú mohutnosť} ak existuje bijektívne zobrazenie
	$f: A \to B$. Značíme $|A| \equiv |B|$.

	Ak existuje injektívne zobrazenie $f: A \to B$, potom $|A| \le |B|$.\\
	Ak $|A| \le |B| \land |A| \ne |B|$, potom $|A| < |B|$.
\end{defn}

\begin{defn}
	Množina $A$ je \underline{spočítateľná} $\Leftrightarrow |A| = \aleph_0$.\\
	Množina $A$ je \underline{konečná} $\Leftrightarrow |A| < \aleph_0$.
\end{defn}

\begin{defn}[Kardinálne číslo]
	Množiny rozdelíme do tried ekvivalencie podľa počtu prvkov. Z každej triedy vyberieme jednu
	zastupujúcu množinu, tzv. \underline{kardinálne číslo}.
	$$
	\begin{array}{ccccl}
		|X| & = & 0 & = & \emptyset\\
		|X| & = & 1 & = & \{ \emptyset \} \\
		|X| & = & 2 & = & \{ \emptyset, \{ \emptyset \} \} \\
		\vdots & & & & \\
	\end{array}
	$$

	Potom definujeme:
	\begin{itemize}
		\item \underline{súčet}: $|A| + |B| = |A \times \{ \emptyset \} \cup B \times \{ \{
			\emptyset \} \}|$
		\item \underline{súčin}: $|A| \cdot |B| = |A \times B|$
		\item \underline{mocnina}: $|A|^{|B|} = |\textrm{Množina $\forall$ zobrazení $f: B \to A$}|$
		\end{itemize}
\end{defn}

% */

% TODO Kombinatorika

\section{Cantor-Bernsteinova veta} % /*

\begin{veta}[Cantor-Bernstein]
	$$|A| \le |B| \land |B| \le |A| \Rightarrow |A| = |B|$$
\end{veta}

\begin{dokaz}
	Dokazujeme, že ak existuje injekcia $f: A \to B$ a zároveň injekcia $g: B \to A$, potom $|A| =
	|B|$. Vyjadríme si množiny $A_1 = g(B), A_2 = g(f(A)), A_3 = g(f(A_1))$. Dostávame $A \supseteq
	A_1 \supseteq A_2 \supseteq ... \supseteq A_k \supseteq ...$. Označme $D = \bigcap_{i=0}^\infty
	A_i$. Potom $A = D \cup (A - A_1) \cup (A_1 - A_2) \cup ...$ a tiež 
	            $A_1 = D \cup (A_1 - A_2) \cup (A_2 - A_3) \cup ...$.\\
	\dots
\end{dokaz}

% */

\section{Cantorova veta} % /*

\begin{veta}[Cantorova]
	Pre každú množinu $X \ne \emptyset$ platí $|X| < |P(X)|$, kde $P(X) = \{ Y ~|~ Y \subset X \}$.
\end{veta}

\begin{dosledok}
	$$|X| < 2^{|X|} = P(X)$$
\end{dosledok}

\begin{dosledok}
	Neexistuje množina všetkých množín.
\end{dosledok}

% */

\section{Princíp zapojenia a vypojenia} % /*

\begin{veta}[Zapojenie-vypojenie]
	Nech $A_1, A_2, ..., A_n$ sú konečné množiny. Pre $\forall k = 1, 2, ..., n$ položme $$S_k = \sum_{1 \le
	i_1 < i_2 < ... < i_k \le n} | A_{i_1} \cap A_{i_2} \cap ... \cap A_{i_k}|$$ kde sumačný
	symbol sa vzťahuje na všetky podmnožiny $\{i_1, i_2, ..., i_k\}$ množiny $\{1, 2, ..., n\}$.
	Potom $$|A_1 \cup A_2 \cup ... \cup A_n| = \sum_{k=1}^n (-1)^{k+1} S_k$$
\end{veta}

\begin{dokaz}
	Úvahou alebo matematickou indukciou vzhľadom na počet množín.
\end{dokaz}

\begin{veta}
	Nech $S^A_B$ je množina všetkých surjektívnych zobrazení z $A$ do $B$. Nech $|A| = m$, $|B| =
	n$ a $B = \{ b_1, b_2, ..., b_n \}$. Potom $$|S^A_B| = \sum_{k=0}^n (-1)^k {n \choose k} (n-k)^m$$
\end{veta}

\begin{dokaz}
	Všetkých zobrazení je $n^m$. Musíme odpočítať počet nesurjekcií $|S'^A_B|$. To sú také
	zobrazenia $f: A \to [ B - \{ 1~prvok \} ]$. Takýchto zobrazení je $(n-1)^m$. Takýchto prvkov je
	${n \choose 1}$, čize celkom je to ${n \choose 1}(n-1)^m$ zobrazení. Podobne pre dva prvky je to
	${n \choose 2}(n-2)^m$. Pomocou princípu zapojenia a vypojenia dostávame celkový počet
	nesurjekcií: $$|S'^A_B| = \sum_{k=1}^n (-1)^{k+1} {n \choose k} (n - k)^m$$ Výsledný počet
	zobrazení je teda $$|S^A_B| = n^m - |S'^A_B| = \sum_{k=1}^n (-1)^k {n \choose k} (n-k)^m$$
\end{dokaz}

\begin{veta}
	Nech $A_1, A_2, ..., A_n$ sú konečné množiny. Nech $A(r)$ označuje počet prvkov, ktoré sa
	nachádzajú v práve $r$ množinách a $A'(r)$ označuje počet prvkov, ktoré sa nachádzajú v aspoň
	$r$ množinách. Potom
	$$ A(r) = \sum_{k=r}^n (-1)^{k-r} {k \choose r} S_k ~~~~~ r = 0, 1, ..., n$$
	$$ A'(r) = \sum_{k=r}^n (-1)^{k-r} {{k-1} \choose {r-1}} S_k ~~~~~ r = 1, 2, ..., n$$
\end{veta}

% */

\section{Dirichletov princíp} % /*

\begin{veta}
	Nech $X, Y$ sú konečné množiny a $f$ je zobrazenie množiny $X$ do~$Y$. Ak $|X| > |Y|$, tak
	existuje také $y \in Y$, že aspoň pre dva rôzne prvky $x_1, x_2 \in X$ platí $f(x_1) = f(x_2) =
	y$.
\end{veta}

\begin{veta}
	Nech $f$ je zobrazenie množiny $X$ do $Y$. Nech $\lambda \in \mathbb{N}^+$. Ak $\lambda \cdot
	|Y| < |X|$, tak $\exists y \in Y$ také, že množina $\{ x \in X ~|~ f(x) = y \}$ má mohutnosť
	väčšiu než $\lambda$.
\end{veta}

% */

\section{Spernerova veta} % /*

\begin{veta}[Spernerova]
	Nech $A$ je konečná množina o $n$ prvkoch a $A_1, A_2, ..., A_m$ sú jej neprázdne konečné
	podmnožiny také, že $A_i \notsubseteq A_j, i \ne j$, tj. nezapadajú do seba. Potom platí $$ m
	\le {n \choose {\lfloor \frac{n}{2} \rfloor}}$$ kde $|A| = n$, tj. $m$ je maximálny možný počet
	takých množín.
\end{veta}

% */

\section{Ko:nigova veta} % /*

\begin{veta}[Ko:nigova o strome]
	Nech každý vrchol stromu $T$ má konečný stupeň vetvenia. Ak mám nekonečný počet vrcholov, potom
	existuje v strome aspoň jedna nekonečne dlhá vetva.
\end{veta}

% */

\section{Ramseyho čísla} % /*

\begin{defn}
	Každý graf, ktorý má aspoň $R(m, n)$ vrcholov buď obsahuje $K_m$ ako svoj podgraf, alebo
	doplnok grafu obsahuje $K_n$ ako svoj podgraf.
\end{defn}

\begin{veta}[E:rdos, Sekeres]
	Pre $m,n \ge 2$ platí: $$R(m, n) \le R(m, n - 1) + R(m - 1, n)$$
\end{veta}

\begin{veta}
	Pre $m,n \ge 2$ platí: $$R(m, n) \le {m + n - 1 \choose n - 1}$$
\end{veta}

\begin{veta}[Ramseyho]
	Pre ľubovoľné $m, n \ge 2, m, n \in \mathbb{N}$ existuje prirodzené číslo $R(m, n)$ také, že pre
	každé číslo $r \ge R(m, n)$ platí, že pri ľubovoľnom zafarbení hrán grafu $K_r$ dvoma farbami v
	ňom existuje jednofarebný podgraf $K_m$ ofarbený prvou farbou alebo jednofarebný podgraf $K_n$
	ofarbený druhou farbou.
\end{veta}

% */

\section{Systémy reprezentantov} % /*

\begin{veta}[Hallova]
	Pre systém $M = (S_1, S_2, ..., S_m)$ existuje $m$-tica navzájom rôznych reprezentantov práve
	vtedy, keď zjednotenie ľubovoľných $k$-množín obsahuje aspoň $k$ prvkov.
\end{veta}

\begin{veta}[Ko:nigova]
	V ľubovoľnej binárnej matici je najväčší počet po dvoch nezávislých jendotlivých prvkov rovný
	najmenšiemu počtu buniek pokrývajúcich všetky jednotky.
\end{veta}

% */

% vim: ts=4 tw=100
% vim600: fdl=0 fdm=marker fdc=0 fmr=/*,*/