Дискретная математика для программистов.

Глава 1. Введение

Дискретный - составленный из отдельных частей.

Современный цифровой компьютер - конечная дискретная система, состоящая из устройств ввода и вывода, вычислительного аппарата и памяти.

Алгоритм - последовательность команд, приводящих к решению задачи за конечное время.

Математическое моделирование - привлечение математики для решения практических задач.

Псевдокод - неформальный язык выражения алгоритмов. (В данной записи будет использоваться конструкции языка Си: операторы, циклы, условия и другие базовые концепции программирования).

Глава 2. Логика и доказательство

Простые высказывания P - "Звёзды холодные" и Q - "Солнце - это звезда". Составные высказывания P → Q - "Если звёзды холодные, то солнце - это звезда" или Q -> P - "Если солнце - это звезда, то звёзды холодные".

Логика высказываний определяет следующие логические операции:

• отрицание - не;
• конъюнкция - и;
• дизъюнкция - или;
• импликация - если..., то...;
• эквиваленция - ...то же, что и....

Таблица истинности

Таблица всех возможных значений составного выражения в зависимости от истинностного значения простых высказываний.

Рассмотрим таблицу истинности импликации и попытаемся обосновать его значения. Высказывание с импликацией вида A → B имеет посылку - A и следствие или заключение - B. Стоит прояснить, что импликация как и другие логические операции имеет свои приближения в естественном языке, например "если A, то B" или "B влечёт A".

оказывает эффект на истинностное значение составного высказывания. Формальная запись импликации имеет вид стрелки: ⇒ или →. В естественном языке импликация играет важную роль в рассуждениях и умозаключениях, иначе условных высказываниях, так как она предполагает причинную связь между посылкой и заключением, и её истинность зависит от истинности этих высказываний. Так, в русском языке распространены следующие выражения импликации: .

Частный и более понятный на интуитивном уровне случай импликации - логическое следование, где из истинной посылки следует истинное заключение, например "Если идёт дождь, то снаружи облачно". Таким образом логическое следование это высказывание о двух заведомо истинных и связанных причинностью явлениях. Но если логическое следование оперирует только истинными высказываниями, то импликация принимает как истинные, так и ложные высказывания. Рассмотрим пример с импликацией, истинностное значение которого сведём к сдерживанию обещания, В естественном языке мы можем трезво оценить только два случая: то есть высказывание соврал я или нет - "Если я буду здоров, то я посещу занятия":

1. Он был здоров и я посетил занятия. Он сказал правду.
2. Он был здоров, но я не посетил занятия. Я соврал. Но как же быть если я всё-таки заболел? С житейской точки зрения случаи, когда:
3. Он был нездоров и не посетил занятия.
4. Он был нездоров и посетил занятия. трудно поддаются оцениванию.

Предикаты(условие) и кванторы.

Способы доказательства

1. Прямой способ доказательства: предположить, что P истинно и из него вывести истинность Q, тем самым доказав истинность P -> Q
2. Обратный способ доказательства: предположить что Q ложно, то есть неQ истинно и вывести ложность P, то есть истинность не P, тем самым доказав истинность не Q => не P
3. Метод от противного: предположить, что P - истинно, а Q - ложно и прийти от P к другому Q, получив противоречие и доказав истинность Q и истинность P => Q.

Математическая индукция

1. Показать истинность P(1)
2. Показать истинность P(n) Например, доказать формулу суммы натуральных чисел: сначала показать истинность формулы в тривиальном случае, а затем предположить истинность для произвольного значения и применить прямой способ доказательства, например допустим P(k) - истинно, тогда из него можно вывести, то есть будет следовать и истинность P(k + 1). В таком случае мы придём к цепочке импликаций P(1) => P(2) => ... => P(n).

Корректность алгоритмов

P - входное условие или предусловие, а Q - выходное условие или постусловие. A - алгоритм. {P}A{Q} - есть предикат, если P истинно, то Q истинно. Доказать предикат {P}A{Q} <=> доказать истинность {P} и {Q}, где P и Q истинные предикаты. Цепочка утверждений {P}A1{Q1}, {Q1}A2{Q2}, {Q2}A3{Q3}, ... Напрмер: A - квадратный многочлен. P -> {x = x1} A1 -> {y = ax1} Q -> {y = ax1 и x = x1}

Дописать примеры со второй главы

Чтобы проверить корректность алгоритма, нужно проверить все изменения до, в течение и после работы алгоритма. Это можно сделать с помощью записи цепочки утверждений алгоритма с пред- и постусловиями. Но корректность алгоритмов с циклами легче доказывать с помощью математической индукции. Пример с матиндукцией переписать.

Ещё желательно показать, что цикл закончится.

Глава 3. Теория множеств

Операции над множествами

• Дополнение ￣
• Объединение ⋃
• Пересечение ⋂
• Разность /
• Симметрическая разность △

Алгебра множеств. Свойства множеств. Нотация множеств A = {a: P(a)} и B = {b: P(b)}

Множество натуральных чисел - N Множество рациональных чисел - Q Множество вещественных чисел - R Универсальное множество U - множество всех множеств.

Диаграмма Вена. Подмножества. Равные множества. Переменные. Тип данных. Аналогия операций над множествами и логических операций. Мощность множества - |A|. Закон двойственности.

Формула включений и исключений

|A ⋃ B| = |A| + |B| - |A ⋂ B|

Декартово или прямое произведение матриц

A × B = C, где C = {(a, b): P(a, b)}, где (a, b) - упорядоченная пара, то есть (a, b) ≠ (b, a). R × R = R² = {(x, y): x ∈ R, y ∈ R} - Декартова плоскость, где x и y координаты. |A × B| = |A| * |B| A1 × A2 × A3 × ... × An = {(a1, a2, a3, ..., an): ai ∈ Ai, i = 1, 2, 3, ..., n} A × A × A × ... × A = A^n |A^n| = |A|^n

Если B = {0, 1}, то B^n - последовательность нулей и единиц(битовая строка) длины n. Характеристический вектор подмножества - набор нулей и единиц длины n, где A ///to be continued...

Показательное множество, множество частей, степень множества, булеан

P(A) = {C: C ⊂ A}. |P(A)| = 2^|A|

Глава 4. Отношения

S - множество студентов К - множество курсов S × K - множество упорядоченных пар, где пара (s, k) отображает отношение "слушает", то есть слушает(s, k).

Бинарные отношения, отношения эквивалентности(обобщение отношения равенства), отношение частичного порядка, система управления базами данных.

Бинарное отношение между A и B, есть R ⊂ A x B и просто отношение R на A, если A = B, где R определяет отношение, а точнее его предикат. Например, в ориентированном графе элементы пары соединены ориентированными стрелками.

Матрица

Объект, представляющий отношение на множестве с m строками и n столбцами, если A = {a1, a2, ..., am} B = {b1, b2, ..., bn} M(i, j) = И, если (ai, bj) ∈ R M(i, j) = Л, если (ai, bj) ∉ R

R - бинарное отношение, то можно записать (x, y) ∈ R <=> xRy, либо перечислить R = {(a1, b1), (a1, b2), ..., (a2, b1), (a2, b2), ..., (am, bn)}

Свойства отношений

R на A(R ⊂ A^2):

1. рефлексивно, если xRx, для ∀x ∈ A
2. симметрично, если xRy => yRx
3. кососимметрично(в данной книге, но в википедии антисимметрично)
4. транзитивно, если xRy ^ yRz => xRz, где x, y, z ∈ A

Запись xRy похожа на {P}A{Q}, где R можно рассматривать как отношение "влечёт по условию", то есть xRy - "x влечёт y по условию R".

Множество R* - продолжение(замыкание) отношения R

чтобы удовлетворить свойство R ⊂ A x A, R ⊂ A x A, R ⊂ R. R* - замыкание отношения R относительно свойства P. Например A = {1, 2, 3}, и R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)}

• Рефлексивное замыкание отношения R: R* = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3); (2, 2), (3, 3)}
• Замыкание отношения R относительно симметричности: R* = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3); (2, 1), (3, 2)}
• Транзитивное замыкание(|R | = |A x A|): R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3); (3, 2), (2, 1), (2, 2)}

Замыкание по транзитивности можно применить для определения достижимости от одной точки до другой, например: aRb ^ bRc => aRc cRd ^ dRe => cRe aRc ^ cRe => aRe

Важно понимать, что 1, 2, 3, 4 - это свойства отношений, то есть их характеристика, а не описание. И если отношение удовлетворяет какому-то условию, то у неё имеется определённое свойство. И отношение одновременно может иметь несколько свойств, например отношение R на N, где R = {(x, y): x - делитель y} - является не симметричным, рефлексивным, транзитивным и кососимметричным.

Специальные типы бинарных отношений

• Отношение эквивалентности(обобщение равенства) обладает свойствами - рефлексивности, транзитивности и симметричности.

Кососимметричность исключает симметричность и включает рефлексивность, но не запрещает транзитивность.

Бинарное отношение

Множество упорядоченных пар удовлетворяющих определённому условию. Если на множестве задано отношение эквивалентности, то его можно разделить на непересекающиеся подмножества, где каждый элемент подмножества будет эквивалентен другому любому элементу в этом же подмножестве. По сути R - это свойство пар или элементов.(Наверное нет)

Вот есть множество A и B, есть отношение R на A x B, где R - это свойство, например двигающие предметы, то есть приводящие в движение, это отношение не эквивалентно, так как в паре (человек, ручка) нет симметричности и транзитивности, но есть рефлексивность(частичная) есть только кососимметричность. A - мнржество людей B - множество ручек С - множество пресноводных Отношение R на A x C - симметрично, транзитивно и рефлексивно, то есть оно эквивалентно, что означает что все элементы множества A x C относятся друг к другу одинаково. С горем поплам, но понял.(В этом моменте меня прорвало, но есть ошибки в рассуждениях)

Разбиение

Подобно классификации, например книги бывают историческими, художественными, научно-фантастическими и т.д.

Разбиение множества A

1. A = A1 U A2 U ... U An
2. Ai ⋂ Aj = ∅, где i != j

Ai - блок разбиения и подмножество A

Класс эквивалентности

Ex = {z e A: zRx} - это множество таких элементов z из множества A, которые относятся к x по условию R(или P в R). Проще говоря, это все идентичные иксу элементы z. Ex ( A

Глава 5. Функции

Функция - специальный тип бинарных отношений.

R - отношение на A x B R^-1 - обратное отношение на B x A R^-1 = {(b, a): (a, b) e R} Пример: обратным отношению "x - родитель y" - "y - ребёнок x".

R - отношение на A x B S - B x C

f: A -> B - функция f определена или задана на множестве A со значениями в множестве B.

Виды функций

Функция f обратима, если она биективна. f: A -> B

Принцип Дирихле

f: A -> B - функция

Если |A| > |B|, то хотя бы одно значение f встретится более одного раза, то есть ai != aj, f(ai) = f(aj). Рассадить 10 зайцев по 9 клеткам. Обобщение: |A| > k|B|, то f встретится минимум k + 1 раз.

(S comp R) = R^-1 comp S^-1

Частично вычислимые функции

Глава 6. Комбинаторика

Комбинаторика - подсчёт элементов конечных множеств.

Правило суммы

Если A и B - несвязанные события и для A есть n1 исходов, а для B существует n2 исходов, то всего возможно n₁ + n "A или B" исходов. То есть правило суммы следует из формулы включений и исключений. A и B - множество исходов. |A| = n1 и |B| = n2, тогда |A ⋃ B| = |A| + |B|, так как A ⋂ B по условию, значит |A ⋂ B| = 0.

Правило произведения

Если последовательность событий k, а исходов n1, n2, ..., nk, то всего n1 n2 ... nk исходов. Если элемент из A можно выбрать m способами и при любом выборе из A элемент из B можно выбрать n способами, то пару (a, b) можно выбрать m n способами. Обобщение правила "и": A1 × A2 × A3 × ... × An = |A1| |A2| |A3| ... |An| то есть набор из n упорядоченных и повторяющихся элементов.

Выборка (n, k) - выборка объёма k из n элементов: упорядоченная и неупорядоченная выборка. Элементы x1, x2, ..., xk из множества X.

• (n, k) - размещение с повторениями - упорядоченная выборка (n, k), элементы которой могут повторяться: n^k
• (n, k) - размещение без повторений - упорядоченная выборка (n, k) элементы которой не повторяются: P(n, k) или An^k = n! / (n-k)!
• неупорядоченная (n, k)- выборка с повторениями - (n, k) - сочетание с повторениями: (n + k - 1)! / ((n - 1)! * k!)
• неупорядоченная (n, k)- выборка без повторений - (n, k) - сочетание без повторений: C(n, k) или Cn^k или (^n _k) = P(n, k) / k! = n! / ((n - k)! * k!)
• Перестановки (k, k): k! / (k1! k2! ... * kn!) - мультиномиальный коэффициент. \Написать вывод формул

Бином Ньютона

Если 0! = 1, то C(n , k) - коэффициенты бинома (a + b)^n = Sum(k = 0, n)a^(n-k) b^k C(n, k), где C(n, k) - биномиальный коэффициент. Например: (a + b)^3///

Треугольник Паскаля

C(0, 0) C(1, 0) C(1, 1) C(2, 0) C(2, 1) C(2, 2) ... 1 1 1 1 2 1 ...

C(n, k) = C(n, n - k)

Формула Паскаля: C(n, k) = C(n - 1, k - 1) + C(n - 1, k)

Глава 7. Графы

Задача про кённингбергские мосты и её представление в виде графа. Граф состоит из вершин(точки) и рёбер(линии). Простой граф - G = (V, E), где V - множество вершин, а E - множество рёбер. Простой граф не содержит петель и кратных рёбер.

Смежные вершины соединяются ребром, инцидентным к этим двум вершинам. e = uv = vu

Матрица смежности.

На языке теории множеств E это отношение на V x V.

Подграф - G' = (V', E'), где V' e V и E' ( E.

Маршрут - последовательность вершин соединённых рёбрами: v0, v1, ..., vk для

Глава 8. Ориентированные графы

Орграф G = (V, E), где V - конечное множество вершин, а E - отношение на V. Ориентированные рёбра - дуги. Совокупность всех дуг образует множество E. Дуга, соединяющая вершины - "uv", где "u" антецедент "v". Путь длины k - последовательность вершин где каждая пара v_i-1vi lkz i = 1, ...,k (v0, v1, ..., vk) образует дугу. Контур - путь без повторяющихся вершин где v0 = vk. Граф G бесконтурный если в нём нет контура. Бесконтурный граф что-то типа дерева или зависимость PERT. Контур своего рода ориентированный Гамильтонов цикл.

Алгоритм топологической сортировки Кана создаёт последовательность согласованных меток для бесконтурного орграфа.

M^2 - матрица смежности с длиной дуги 2. M^3 - с длиной дуги 3 где M^3 = M M M

Матрица достижимости есть замыкание по транзитивности E отношения E в G = (V, E) Матрица достижимости: M = M или M^2 или ... или M^n Матрица достижимости: более удобный алгоритм Уоршелла генерирует последовательность матриц W0 = M, W1, ..., Wn где элемент aij из Wk(k >= 1) равен "И" когда существует путь vivj произвольной длины. Wn = M*

Алгоритм Дейкстры на нагруженном графе для нахождения кратчайшего пути. Расстояние от "u" до "v" - общий вес пути.

Весовая матрица w(u, v) = {0, если "u" = "v"; inf, если "u" и "v" не соединены дугой(не инцидентны); d, если дуга "uv" имеет вес d.

Полустепень исхода - число дуг delta+(v) орграфа исходящих из v. Полустепень захода - число дуг delta-(v) орграфа заходящих в v.

Связный граф - любая пара u и v достижима.

Сильно связый граф - любая пара ю и ви имеет путь.

Если в матрице смежности простого графа все столбцы имеют хотя бы один "И", то граф связный. (простой - нерефлексивный и кососимметричный) Если все множества антецедентов непусты, то в этом орграфе есть контуры.

Глава 9. Булева алгебра

B = {0, 1} - точка. Булевые переменные p и q. Высказывания P и Q. Логика высказываний и предикатов <- Булева алгебра -> Алгебра множеств. То есть булева алгебра есть обобщение его соседей.

Булевы выражения и законы булевой алгебры: переписать законы

Эквивалентные булевы выражения.

Булева функция f: B^n -> B, n - булевых переменных в f(p1, p2, ..., pn).

Минтерм(элеметарная конъюнкция)(функция) - принимает значение 1 только на одном наборе значений аргументов.

Элементараная конъюнкция - p1 ^ p2 ^ ... ^ pn

Дизъюнктивная нормальная форма - дизъюнкция минтермов f = f1 + f2 + ... + fn, где fi - минтерм.

Полная система функций или операций - множество функций через которые можно выразить любую булеву функцию, например {f1, f2, f3}, где ...

Карта Карно, а также метод Куина-Мак-Класки

Функциональные схемы и их элементы (https://logijs.com/)

Функциональная система - это абстрактная физическая реализация булевой функции.

Приложения

Подтянуть и другие небольшие по объёму источники. Алгоритмы на графах. Реализация алгебры множеств. Исчисление и оценка конечных сумм. Элементы теории рекурсии. Производящие фуекции. NP полные задачи. Введение в динамическое программирование.

\\TO DO добавить картинки добавить наглядные примеры или анимации добавить вёрстку в LaTeX уточнить стиль изложения