diff options
Added discrete math notes
1 files changed, 251 insertions, 0 deletions
| -rw-r--r-- | Year 1/Discrete math/notes.md | 251 |
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 не могат да се решат с този алгоритъм. |
