From 99da7f6b6b662d9ea31d2029e18fb13a9c52722d Mon Sep 17 00:00:00 2001 From: Syndamia Date: Sat, 4 Dec 2021 11:39:38 +0200 Subject: Added information about induction and set completement --- Year 1/Discrete math/notes.tex | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+) diff --git a/Year 1/Discrete math/notes.tex b/Year 1/Discrete math/notes.tex index a4d3b73..404a009 100644 --- a/Year 1/Discrete math/notes.tex +++ b/Year 1/Discrete math/notes.tex @@ -92,6 +92,9 @@ \item \emph{Симетрична разлика} \newline $A \triangle B = \left\{ a \mid 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\}$ + + \item \emph{Допълнение} на множество $A$ до универсум $U$ \newline + $\overline{A^U} = \left\{ a \mid a \in U \land a \notin A \right\}$ \quad Ако $U$ се подразбира, пишем само $\overline{A}$ \end{enumerate} \subsection{Наредена двойка} @@ -126,6 +129,24 @@ \end{enumerate} +\subsection{Доказателство по индукция} + +\begin{enumerate} + \item \emph{Обикновена индукция} + \begin{enumerate} + \item \emph{База}: Проверяваме за най-ниската възможна стойност \hfill $P(0), n \geq 0$ + \item \emph{Индукционно предположение}: Допускаме че е вярно за произволна стойност \hfill $P(n)$ + \item \emph{Индукционна стъпка}: Доказваме че е вярно за следващата произволна стойност, въз основа на индукционното предположение \hfill $P(n + 1)$ + \end{enumerate} + + \item \emph{Силна индукция} + \begin{enumerate} + \item \emph{База}: Проверяваме за най-ниската възможна стойност \hfill $P(0), n \geq 0$ + \item \emph{Индукционно предположение}: Допускаме, че е вярно за всички стойности от най-ниската до произволно $n$ \hfill $P(0), P(1), ..., P(n)$ + \item \emph{Индукционна стъпка}: Доказваме че е вярно за следващата произволна стойност, въз основа на индукционното предположение \hfill $P(n + 1)$ + \end{enumerate} +\end{enumerate} + \section{\underline{Релации}} Релация над декартовото произведение $A_1 \times A_2 \times ... \times A_n$ се нарича всяко множество $R \subseteq A_1 \times A_2 \times ... \times A_n$ -- cgit v1.3.1-26-gb76a