%
% 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=/*,*/
Platon Group <platon@platon.org> http://platon.org/
|