diff options
Added information about induction and set completement
1 files changed, 21 insertions, 0 deletions
| -rw-r--r-- | Year 1/Discrete math/notes.tex | 21 |
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$ |
