Summary Files Commits Branches @commit @diff @stats
diff options
context:
space:
mode:
Commit26970c93d171521fd1a7c421a43eed76a9cb36e7 (patch)
Author
 Syndamia <kamen.d.mladenov@protonmail.com>
2021-12-02 13:56:07 +0200
Committer
 Syndamia <kamen.d.mladenov@protonmail.com>
2021-12-02 13:56:07 +0200
Files5d4607deb40f871c78178cc5d5bf7ca3a741f681
uni-projects-26970c93d171521fd1a7c421a43eed76a9cb36e7.tar
uni-projects-26970c93d171521fd1a7c421a43eed76a9cb36e7.tar.gz
uni-projects-26970c93d171521fd1a7c421a43eed76a9cb36e7.zip
Parent6bc2d9c8ca39a3cfa0d557c0211b9391a0ab5ed4 (diff)
Added discrete math notes
1 files changed, 251 insertions, 0 deletions
-rw-r--r--Year 1/Discrete math/notes.md251
diff --git a/Year 1/Discrete math/notes.md b/Year 1/Discrete math/notes.md
new file mode 100644
index 0000000..c1f5b1c
--- /dev/null
+++ b/Year 1/Discrete math/notes.md
@@ -0,0 +1,251 @@
+- *Свойства на константите*
+ p ∧ T ≡ p, p ∨ F ≡ p, p ∨ T ≡ T, p ∧ F ≡ F
+- *Свойства на отрицанието*
+ p ∧ ¬p ≡ F, p ∨ ¬p ≡ T
+- *Закон за двойното отрицание*
+ ¬(¬p) ≡ p
+
+- *Идемпотентност*
+ p ∨ p ≡ p, p ∧ p ≡ p
+- *Комутативност*
+ p ∨ q ≡ q ∨ p, p ∧ q ≡ q ∧ p
+- *Асоциативност*
+ (p ∨ q) ∨ r ≡ p ∨ (q ∨ r), (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
+- *Дистрибутивност*
+ p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
+- *Закони на De Morgan*
+ ¬(p ∨ q) ≡ ¬p ∧ ¬q, ¬(p ∧ q) ≡ ¬p ∨ ¬q
+
+- *Поглъщане*
+ p ∨ (p ∧ q) ≡ p, p ∧ (p ∨ q) ≡ p
+- *Свойство на импликацията*
+ p → q ≡ ¬p ∨ q
+- *Свойство на би-импликацията*
+ p ↔ q ≡ (p → q) ∧ (q → p)
+
+# Лекция 2: Множества
+
+Множество, което не съдържа себе си, е обикновено.
+Множество, което съдържа себе си, е необикновено.
+
+### Аксиоми
+
+- *Аксиома 1: Аксиома за обема*
+ Две множества са равни тстк съдържат едни и същи елементи (редът е без значение)
+
+- *Аксиома 2: Аксиома за отделянето*
+ Ако X е множество и π е предикат с домейн X , то съвкупността Y от елементите на X , които имат свойството π , е множество.
+ B = {a ∈ A : π(a)}. Казваме, че B е подмножество на A
+
+- *Аксиома 3: Аксиома за степенното множество*
+ За всяко множество X съществува множеството от всички негови подмножества, което наричаме степенното множество на X
+
+- *Аксиома 4: Максимално по включване множество*
+ Множество, за което свойството (предикатът) е в сила, но то не е в сила за никое същинско негово надмножество
+ 1) σ(B) и
+ 2) ∀C(B ⊂ C ⊆ A → ¬σ(C))
+
+ *Минимално по включване множество*
+ Такова подмножество, за което свойството (предикатът) е в сила, но то не е в сила за никое същинско негово подмножество.
+ 1) σ(B) и
+ 2) ∀C(C ⊂ B → ¬σ(C))
+
+### Операции
+
+- *Симетрична разлика*
+ A ▵ B = { a | a ∈ A ⊕ a ∈ B }
+ {a, b, c, d} ▵ {a, b, x, y} = {c, d, x, y}
+
+### Наредена двойка
+
+(Дефиниция на Kuratowski) Всяко множество {{a}, {a, b}} наричаме наредена двойка с първи елемент a и втори елемент b. Краткият запис е “(a, b)”.
+
+### Разбиване и покриване
+
+- *Покриване на A*
+ Всяка фамилия X = {X1, X2, ..., Xk}, k >= 0
+ 1) ∀i ∈ {1, 2, ..., k} : Xi ⊆ A
+ 2) ∀i ∈ {1, 2, ..., k} : Xi =/= ∅
+ 3) U_{i = 1} ^{k} Xi = A
+ Тоест, всяка фамилия, чието обединение на множества е даденото множество.
+
+ А = {a, b, c, d}
+ {{a, b, d}, {b, c}, {a, b, c, d}}
+
+- *Разбиване на A*
+ Всяка фамилия X = {X1, X2, ..., Xk}, k >= 0
+ 1) ∀i ∈ {1, 2, ..., k} : Xi ⊆ A
+ 2) ∀i ∈ {1, 2, ..., k} : Xi =/= ∅
+ 3) U_{i = 1} ^{k} Xi = A
+ 4) ∀i∀j(1 <= i < j <= k → Xi ∩ Xj = ∅)
+ Тоест, покриване, при което няма общи елементи между множествата във фамилията.
+
+ {{a, c}, {b}, {c}}
+
+# Лекция 3: Релации
+
+Релация над декартовото произведение A1 x A2 x ... x An се нарича всяко множество R ⊆ A1 x A2 x ... x An
+
+### Свойства на релации от вида R ⊆ A^2
+
+- *Рефлексивност* ∀a ∈ A : aRa
+ - *Антирефлексивност* ∀a ∈ A : ¬aRa
+- *Симетричност* ∀a, b ∈ A, a =/= b : aRb → bRa
+ - *Антисиметричност* ∀a, b ∈ A, a =/= b : aRb → ¬bRa
+ - *Силна антисиметричност* ∀a, b ∈ A, a =/= b : aRb ⊕ bRa
+- *Транзитивност* ∀a, b, c ∈ A : aRb ∧ bRc → aRc
+
+- *Затваяне на релация*
+ R' - рефлексивно затваряне
+ 1) R' ⊆ A^2
+ 2) R ⊆ R'
+ 3) R' е рефлексивна
+ Аналогично за симетрично и транзитивно затваряне
+
+- *Релация на еквивалентност* рефлексивна, симетрична, транзитивна
+- *Класове на еквивалентност* (Само за релации на еквивалентност)
+ [a] = { b ∈ A | aRb }
+
+- *Релация на частична (нестрога) наредба* рефлексивна, антисиметрична, транзитивна
+ - *Минимален елемент* а е минимален, ако ¬∃b ∈ A, a =/= b : bRa
+ - *Максимален елемент* a е максимален, ако ¬∃b ∈ A, a =/= b : aRb
+- *Релация на частична строга наредба* антирефлексивна, антисиметрична, транзитивна
+
+- *Релация на линейна (нестрога) наредба* рефлексивна, силно антисиметрична, транзитивна
+ - *Линейно разширение* Частична наредба R ⊆ A^2, линейна наредба R' ⊆ A^2, R ⊆ R' => R' е линейно разширение на R
+- *Релация на линейна строга наредба* антирефлексивна, силно антисиметрична, транзитивна
+
+- *Верига* всяка редица ai0, ai1, ..., aik където i0,...,ik ∈ {1,...,n}, aij R aij+1 и aij =/= aij+1 за 0 <= j < k
+ Редица от елементи, където всеки два съседни елемента са в релация
+ - веригите не минават през примки
+- *Контур* ако за верига, ai0 = aik и k > 0
+ Редица от елементи, където всеки два съседни елемента са в релация и първия и последния също са в релация
+
+# Лекция 4: Функции
+
+- *Тотална функция* Всяка релация f ⊆ X x Y, за всяко x, има точно едно y, (x, y) ∈ f
+- *Частична функция* Всяка релация f ⊆ X x Y, за всяко x, има поне едно y, (x, y) ∈ f
+
+- *Инекция* Всеки елемент води до единствен друг елемент (може не всички елемeнти от другите да са "покрити")
+- *Сюрекция* Всеки елемент от другите е "покрит" от един или повече елементи
+- *Биекция* Едно към едни между елементите
+
+- *Крайно множество*
+ Ако А е празното, то имаме кардиналност 0
+ Иначе, трябва да съществува n, за което имаме биекция f : A → {1, 2, ..., n}
+- *Безкрайно множество* ако не е крайно
+
+- *Изброимо безкрайно множество* Равномощно на ℕ
+
+### Принцип на Дирихле
+
+За крайни X и Y, |X| > |Y|, то няма инекция f: X → Y
+
+Ако има m обекта в n чекмеджета и m > n, то в поне едно чекмедже има повече от един обект
+
+# Лекция 5: Изброителна комбинаторика
+
+- *Първи принцип*: Принцип на Дирихле
+- *Втори принцип*: Принцип на разбиването
+ За множество X и негово разбиване {Y1, ..., Yk}, |X| = |Y1| + ... + |Yk|
+ - Принцип на изваждането
+ За множество A и универсум A, |A| = |U| - |A̅|
+- *Трети принцип*: Принцип на умножението
+ |A x B| = |A| * |B|
+- *Четвърти принцип*: Пинцип на биекцията
+ |A| = |B| тстк съществува биекция f: A → B
+- *Пети принцип*: Принцип на делението
+ k на брой класове на еквивалентност [a], |[a]| = m
+ m = |A|/k
+- *Шести принцип*: Принцип на включването и изключването
+ При разбиването, кардиналността е сума от кардиналностите на дяловете на разбиване
+ Тук, кардиналноста е сума от дяловете на покритие и изваждане на техните сечения.
+ |A1 U ... U An| = Σ{1 <= i <= n} |Ai| - Σ{1 <= i < j <= n} |Ai ∩ Aj| + ... + (-1)^(n-1) * |A1 ∩ ... ∩ An|
+
+# Лекция 6: Комбинаторни конфигурации
+
+Дадено е опорно множество А = {a1, a2, ..., an} чрез което изграждаме комбинаторни конфигурации.
+n е брой елементи в A. m е брой елементи в конфигурация.
+
+- *Множество от конфигурациите с наредба, с повтаряне*
+ К\_{Н,П}(n, m) = A^m
+ |К\_{Н,П}(n, m)| = |A^m| = n^m
+
+ А = {a, b, c}, m = 2
+ К\_{Н,П}(3, 2) = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}
+
+- *Множество от конфигурациите с наредба, без повтаряне*
+ К\_{Н}(n, m)
+ |К\_{Н}(n, m)| = n * (n - 1) * (n - 2) * ... * (n - m + 1) = n на падаща степен m
+
+ А = {a, b, c}, m = 2
+ К\_{Н}(3, 2) = {(a, b), (a, c), (b, a), (b, c), (c, a), (c, b)}
+ - частен случай: n = m. Тогава това са *пермутации без повторения* и |К\_{Н}(n, m)| = n!
+ - *пермутации с повторения*
+
+- *Множество от конфигурациите без наредба, без повтаряне*
+ K(n, m); Комбинации/Подмножество
+ |K(n, m)| = |K\_{Н}(n, m)|/m! = n!/((n-m)!m!) = (n на падаща степен m)/m! = биномен коефициент (n m)
+
+
+- *Нютонов бином* (x + y)^n = Σ\_{k=0}^n (n k) * x^k * y^(n-k)
+
+# Лекция 7: Рекурентни уравнения
+
+Уравнение, при което дясната му страна включва и самото уравнение и имаме начално условие(ия)
+
+Tn = { nT\_(n-1) ако n >= 1
+ { 1, ако n = 0
+Не е с константни коефициенти
+
+Sn = { S\_(n-1) + S\_(n-2) + ... + S1 + S0 ако n >= 1
+ { 1 ако n = 0
+Не е с крайна история
+
+### Алгоритъм за решаване на рекурентни уравнения от определен вид
+
+1. *Характеристично уравнение* Заместваме an с x^n, a\_(n-1) с x^(n-1) и так. нат. Делим на x^(n-k).
+ x^k - c1 * x^(k-1) - c2 * x^(k-2) - ... - c\_(k-1) * x - c\_k = 0
+
+2. *Общо решение* Нека {α1, α2, ..., αk}\_M е мултимножество от корените
+ a\_n = A1 * α1^n + A2 * α2^n + ... + Ak * αk^n където A1,...,Ak са неизвестни константи
+ Ако има еднакви α корени, то ние умножаваме и с n^k в нарастващ ред на ка, тоест ако примерно α1 = α2 = a3 != α4 != α5
+ а\_n = A1 * α1^n + A2 * α2^n * n^1 + A3 * α3^n * n^2 + A4 * α4^n + A5 * α5^n
+
+3. *Точно решение* Ако началните условия не са дадени, общто решение е отговора.
+ Ако са дадени, те ще са k на брой и ще намерим A1,...,Ak като заместим n със стойностите на аргумента в началните условия.
+ Ще получим система от k линейни уравнения с k неизвестни. След като я решим, със заместваме ще стигнем до точното решение.
+
+Пример: аn = 12a\_(n-1) - 51a\_(n-2) + 92a\_(n-3) - 60a\_(n-4) с начални условия a1 = 1, a2 = 2, a3 = 4, a4 = 6
+
+1. Характеристично уравнение - x^4 - 12x^3 + 51x^2 - 92x + 60 = 0 ↔ (x - 2)^2 * (x - 3) * (x - 5) = 0
+
+2. Мултимножеството от корените му е {2, 2, 3, 5}\_M
+ Общото решение е а\_n = A * 2^n + B * n * 2^n + C * 3^n + D * 5^n
+
+3. а1 = A * 2^1 + B * 1 * 2^1 + C * 3 ^ 1 + D * 5^1
+ a2 = A * 2^2 + B * 2 * 2^2 + C * 3 ^ 2 + D * 5^2
+ a3 = A * 2^3 + B * 3 * 2^3 + C * 3 ^ 3 + D * 3^3
+ a4 = A * 2^4 + B * 4 * 2^4 + C * 3 ^ 4 + D * 5^4
+
+ 1 = 2A + 2B + 3C + 5D
+ 2 = 4A + 8B + 9C + 25D
+ 4 = 8A + 24B + 27C + 125D
+ 6 = 16A + 64B + 81C + 625D
+
+ Излиза, че A = 2/9 B = -1/6 C = 1/3 D = -1/45
+
+ an = 2^(n+1)/9 - n * 2^n/6 + 3^(n-1) - 5^n/45
+
+### Решаване на рекурентни нехомогенни уравнения от определен вид
+
+an = c1 * a\_(n-1) + ... + ck * a\_(n-k) + p1(n) * b1^n + ... + pl(n) * bl^n
+ \_________________________________/ \_______________________________/
+ хомогенна част нехомогенна част
+
+Изъплняваме стъпки 1 от решаването на рекуренти уравнения от определен вид само с хомогенната част и игнорираме нехомогенната.
+Намираме мултимножеството, обединяваме го с мултимножеството на нехомогенната част.
+Изпълняваме стъпка 2 и 3 от решаването на рекуренти уравнения от определен вид, като използваме полученото мултимножество.
+ Понеже имаме само k начални условия, а обединението изисква k+l, ще направим още l начални условия.
+
+Уравнения като T(n) = 2T(n-1) + ⌈√n⌉ или S(n) = S(n - 1) + 1/n не могат да се решат с този алгоритъм.