Теория множеств, логика и теория графов: полный конспект с определениями, законами и алгоритмами

Теория множеств

1. Конечное и бесконечное множество

Конечное множество — это множество, число элементов которого можно выразить конкретным натуральным числом (например, {a, b, c}). Бесконечное множество — это множество, которое не является конечным, то есть его элементы нельзя перенумеровать до конца (например, множество всех натуральных чисел N).

2. Отображения на множествах

Отображение f: A → B — это правило, которое каждому элементу множества A (область определения) ставит в соответствие ровно один элемент множества B (область значений). Важные типы:

• инъекция — каждый образ уникален;
• сюръекция — каждый элемент B является образом;
• биекция — одновременно инъекция и сюръекция, то есть взаимно однозначное соответствие.

3. Бинарные отношения

Бинарное отношение между множествами A и B — это любое подмножество их декартова произведения A×B. Его можно задать перечислением пар, матрицей или ориентированным графом.

Основные свойства отношения на одном множестве:

• рефлексивность — каждый элемент связан с самим собой;
• симметричность — если a связано с b, то и b связано с a;
• антисимметричность — если a связано с b и b связано с a, то a = b;
• транзитивность — если a связано с b, а b связано с c, то a связано с c.

4. Основные понятия теории множеств

Множество — это неупорядоченная совокупность различных объектов, называемых элементами. Пустое множество (∅) не содержит элементов. Множества задаются либо прямым перечислением элементов в фигурных скобках, либо через характеристическое свойство, которому эти элементы удовлетворяют.

5. Операции и структуры множеств

Булеан P(A) — это множество всех возможных подмножеств множества A. Основные операции:

• объединение A∪B — элементы, принадлежащие A или B;
• пересечение A∩B — элементы, принадлежащие и A, и B;
• разность A\B — элементы из A, не принадлежащие B;
• симметрическая разность.

Система множеств — это множество, элементами которого являются другие множества.

6. Отношения на множествах

Бинарное отношение на множестве A — это подмножество R ⊆ A×A. Комбинации свойств определяют специальные типы отношений:

• эквивалентность — рефлексивность, симметричность, транзитивность;
• порядок — рефлексивность, антисимметричность, транзитивность.

7. Свойства бинарных отношений

Для отношения R на множестве A выделяют четыре ключевых свойства:

• рефлексивность: для всех a из A выполняется aRa;
• симметричность: из aRb следует bRa;
• антисимметричность: из aRb и bRa следует a = b;
• транзитивность: из aRb и bRc следует aRc.

8. Область определения и область значения соответствия

Для соответствия G между множествами X и Y:

• областью определения называется множество всех x из X, для которых существует y из Y такой, что (x, y) ∈ G;
• областью значения называется множество всех y из Y, для которых существует x из X такой, что (x, y) ∈ G.

Математическая логика и булева алгебра

9. Основные логические связки и их таблицы истинности

Логические связки — это операции над высказываниями, принимающими значения «истина» (1) или «ложь» (0):

• отрицание (НЕ, ¬) — меняет значение на противоположное;
• конъюнкция (И, ∧) — истинна только когда оба операнда истинны;
• дизъюнкция (ИЛИ, ∨) — ложна только когда оба операнда ложны;
• импликация (→) — ложна только когда посылка истинна, а следствие ложно;
• эквиваленция (↔) — истинна, когда оба операнда равны.

10. Эквивалентные преобразования и основные соотношения

Эквивалентными называются формулы, которые принимают одинаковые значения при всех наборах значений переменных. Основные законы булевой алгебры:

• коммутативности (перестановка операндов);
• ассоциативности (расстановка скобок);
• дистрибутивности, например: A∧(B∨C) = (A∧B)∨(A∧C);
• законы де Моргана: ¬(A∧B) = ¬A∨¬B, ¬(A∨B) = ¬A∧¬B;
• закон двойного отрицания: ¬¬A = A;
• законы идемпотентности: A∨A = A, A∧A = A;
• законы с константами: A∨1 = 1, A∧0 = 0.

11. Понятие формул логики и таблицы истинности

Формула логики высказываний строится из переменных, логических связок и скобок по индуктивному определению:

• каждая переменная — формула;
• если A и B — формулы, то (¬A), (A∧B), (A∨B), (A→B), (A↔B) — тоже формулы.

Таблица истинности перечисляет все возможные наборы значений переменных и соответствующие им значения формулы.

12. Равносильные преобразования и упрощение формул

Равносильные преобразования — замена части формулы на эквивалентную ей на основе основных законов (п. 10). Цель упрощения — получить формулу того же смысла, но с меньшим числом операций или переменных. Например, законы поглощения: A ∨ (A∧B) = A и A ∧ (A∨B) = A.

13. Дизъюнктивная и конъюнктивная нормальные формы

• ДНФ — дизъюнкция одного или нескольких конъюнктов, где конъюнкт — конъюнкция переменных или их отрицаний;
• КНФ — конъюнкция одного или нескольких дизъюнктов, где дизъюнкт — дизъюнкция переменных или их отрицаний.

Совершенные формы (СДНФ/СКНФ) строятся по таблице истинности и содержат все переменные в каждом слагаемом или множителе.

14. Алгебра логики. Дизъюнктивная нормальная форма

Алгебра логики (булева алгебра) — раздел математической логики, изучающий высказывания и логические операции над ними. Например, для функции трёх переменных ДНФ может иметь вид:

(¬x∧y∧z) ∨ (x∧¬y∧z) ∨ (x∧y∧¬z)

Совершенная ДНФ (СДНФ) строится по таблице истинности и включает все переменные в каждой конъюнкции.

15. Логическая равносильность. Законы логики

Логическая равносильность — отношение между формулами, означающее, что они принимают одинаковые значения при всех наборах переменных. Основные законы:

• коммутативные: A∧B ≡ B∧A, A∨B ≡ B∨A;
• ассоциативные: (A∧B)∧C ≡ A∧(B∧C);
• дистрибутивные: A∧(B∨C) ≡ (A∧B)∨(A∧C);
• законы де Моргана: ¬(A∧B) ≡ ¬A∨¬B, ¬(A∨B) ≡ ¬A∧¬B;
• закон противоречия: A∧¬A ≡ 0;
• закон исключённого третьего: A∨¬A ≡ 1.

17. Дедуктивные и индуктивные рассуждения

• Дедуктивные рассуждения — логический вывод частных следствий из общих положений (от общего к частному). Достоверность вывода гарантирована истинностью посылок и правильностью логической формы.
• Индуктивные рассуждения — обобщение от частных случаев к общему выводу (от частного к общему). Индуктивный вывод носит вероятностный характер и не гарантирует истинности заключения, даже при истинных посылках.

18. Функции алгебры логики

Функции алгебры логики (булевы функции) — функции, аргументы и значения которых принадлежат множеству {0, 1}. Переход от табличного задания к булевой формуле методом СДНФ:

1. в таблице истинности выделяются строки, где функция равна 1;
2. для каждой такой строки записывается конъюнкция всех переменных;
3. переменные, равные 0 в данной строке, берутся с отрицанием;
4. все полученные конъюнкции объединяются дизъюнкцией.

19. Простые и сложные высказывания

Простые (атомарные) высказывания — элементарные утверждения без логических связок, которые можно оценить как истинные или ложные. Сложные высказывания образуются из простых с помощью логических операций: отрицания, конъюнкции, дизъюнкции, импликации («ЕСЛИ-ТО») и эквиваленции («ТОГДА И ТОЛЬКО ТОГДА»).

20. Совершенные дизъюнктивная и конъюнктивная нормальные формы

• СДНФ — дизъюнкция конституент единицы, где каждая конституента — конъюнкция всех переменных, взятых с отрицанием или без него. Строится по строкам таблицы истинности, где функция равна 1.
• СКНФ — конъюнкция конституент нуля, где каждая конституента — дизъюнкция всех переменных. Строится по строкам, где функция равна 0.

Обе формы канонические: однозначно определяются по таблице истинности.

21. Определение и примеры предикатов

Предикат — высказывание, зависящее от одной или нескольких переменных, которое становится высказыванием при подстановке конкретных значений. Примеры: «x — простое число» (одноместный), «x > y» (двухместный), «x + y = z» (трёхместный). Область определения предиката — множество значений, которые могут принимать переменные.

22. Логические операции над предикатами. Выполнимость и истинность

Над предикатами выполняются логические операции: отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция.

• Выполнимый предикат — существует набор значений переменных, при котором он истинен;
• тождественно истинный предикат — истинен при всех наборах значений переменных из области определения.

Кванторы: всеобщности (∀ — «для всех») и существования (∃ — «существует») позволяют связывать переменные и формулировать утверждения над множествами.

Теория графов

26. Графы: основные определения и представления

Граф — пара G = (V, E), где V — множество вершин, E — множество рёбер. Основные способы представления:

• список смежности — для каждой вершины хранится список смежных с ней вершин;
• матрица смежности — квадратная матрица, где a[i][j] = 1, если есть ребро из i в j;
• матрица инцидентности — матрица «вершины — рёбра», элемент которой указывает связь вершины с ребром.

25. Простой граф, мультиграф и орграф

• Простой граф — граф без петель и кратных рёбер;
• мультиграф — граф, допускающий кратные рёбра и петли;
• орграф (ориентированный граф) — граф, все рёбра которого имеют направление (дуги).

32. Основные понятия теории графов

Степень вершины — количество инцидентных ей рёбер. Петля — ребро, соединяющее вершину саму с собой. Кратные рёбра — несколько рёбер между одной парой вершин. Путь — последовательность вершин, соединённых рёбрами. Цикл — замкнутый путь. Граф может быть взвешенным (рёбрам присвоены веса).

23. Пути и циклы в графах

Путь — последовательность вершин, где каждая следующая соединена ребром с предыдущей; в орграфе дуги направлены вдоль пути. Цикл — путь, у которого начало и конец совпадают. Простой путь/цикл не повторяет вершин (кроме начала и конца в цикле).

24. Минимальные и максимальные пути

Минимальный путь — путь с наименьшим количеством рёбер (или наименьшей суммой весов). Максимальный путь — с наибольшим количеством рёбер или суммой весов. Поиск кратчайшего пути имеет эффективные алгоритмы (Дейкстра, Флойд), поиск самого длинного пути в общем случае NP-трудная задача.

27. Поиск кратчайших путей между вершинами

• для невзвешенных графов — поиск в ширину (BFS);
• для взвешенных графов без отрицательных весов — алгоритм Дейкстры;
• для графов с отрицательными весами (без отрицательных циклов) — алгоритм Беллмана–Форда.

16. Алгоритм поиска кратчайшего пути (Дейкстра)

Алгоритм Дейкстры работает во взвешенном графе без отрицательных весов:

1. каждой вершине присваивается метка — текущее известное кратчайшее расстояние от начальной вершины;
2. на каждом шаге выбирается непосещённая вершина с наименьшей меткой;
3. для всех её соседей пересчитываются метки;
4. процесс повторяется, пока все вершины не будут посещены.

Алгоритм гарантированно находит кратчайшие пути от начальной вершины до всех остальных.

28. Матричное представление неориентированных графов

Матрица смежности неориентированного графа — симметричная квадратная матрица n×n, где a[i][j] = 1, если между вершинами i и j есть ребро, и 0 в противном случае. Для взвешенных графов вместо 1 записывается вес ребра.

29. Матричное представление ориентированных графов

Матрица смежности орграфа — квадратная матрица n×n, где a[i][j] = 1, если существует дуга из i в j. Матрица не обязательно симметрична. Сумма элементов строки i даёт полустепень исхода вершины, сумма элементов столбца j — полустепень захода.

30. Поиск в ширину

Поиск в ширину (BFS) посещает вершины, достижимые из начальной, в порядке возрастания расстояния от неё. Использует очередь. Находит кратчайшие пути в невзвешенном графе, применяется для проверки связности, поиска компонент связности и проверки двудольности.

33. Поиск в глубину

Поиск в глубину (DFS) идёт «вглубь» до тех пор, пока возможно, и лишь затем возвращается назад. Использует стек (явно или через рекурсию). Применяется для топологической сортировки, поиска компонент связности и проверки на ацикличность.

38. Поиск на графах

Основные стратегии: BFS — обход «слой за слоем», кратчайшие пути в невзвешенном графе; DFS — рекурсивное исследование с уходом как можно дальше. Применяются для связности, поиска циклов, проверки двудольности, топологической сортировки, нахождения компонент сильной связности, мостов и точек сочленения.

31. Геометрическое изображение и изоморфизм графов

Граф изображается геометрически: вершины — точками, рёбра — линиями. Один граф может иметь разные геометрические представления. Два графа изоморфны, если существует взаимно однозначное соответствие между их вершинами, сохраняющее смежность. Проверка изоморфизма — NP-сложная задача без эффективного общего решения.

34. Связность и сильная связность графов

• Неориентированный граф связен, если между любыми двумя вершинами существует путь. Компонента связности — максимальный связный подграф.
• Орграф сильно связен, если для любых вершин u и v существуют пути из u в v и из v в u. Компонента сильной связности — максимальный сильно связный подграф.
• Орграф слабо связен, если соответствующий неориентированный граф связен.

35. Алгоритм Краскала

Алгоритм Краскала находит минимальное остовное дерево во взвешенном неориентированном графе: рёбра сортируются по весу, затем последовательно добавляются к остову, если не создают цикла. Для проверки цикла используется система непересекающихся множеств (DSU). Сложность — O(E log E).

36. Деревья и их свойства

Дерево — связный ациклический граф. Свойства:

• между любыми двумя вершинами существует ровно один простой путь;
• число рёбер на 1 меньше числа вершин: |E| = |V| − 1;
• добавление любого ребра создаёт ровно один цикл;
• удаление любого ребра нарушает связность.

Корневое дерево — дерево с выделенной вершиной-корнем. Остовное дерево — подграф, содержащий все вершины исходного графа и являющийся деревом.

37. Эйлеров путь и эйлеров цикл

Эйлеров путь проходит через каждое ребро графа ровно один раз, эйлеров цикл — замкнутый эйлеров путь. Алгоритм Флёри строит путь, на каждом шаге выбирая ребро, которое не является мостом (если есть альтернатива). Более эффективен подход на основе DFS.

39. Эйлеровы графы

Эйлеров граф — граф, содержащий эйлеров цикл. Теорема Эйлера:

• связный неориентированный граф имеет эйлеров цикл тогда и только тогда, когда все вершины имеют чётную степень;
• граф имеет эйлеров путь (но не цикл) тогда и только тогда, когда ровно две вершины имеют нечётную степень;
• для орграфа: эйлеров цикл существует, если граф сильно связен и полустепени захода и исхода всех вершин равны.