Platon Technologies
not logged in Login Registration
EnglishSlovak
open source software development celebrating 10 years of open source development! Friday, March 29, 2024

File: [Platon] / doc / statnica-matematika / 04-diskretna-matematika.tex (download)

Revision 1.4, Thu Feb 3 09:44:18 2005 UTC (19 years, 1 month ago) by nepto


Changes since 1.3: +3 -5 lines

Fixed several typos and errors in text.

%
% 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/
Copyright © 2002-2006 Platon Group
Site powered by Metafox CMS
Go to Top