Summary Files Commits Branches @commit @diff @stats
diff options
context:
space:
mode:
Commit78564c227e610db6214f62af5cfd158c6658a478 (patch)
Author
 Syndamia <kamen.d.mladenov@protonmail.com>
2021-12-02 18:34:37 +0200
Committer
 Syndamia <kamen.d.mladenov@protonmail.com>
2021-12-02 18:34:37 +0200
Filesa8f49bb3f14d99145a05ba4468c107afed28b7d1
uni-projects-78564c227e610db6214f62af5cfd158c6658a478.tar
uni-projects-78564c227e610db6214f62af5cfd158c6658a478.tar.gz
uni-projects-78564c227e610db6214f62af5cfd158c6658a478.zip
Parent38207fcdaa3e3adb93302e3c4b6b5eb39cfed36b (diff)
Added discrete math notes
2 files changed, 339 insertions, 0 deletions
-rw-r--r--Year 1/Discrete math/notes.pdfbin0 -> 65256 bytes
-rw-r--r--Year 1/Discrete math/notes.tex339
diff --git a/Year 1/Discrete math/notes.pdf b/Year 1/Discrete math/notes.pdf
new file mode 100644
index 0000000..c799897
--- /dev/null
+++ b/Year 1/Discrete math/notes.pdf
Binary files differ
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}