diff options
Added discrete math notes
2 files changed, 339 insertions, 0 deletions
| -rw-r--r-- | Year 1/Discrete math/notes.pdf | bin | 0 -> 65256 bytes | |||
| -rw-r--r-- | Year 1/Discrete math/notes.tex | 339 |
diff --git a/Year 1/Discrete math/notes.pdf b/Year 1/Discrete math/notes.pdf Binary files differnew file mode 100644 index 0000000..c799897 --- /dev/null +++ b/Year 1/Discrete math/notes.pdf diff --git a/Year 1/Discrete math/notes.tex b/Year 1/Discrete math/notes.tex new file mode 100644 index 0000000..2255123 --- /dev/null +++ b/Year 1/Discrete math/notes.tex @@ -0,0 +1,339 @@ +% Document MUST be built with XeLaTeX! +\documentclass[11pt,a4paper]{article} + +\usepackage[margin=1.5cm]{geometry} + +% Поддръжка на български език +% Thanks to https://tex.stackexchange.com/a/136926 +\usepackage{fontspec} +\defaultfontfeatures{Ligatures=TeX} +\setmainfont{CMU Serif} +\setsansfont{CMU Sans Serif} + +\usepackage[bulgarian,english]{babel} + +\usepackage{amsmath} % Математически символи +\usepackage{amsfonts} % Още математически символи +\usepackage{hyperref} % Линкове +\usepackage{cancel} % Зачертаване +\usepackage[dvipsnames]{xcolor} % Цветни кутийки + допълнителни цветове + +\usepackage{enumitem} +\setlist[enumerate]{label=\arabic*.} + +\renewcommand{\thesection}{Лекция \arabic{section}} +\renewcommand{\thesubsection}{\quad\arabic{section}.\arabic{subsection}} + +\begin{document} + +\section{\underline{Съждителна логика}} + +\begin{tabular}{l|l} + \hline \\[-0.9em] + \textbf{Свойства на константите} & $p \land T \equiv p, \quad p \lor F \equiv p, \quad p \lor T \equiv T, \quad p \land F \equiv F$ \\[0.2em] + \hline \\[-0.9em] + \textbf{Свойства на отрицанието} & $p \land \neg p \equiv F, \quad p \lor \neg p \equiv T$ \\[0.2em] + \hline \\[-0.9em] + \textbf{Закон за двойното отрицание} & $\neg (\neg p) \equiv p$ \\[0.2em] + \hline \\[-0.9em] + \textbf{Идемпотентност} & $p \lor p \equiv p, \quad p \land p \equiv p$ \\[0.2em] + \hline \\[-0.9em] + \textbf{Комутативност} & $p \lor q \equiv q \lor p, \quad p \land q \equiv q \land p$ \\[0.2em] + \hline \\[-0.9em] + \textbf{Асоциативност} & $(p \lor q) \lor r \equiv p \lor (q \lor r), \quad (p \land q) \land r \equiv p \land (q \land r)$ \\[0.2em] + \hline \\[-0.9em] + \textbf{Дистрибутивност} & $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r), \quad p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$ \\[0.2em] + \hline \\[-0.9em] + \textbf{Закони на De Morgan} & $\neg (p \lor q) \equiv \neg p \land \neg q, \quad \neg (p \land q) \equiv \neg p \lor \neg q$ \\[0.2em] + \hline \\[-0.9em] + \textbf{Поглъщане} & $p \lor (p \land q) \equiv p, \quad p \land (p \lor q) \equiv p$ \\[0.2em] + \hline \\[-0.9em] + \textbf{Свойство на импликацията} & $p \rightarrow q \equiv \neg p \lor q$ \\[0.2em] + \hline \\[-0.9em] + \textbf{Свойство на би-импликацията} & $p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)$ \\[0.2em] + \hline +\end{tabular} + + +\section{\underline{Множества}} + +Множество, което не съдържа себе си, е обикновено. +Множество, което съдържа себе си, е необикновено. + +\subsection{Аксиоми} + +\begin{enumerate} + \item \emph{Аксиома за обема} \newline Две множества са равни тстк съдържат едни и същи елементи (редът е без значение) + + \item \emph{Аксиома за отделянето} \newline Ако $X$ е множество и $\pi$ е предикат с домейн $X$, то съвкупността $Y$ от елементите на $X$, които имат свойството $\pi$, е множество. \newline \newline $B = \left\{a \in A \;|\; \pi(a) \right\}$ Казваме, че B е подмножество на A + + \item \emph{Аксиома за степенното множество} \newline За всяко множество $X$ съществува множеството от всички негови подмножества, което наричаме степенното множество на $X$ + + \item \emph{Максимално по включване множество} \newline Множество, за което свойството (предикатът) е в сила, но то не е в сила за никое същинско негово надмножество. + \begin{enumerate} + \item $\sigma (B)$ и + \item $\forall C\left( B \subset C \subseteq A \rightarrow \neg \sigma (C) \right)$ + \end{enumerate} + \emph{Минимално по включване множество} \newline Такова подмножество, за което свойството (предикатът) е в сила, но то не е в сила за никое същинско негово подмножество. + \begin{enumerate} + \item $\sigma (B)$ и + \item $\forall C\left( C \subset B \rightarrow \neg \sigma (C) \right)$ + \end{enumerate} +\end{enumerate} + +\subsection{Операции} + +\begin{enumerate} + \item \emph{Симетрична разлика} \newline \newline + $A \triangle B = \left\{ a \;|\; a \in A \oplus a \in B \right\}$ \qquad\qquad Пример: + $\left\{ a, b, c, d \right\} \triangle \left\{ a, b, x, y \right\} = \left\{ c, d, x, y \right\}$ +\end{enumerate} + +\subsection{Наредена двойка} + +(Дефиниция на Kuratowski) Всяко множество $\left\{\{a\}, \{a, b\}\right\}$ наричаме наредена двойка с първи елемент a и втори елемент b. Краткият запис е “$(a, b)$”. + +\subsection{Разбиване и покриване} + +\begin{enumerate} + \item \emph{Покриване на $A$} \newline + Всяка фамилия $X = \left\{X_1, X_2, ..., X_k \right\}, k \geq 0$, където + + \begin{enumerate} + \item $\forall i \in \left\{ 1, 2, ..., k \right\} : X_i \subseteq A$ + \item $\forall i \in \left\{ 1, 2, ..., k \right\} : X_i \neq \emptyset$ + \item $\bigcup\limits_{i = 1}^{k} X_i = A$ + \end{enumerate} + Тоест, всяка фамилия, чието обединение на множества е даденото множество. \newline + Пример: $A = \left\{ a, b, c, d \right\} \qquad X = \left\{ \{a, b, d\}, \{b, c\}, \{a, b, c, d\} \right\}$ + + \item \emph{Разбиване на $A$} \newline + Всяка фамилия $X = \left\{X_1, X_2, ..., X_k \right\}, k \geq 0$, където + + \begin{enumerate} + \item $\forall i \in \left\{ 1, 2, ..., k \right\} : X_i \subseteq A$ + \item $\forall i \in \left\{ 1, 2, ..., k \right\} : X_i \neq \emptyset$ + \item $\bigcup\limits_{i = 1}^{k} X_i = A$ + \item $\forall i \forall j (1 \leq i < j \leq k \rightarrow X_i \cap X_j = \emptyset)$ + \end{enumerate} + Тоест, покриване, при което няма общи елементи между множествата във фамилията. \newline + Пример: $A = \left\{ a, b, c, d \right\} \qquad X = \left\{ \{a, c\}, \{b\}, \{c\} \right\}$ + +\end{enumerate} + +\section{\underline{Релации}} + +Релация над декартовото произведение $A_1 \times A_2 \times ... \times A_n$ се нарича всяко множество $R \subseteq A_1 \times A_2 \times ... \times A_n$ + +\subsection{Свойства на релации от вида $R \subseteq A^2$} + +\begin{enumerate} + \item \emph{Рефлексивност} \qquad\qquad $\forall a \in A : aRa$ \newline + \emph{Антирефлексивност} \qquad $\forall a \in A : \neg aRa$ + + \item \emph{Симетричност} \qquad\qquad\qquad $\forall a, b \in A, a \neq b : aRb \rightarrow bRa$ \newline + \emph{Антисиметричност} \qquad\qquad $\forall a, b \in A, a \neq b : aRb \rightarrow \neg bRa$ \newline + \emph{Силна антисиметричност} \quad $\forall a, b \in A, a \neq b : aRb \oplus bRa$ \newline + + \item \emph{Транзитивност} \qquad $\forall a, b, c \in A : aRb \land bRc \rightarrow aRc$ +\end{enumerate} + +\subsubsection{Затваряне на релации} + +\begin{enumerate} + \item \emph{Рефлексивно затваряне} $R'$ + \begin{enumerate} + \item $R' \subseteq A^2$ + \item $R \subseteq R'$ + \item $R'$ е рефлексивна + \end{enumerate} +\end{enumerate} + +Аналогично за симетрично и транзитивно затваряне + +\subsubsection{Типове релации} + +\begin{enumerate} + \item \emph{Релация на еквивалентност}: рефлексивна, симетрична, транзитивна \newline + \emph{Класове на еквивалентност}: $[a] = \{ b \in A \;|\; aRb \}$ + + \item \emph{Релация на частична наредба}: рефлексивна, антисиметрична, транзитивна \newline + \emph{Минимален елемент}: \; $a$ е минимален, ако $\neg \exists b \in A, a \neq b : bRa$ \newline + \emph{Максимален елемент}: $a$ е максимален, ако $\neg \exists b \in A, a \neq b : aRb$ \newline \newline + \emph{Релация на частична строга наредба}: рефлексивна, антисиметрична, транзитивна + + \item \emph{Релация на линейна наредба}: рефлексивна, силно антисиметрична, транзитивна \newline + \emph{Линейно разширение}: Частична наредба $R$, линейна наредба $R'$, $R \subseteq R' \implies R'$ е линейно разширение на $R$ \newline \newline + \emph{Релация на линейна строга наредба}: антирефлексивна, силно антисиметрична, транзитивна +\end{enumerate} + +\subsubsection{Верига и контур} + +\begin{itemize} + \item \emph{Верига}: всяка редица $a_{i_0}, a_{i_1}, ..., a_{i_k} \;\text{, където }\\ i_0,...,i_k \in \{1,...,n\}, \, a_{i_j} \, R \, a_{i_{j + 1}} \;\text{ и }\; a_{i_j} \neq a_{i_{j + 1}} \;\text{ за }\; 0 \leq j < k$ \newline \newline + Дефакто, редица от елементи, където всеки два съседни елемента са в релация. \newline Веригите НЕ минават през примки! + + \item \emph{Контур}: всяка верига, за която е вярно и, че $a_{i_0} = a_{i_k} \text{ за } k > 0$ \newline \newline + Дефакто, редица от елементи, където всеки два съседни елемента са в релация и първия и последния също са в релация. +\end{itemize} + +\section{\underline{Функции}} + +\begin{itemize} + \item \emph{Тотална функция}: Всяка релация $f \subseteq X \times Y$, където за всяко $x$ има точно едно $y : (x, y) \in f$ + \item \emph{Частична функция}: Всяка релация $f \subseteq X \times Y$, където за всяко $x$ има поне едно $y : (x, y) \in f$ +\end{itemize} + +\subsection{Свойства} + +\begin{enumerate} + \item \emph{Инекция}: Всеки елемент води до единствен друг елемент (може не всички елемeнти от другите да са "покрити") + \item \emph{Сюрекция}: Всеки елемент от другите е "покрит" от един или повече елементи + \item \emph{Биекция}: Едно към едно връзка между елементите и другите +\end{enumerate} + +\begin{itemize} + \item \emph{Крайно множество}: Ако $A$ е празно, то имаме кардиналност 0. Иначе, трябва да съществува $n$, за което имаме биекция $f : A \rightarrow \{1, 2, ..., n\}$ + + \item \emph{Безкрайно множество}: Ако не е крайно \newline + \emph{Изброимо безкрайно мнжоество}: Ако е равномощно на $\mathbb{N}$ +\end{itemize} + +\subsubsection{Принцип на Дирихле} + +За крайни $X$ и $Y$, $|X| > |Y|$, то не съществува инекция $f : X \rightarrow Y$ + +Ако има $m$ обекта в $n$ чекмеджета и $m > n$, то в поне едно чекмедже има повече от един обект. + +\section{\underline{Изброителна комбинаторика}} + +\subsection{Принципи} + +\begin{enumerate} + \item \emph{Принцип на Дирихле} + + \item \emph{Принцип на разбиването} \newline + Кардиналността е сума от кардиналностите на дяловете на разбиване. \newline + За множество $X$ и негови разбивания $\left\{ Y_1, ..., Y_k \right\}$, имаме $|A| = |Y_1| + ... + |Y_k| = \sum\limits_{i = 1}^{k} |Y_i|$ \newline \newline + \emph{Принцип на изваждането} (следствие от Принцип на разбиването) \newline + За множество $A$ и универсум $U$, имаме $|A| = |U| - \left| \overline{A} \right|$ + + \item \emph{Принцип на умножението}: $|A \times B| = |A| * |B|$ + + \item \emph{Принцип на биекцията}: $|A| = |B|$ тстк съществува биекция $f : A \rightarrow B$ + + \item \emph{Принцип на делението} \newline + За $k = $ брой класове на еквивалентност, $\left| [a] \right| = m$, имаме $m = \frac{|A|}{k}$ + + \item \emph{Принцип на включването и изключването} \newline + Кардиналността е сума от дяловете на покритие със изваждане на техни сечения. \newline + $|A_1 \cup ... \cup A_n| = \sum\limits_{1 \leq i \leq n} |A_i| - \sum\limits_{1 \leq i < j \leq n} |A_i \cap A_j| + ... + (-1)^{(n-1)} \cdot |A_1 \cap ... \cap A_n|$ +\end{enumerate} + +\section{\underline{Комбинаторни конфигурации}} + +Дадено е опорно множество $А = {a1, a2, ..., an}$ чрез което ще изграждаме комбинаторни конфигурации. +Общоприето е, че $n$ е брой елементи в $A$, $m$ е брой елементи в конфигурация. + +\begin{enumerate} + \item \emph{Множество от конфигурации с наредба, с повтаряне} \newline + $\text{К}_\text{Н, П}(n, m) = A^m \qquad\qquad \left| \text{К}_\text{Н, П}(n, m) \right| = |A^m| = n^m$ + + \item \emph{Множество от конфигурации с наредба, без повтаряне} \newline + $\text{К}_\text{Н}(n, m) \qquad\qquad \left| \text{К}_\text{Н}(n, m) \right| = n \cdot (n-1) \cdot (n-2) \cdot ... \cdot (n - m + 1) = n^{\underline{m}}$ \newline\newline + \emph{Пермутации с повторения}: частен случай, когато $n = m$. $\left| \text{К}_\text{Н}(n, m) \right| = n!$ + + \item \emph{Множество от конфигурации без наредба, без повтаряне}: просто комбинации/подмножество \newline + $\text{К}(n, m) \qquad\qquad \left| \text{К}(n, m) \right| = \frac{\left| \text{К}_\text{Н}(n, m) \right|}{m!} = \frac{n!}{(n-m)!m!} = \frac{n^{\underline{m}}}{m!} = \binom{n}{m}$ +\end{enumerate} + +\subsection{Нютонов бином} + +\begin{equation*} + (x + y)^n = \sum_{k = 0}^n \binom{n}{k} \cdot n^k \cdot y^{(n - k)} +\end{equation*} + +\section{\underline{Рекурентни уравнения}} + +Уравнение, при което дясната му страна включва и самото уравнение и имаме начално условие(ия) + +\begin{align*} + & \text{Пример: } L(n) = + \begin{cases} + L(n-1) + n, & \text{ ако } n \in \mathbb{N}^+ \\ + 1, & \text{ ако } n = 0 + \end{cases} +\end{align*} + +\subsection{Алгоритъм за решаване на линейно рекурентно уравнение с константни коефициенти и крайна история} + +\begin{align*} + & F_n = + \begin{cases} + F_{n-1} + F_{n-2}, & \text{ ако } n \geq 2 \\ + 1, & \text{ ако } n = 1 \\ + 0, & \text{ ако } n = 0 + \end{cases} + \text{ е такова валидно уравнение} \\ + & \text{Обаче, следните уравнения не могат да се решат с този метод:} \\ + & T_n = + \begin{cases} + n \cdot T_{n-1} & \text{ ако } n \geq 1 \\ + 1, & \text{ ако } n = 0 + \end{cases} + \text{ защото не е с константи коефициенти} \\ + & S_n = + \begin{cases} + S_{n-1} + S_{n-2} + ... + S_1 + S_0, & \text{ ако } n \geq 1 \\ + 1, & \text{ ако } n = 0 + \end{cases} + \text{ защото не е с крайна история} +\end{align*} + +За илюстриране на метода, нека да разгледаме $a_n = c_1 a_{n-1} + c_2 a_{n-2} + ... + c_k a_{n-k}$ + +\begin{enumerate} + \item \emph{Характеристично уравнение} \newline + Заместваме $a_n$ с $x^n$, $a_{n-1}$ с $x^{n-1}$ и так. нат. \hfill $x^n = c_1 x^{n-1} + c_2 x^{n-2} + ... + c_k x^{n-k}$ \newline + След това, делим всичко на $x^{(n-k)}$ \hfill $x^k = c_1 x^{k-1} + c_2 x^{k-2} + ... + c_k$ \newline + Алтернативно, може да се запише и като \hfill $x^k - c_1 x^{k-1} - c_2 x^{k-2} - ... - c_k = 0$ + + \item \emph{Общо решение} \newline + Намираме корените на хар. уравнение. \hfill Нека те да са мултимножеството $\{ \alpha_1, \alpha_2, ..., \alpha_k \}_{\text{М}}$ \newline + Съставяме уравнението \hfill $a_n = A_1 \cdot \alpha_1^n + A_2 \cdot \alpha_2^n + ... + A_k \cdot \alpha_k^n$ \newline\newline + Ако имаме еднакви корени, умножаваме с $n^r$, където $r \in \mathbb{N}$ е r-тия повтарящ се корен. \newline + Тоест, ако да имаме 5 корена, за които $\alpha_1 = \alpha_2 = \alpha_3 \neq \alpha_4 \neq \alpha_5$, ще изглежда така: \newline + $a_n = A_1 \alpha_1^n \cdot n^0 + A_2 \alpha_2^n \cdot n^1 + A_3 \alpha_3^n \cdot n^2 + A_4 \alpha_4^n + A_5 \alpha_5^n$ + + \item \emph{Точно решение} (Само ако началните условия са ни дадени) \newline + Вземаме първите $k$ на брой начални условия (ако се наложи допълваме, тоест изчисляваме всички стойности до $a_k$). \newline + С тях, съставяме система линейни уравнения за $a_1, a_2, a_3, ...$ + \begin{equation*} + \left| \begin{array}{ccccccccc} + a_1 & = & A_1 \cdot \alpha_1^1 & + & A_2 \cdot \alpha_2^1 & + & ... & + & A_k \cdot \alpha_k^1 \\ + \vdots \\ + a_k & = & A_1 \cdot \alpha_1^k & + & A_2 \cdot \alpha_2^k & + & ... & + & A_k \cdot \alpha_k^k + \end{array} \right. + \end{equation*} + Чрез нея, намираме стойностите на $A_1, ..., A_k$ и заместваме в Общото решение +\end{enumerate} + +\subsection{Решаване на нехомогенно рекурентно уравнение с константни коефициенти и крайна история} + +Говорим за уравнения от типа $a_n = c_1 a_{n-1} + ... + c_k a_{n-k} \quad+\quad p_1(n) \cdot b_1^n + ... + p_l(n) \cdot b_l^n$, \newline където $b_1, ..., b_l$ са различни стойности, а $p_1(n), ..., p_l(n)$ са полиноми на $n$. + +\begin{enumerate} + \item \emph{Характеристично уравнение} \newline + Съставя се по същия начин, като просто си представим, че нехомогенната част (тази с $p_l(n)$-вете) не съществува. + + \item \emph{Общо решение} \newline + След като намерим мултимножеството от корени на хомогенната част, разглеждаме нехомогенната. \newline + Абстрахираме се от всякакви коефициенти и разглеждаме хомогенната част като сборове от комбинации на $n^g \cdot h^n$. \newline + Образуваме мултимножеството от корени на нехомогенната част, като добавяме съответните $h$ $g+1$ пъти. \newline + Накрая обединяваме двете мултимножества и съставяме уравнението. + + \item \emph{Точно решение} \newline + Продължаваме по същия начин. +\end{enumerate} + +\end{document} |
