- Строить таблицы истинности, применять равносильности и строить отрицания высказываний с кванторами
- Проводить прямые доказательства, доказательства от противного и по индукции
- Выполнять операции над множествами и определять, является ли функция инъективной, сюръективной или биективной
- Рассуждать о графах с помощью степеней вершин и определять, существует ли эйлеров путь
Каждое «если … то …» в программе, каждое условие WHERE в запросе к базе данных и каждая микросхема в телефоне опираются на логику истины и лжи. В 1730-х годах Леонард Эйлер задался вопросом, можно ли обойти Кёнигсберг, пройдя по каждому из семи его мостов ровно один раз, и, доказывая, что это невозможно, заложил основы теории графов. Дискретная математика — логика, множества, функции и графы — это язык доказательств и информатики.
Высказывания, таблицы истинности и кванторы
Предложение, которое либо истинно (1), либо ложно (0), например «7 — простое число». Составные высказывания строят с помощью связок ¬ (отрицание), ∧ (конъюнкция, «и»), ∨ (дизъюнкция, «или»), → (импликация, «если … то») и ↔ (эквиваленция, «тогда и только тогда»).
| p | q | ¬p | p ∧ q | p ∨ q | p → q | p ↔ q |
|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 | 1 |
Импликация p → q ложна только тогда, когда p истинно, а q ложно. Обещание «если пойдёт дождь, я возьму зонт» нарушено лишь в дождливый день без зонта; в сухой день оно выполнено, что бы я ни делал. Поэтому импликация с ложной посылкой считается истинной.
- ≡равносильность: одинаковое значение в каждой строке таблицы
Законы де Моргана.
- ¬q → ¬pконтрапозиция, равносильна p → q
- q → pобратное утверждение — не равносильно
В высказываниях о многих объектах используют кванторы ∀ («для всех») и ∃ («существует»). Например, ∀x ∈ ℝ: x² ≥ 0 истинно, а ∃n ∈ ℕ: n² = 2 ложно. Чтобы построить отрицание, меняют ∀ на ∃ и наоборот, а то, что стоит после, отрицают:
- P(x)свойство x (предикат)
- ∀квантор всеобщности
- ∃квантор существования
Постройте отрицание: а) «Каждый студент группы сдал хотя бы один экзамен»; б) «Если число делится на 4, то оно чётное».
Показать решениеСкрыть решение
б) p → q, где p = «делится на 4», q = «чётное». Отрицание — p ∧ ¬q: «существует число, которое делится на 4, но не является чётным». Это ложно, значит, исходное утверждение истинно.
Методы доказательства
- Прямое доказательство: от условий через верные шаги приходим к заключению.
- Контрапозиция: вместо p → q доказывают ¬q → ¬p.
- Доказательство от противного: предполагаем, что утверждение ложно, и приходим к противоречию.
- Математическая индукция: доказываем P(1), затем P(n) ⇒ P(n + 1); тогда P(n) верно для всех натуральных n — как бесконечный ряд падающих костяшек домино.
Докажите: а) сумма двух нечётных чисел чётна; б) √2 — иррациональное число.
Показать решениеСкрыть решение
б) Предположим, что √2 = p/q — несократимая дробь. Тогда p² = 2q², p² чётно, значит, и p чётно (при нечётном p квадрат p² был бы нечётным): p = 2k.
Тогда 4k² = 2q², q² = 2k², то есть q тоже чётно.
И p, и q чётны — противоречие с несократимостью дроби. Значит, √2 иррационально ∎.
- P(1)база индукции
- P(n) → P(n + 1)шаг индукции; P(n) — предположение индукции
Докажите, что 1 + 3 + 5 + … + (2n − 1) = n² для любого натурального n.
Показать решениеСкрыть решение
Шаг: пусть 1 + 3 + … + (2n − 1) = n². Прибавим следующее нечётное число 2n + 1:
1 + 3 + … + (2n − 1) + (2n + 1) = n² + 2n + 1 = (n + 1)².
Это утверждение для n + 1, значит, по индукции равенство верно для всех n ∎. Например, 1 + 3 + 5 + 7 = 16 = 4².
Множества и диаграммы Эйлера — Венна
- A ∪ Bобъединение: элементы, принадлежащие A или B (или обоим)
- A ∩ Bпересечение: элементы, принадлежащие обоим
- A \ Bразность: в A, но не в B
- Aᶜдополнение: элементы универсального множества U, не входящие в A
Операции над множествами повторяют логику: ∪ соответствует ∨, ∩ — ∧, дополнение — ¬, поэтому снова верны законы де Моргана: (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ и (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ. A ⊆ B означает, что каждый элемент A лежит в B. У множества из n элементов 2ⁿ подмножеств, а декартово произведение A × B состоит из всех упорядоченных пар (a; b).
- |A|число элементов множества A
Формула включений и исключений: элементы, лежащие в обоих множествах, посчитаны дважды, поэтому их один раз вычитают. Для трёх множеств: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.
В группе из 40 студентов 25 изучают английский, 18 — русский, а 7 — оба языка. Сколько студентов изучают хотя бы один язык, сколько не изучают ни одного и сколько — только английский?
Показать решениеСкрыть решение
Ни одного: 40 − 36 = 4.
Только английский: 25 − 7 = 18; только русский: 18 − 7 = 11.
Проверка по областям диаграммы Эйлера — Венна: 18 + 7 + 11 + 4 = 40 ✓.
Отношения и функции
Отношение из A в B — любое подмножество R ⊆ A × B. Отношение на одном множестве может быть рефлексивным (a R a), симметричным (a R b ⇒ b R a) и транзитивным (a R b и b R c ⇒ a R c). Все три свойства вместе дают отношение эквивалентности, которое разбивает множество на классы: например, «даёт тот же остаток при делении на 3» разбивает ℤ на три класса.
Отношение f: A → B, при котором каждому элементу a ∈ A соответствует ровно один образ f(a) ∈ B. A — область определения, B — множество, в котором функция принимает значения.
| Тип | Смысл | Пример |
|---|---|---|
| Инъективная | Разные элементы имеют разные образы: f(a₁) = f(a₂) ⇒ a₁ = a₂ | f(x) = 2x, ℤ → ℤ (не сюръекция: нечётные числа не получаются) |
| Сюръективная | Каждое b ∈ B является образом некоторого a | f(x) = x³ − x, ℝ → ℝ (не инъекция: f(0) = f(1) = 0) |
| Биективная | И инъективна, и сюръективна; есть обратная функция f⁻¹ | f(x) = x³, ℝ → ℝ; f(x) = x², [0; ∞) → [0; ∞) |
| Ни то ни другое | Ни инъекция, ни сюръекция | f(x) = x², ℝ → ℝ: f(−2) = f(2), а отрицательные числа не являются значениями |
Графы
Множество вершин V вместе с множеством рёбер E, каждое из которых соединяет две вершины: G = (V, E). Степень deg(v) — число рёбер, выходящих из v. Путь — последовательность вершин, соединённых рёбрами, цикл — замкнутый путь; граф связен, если любые две вершины соединены путём.
- deg(v)степень вершины v
- |E|число рёбер
Лемма о рукопожатиях: у каждого ребра два конца. Следствие: число вершин нечётной степени всегда чётно.
- |V|число вершин дерева
Дерево — связный граф без циклов (родословное дерево, папки на компьютере, сеть с минимально возможным числом связей). В любом дереве рёбер ровно на одно меньше, чем вершин: добавление любого ребра создаёт цикл, удаление любого ребра нарушает связность.
Эйлеров путь проходит по каждому ребру ровно один раз, эйлеров цикл к тому же возвращается в начало. Теорема Эйлера: связный граф имеет эйлеров цикл тогда и только тогда, когда степени всех вершин чётны, и (незамкнутый) эйлеров путь — когда ровно две вершины имеют нечётную степень; путь начинается в одной из них и заканчивается в другой. В Кёнигсберге степени четырёх частей суши были 5, 3, 3 и 3: четыре нечётные вершины, поэтому прогулка невозможна. Гамильтонов путь проходит через каждую вершину ровно один раз; простого критерия для него не известно, а поиск кратчайшего такого маршрута (задача коммивояжёра) — одна из знаменитых трудных задач информатики.
«Домик»: квадрат ABCD (A — слева внизу, B — справа внизу, C — справа вверху, D — слева вверху) с диагоналями AC и BD и крышей D–E–C. Можно ли нарисовать его одним росчерком, не проводя ни одну линию дважды?
Показать решениеСкрыть решение
Степени: A = 3, B = 3, C = 4, D = 4, E = 2; сумма 16 = 2 · 8 ✓ (лемма о рукопожатиях).
Нечётных вершин ровно две (A и B), значит, эйлеров путь существует и начинается в A или в B.
Одно решение: A → B → D → E → C → D → A → C → B.
Эйлеров цикл невозможен, потому что у A и B нечётные степени.
а) Встретились 10 человек, и каждый пожал руку ровно троим. Сколько было рукопожатий? б) Может ли каждый из 7 человек пожать руку ровно троим?
Показать решениеСкрыть решение
б) Сумма была бы 7 · 3 = 21 — нечётное число, а она должна равняться 2|E|. Невозможно.
Главное
- p → q ложно только при p = 1, q = 0; p → q ≡ ¬q → ¬p, но не равносильно q → p.
- Отрицание: ∀ и ∃ меняются местами, ∧ и ∨ тоже (де Морган), ¬(p → q) ≡ p ∧ ¬q.
- Индукция: база P(1) плюс шаг P(n) ⇒ P(n + 1); обе части обязательны.
- |A ∪ B| = |A| + |B| − |A ∩ B|; (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ.
- Биекция = инъекция + сюръекция; обратная функция есть только у биекции.
- ∑ deg(v) = 2|E|; у дерева |E| = |V| − 1; для эйлерова пути нужно 0 или 2 нечётные вершины.
Проверь себя
Вопросов: 10. Каждый правильный ответ приносит XP.