Дискретная математика
Дискретная математика изучает отдельные, счётные объекты: истинно или ложно, в множестве или вне его, этот путь или тот. На ней работают компьютеры, и начинается она с логики, которую можно включать и выключать.
Обновлено
Дискретная математика изучает отдельные, счётные объекты. Высказывание истинно или ложно, элемент лежит в множестве или нет, в сети между двумя точками есть связь или её нет. Ничего промежуточного нет, в этом и смысл слова «дискретный», и именно так мир видит компьютер.
Первый курс охватывает шесть тем: логику, множества, комбинаторику, графы, теорию чисел и доказательства. Логика идёт первой, потому что на её языке записаны все остальные темы. Выберите связку ниже и переключайте p и q.
Таблица истинности для p ∧ q
| p | q | p ∧ q |
|---|---|---|
| И | И | И |
| И | Л | Л |
| Л | И | Л |
| Л | Л | Л |
Переключайте p и q или нажмите на строку. Выделена та строка, которую они выбирают.
Читайте p как «x лежит в A», а q как «x лежит в B». Закрашены области, где высказывание истинно; точка показывает текущую строку.
p ∧ q
Как читать p и q
При этих значениях p ∧ q истинно.
Истинно, только когда истинны и p, и q.
На языке множеств И соответствует пересечению: x лежит в A ∩ B ровно тогда, когда x лежит в A и x лежит в B.
Логика: высказывания и связки
Высказывание представляет собой предложение, которое либо истинно, либо ложно, например «7 является простым числом» или «идёт дождь». Логика строит большие высказывания из меньших с помощью нескольких связок, а таблица истинности показывает результат для каждого сочетания входов.
| символ | название | как читать | истинно, когда |
|---|---|---|---|
| ∧ | И, конъюнкция | «p и q» | оба истинны |
| ∨ | ИЛИ, дизъюнкция | «p или q» | хотя бы одно истинно |
| ¬ | НЕ, отрицание | «не p» | p ложно |
| ⊕ | XOR, исключающее ИЛИ | «p или q, но не оба» | истинно ровно одно |
| → | импликация | «если p, то q» | во всех случаях, кроме p истинно и q ложно |
| ↔ | эквиваленция | «p тогда и только тогда, когда q» | у p и q одинаковое значение |
Две из них удивляют. Логическое ИЛИ включающее: «p или q» истинно, когда истинны оба, в отличие от бытового «чай или кофе?». У исключающего варианта своё название, XOR.
Второй сюрприз: импликация. p → q ложна только в одной строке, когда p истинно, а q ложно. Думайте о ней как об обещании: «если пойдёт дождь, я возьму зонт». Обещание нарушено, только если дождь пошёл, а зонта нет. В сухой день обещание не нарушено, что бы вы ни несли, поэтому высказывание считается истинным.
Равносильные высказывания
Два высказывания равносильны, когда их таблицы истинности совпадают в каждой строке. В виджете выберите ИЛИ и включите отрицание p: столбец для ¬p ∨ q совпадает со столбцом для p → q, так что оба говорят одно и то же.
Самые полезные равносильности называют законами де Моргана; они говорят, как НЕ проходит через И и ИЛИ:
¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q
Словами: «не оба сразу» равносильно «одно из них ложно», а «ни то, ни другое» равносильно «оба ложны». Программисты пользуются этим каждый день, чтобы переписать условие вроде «не (вошёл в систему и подтверждён)».
Логика и множества: одна идея
Читайте p как «x лежит в A», а q как «x лежит в B». Тогда И становится пересечением, ИЛИ объединением, а НЕ дополнением, и каждая таблица истинности превращается в закрашенную диаграмму Венна; поэтому виджет рисует её рядом с таблицей. Законы де Моргана становятся правилами для множеств:
(A ∩ B)′ = A′ ∪ B′
Страница про обозначения множеств закрашивает каждое из них на диаграмме, по которой можно щёлкать.
Комбинаторика
Считать в дискретной математике значит считать, не перечисляя. Основную работу делают два правила.
Правило произведения. Если один выбор можно сделать m способами, а второй n способами, то пару можно выбрать m × n способами. У 4-значного PIN-кода на каждую цифру 10 вариантов, поэтому возможных кодов 10^4 = 10000.
Сочетания. Число способов выбрать k объектов из n, когда порядок не важен, записывают как C(n, k). Выбор 3 начинок из 8:
C(8, 3) = (8 × 7 × 6) / (3 × 2 × 1) = 56
Числитель считает упорядоченные выборы, а деление на 3 × 2 × 1 убирает 6 порядков, в которых можно было выбрать те же три начинки.
Ответ: 6 × 5, делённое на 2, то есть 15. Если у вас получилось 30, вы посчитали каждую пару дважды, по разу в каждом порядке.
Графы
Граф представляет собой набор точек, называемых вершинами, соединённых линиями, называемыми рёбрами. Он моделирует всё, что состоит из связей: дороги между городами, друзей в социальной сети, ссылки между веб-страницами.
Первый результат: если 5 человек по разу пожимают руки друг другу, рукопожатий C(5, 2) = 10. Каждый пожимает 4 руки, что даёт 5 × 4 = 20 «концов» рукопожатий, а у каждого рукопожатия два конца, так что 20 / 2 = 10. Это рассуждение называют леммой о рукопожатиях: сумма степеней всех вершин вдвое больше числа рёбер.
Теория чисел и доказательства
Арифметика остатков похожа на арифметику на циферблате. 17 mod 5 равно 2, остатку от деления 17 на 5. Через девять часов после 8 часов будет 5 часов, потому что 17 mod 12 равно 5. Та же идея с очень большими числами лежит в основе шифрования RSA, на котором работают защищённые сайты.
Доказательство по индукции показывает, что утверждение верно для каждого натурального n, в два шага: проверьте его для n = 1, затем покажите, что если оно верно для некоторого n, то верно и для n + 1. Так доказывают, например, что
1 + 2 + ... + n = n(n + 1) / 2
для каждого n, а не только для проверенных значений.
Где применяется дискретная математика
- Программирование: каждый условный оператор if является логикой, а законы де Моргана переписывают условия.
- Базы данных: запрос, который соединяет или фильтрует таблицы, состоит из операций над множествами.
- Алгоритмы: комбинаторика говорит, сколько шагов делает программа при росте входных данных.
- Сети и карты: кратчайшие маршруты и социальные сети сводятся к задачам на графах.
- Безопасность: шифрование опирается на теорию чисел и арифметику остатков.
- Аппаратура: процессор собран из логических вентилей, а они представляют собой таблицы истинности в кремнии.
Сложная ли дискретная математика?
Она сложна иначе, чем алгебра и математический анализ. Формул для запоминания мало и арифметика простая, но многие задачи просят доказать что-то, а не вычислить, и написать убедительное рассуждение большинству студентов приходится учиться заново.
Больше всего помогает разбирать небольшие случаи вручную, прежде чем искать закономерность: нарисуйте диаграмму Венна, выпишите таблицу истинности, перечислите все случаи. Поначалу обозначения кажутся тяжёлыми, но в основном это символы с этой страницы и со страницы про обозначения множеств.
Частые вопросы
- Что такое дискретная математика?
- Раздел математики, который изучает отдельные, счётные объекты, а не плавно меняющиеся величины. Её главные темы: логика, множества, комбинаторика, графы, теория чисел и доказательства. Математический анализ спрашивает, как величины меняются непрерывно; дискретная математика спрашивает, сколько, какие именно и истинно ли высказывание.
- Сложная ли дискретная математика?
- Она сложна иначе, чем математический анализ. Формул для применения меньше, а рассуждений, которые нужно выстроить, больше, и для многих студентов это первый курс, построенный вокруг доказательств. Алгебры обычно немного. Тем, кому трудно, в основном приходится привыкать к доказательствам, и это быстро улучшается с практикой на небольших примерах.
- Где применяется дискретная математика?
- Почти везде в информатике. На логике работают схемы и условные операторы if, на множествах основаны запросы к базам данных, комбинаторика говорит, сколько времени займёт алгоритм, графы моделируют сети и карты, а теория чисел лежит в основе шифрования, которое защищает онлайн-платежи.
- Какие темы входят в дискретную математику?
- Типичный первый курс охватывает логику высказываний и таблицы истинности, множества и диаграммы Венна, функции и отношения, методы доказательства, включая индукцию, подсчёт с помощью перестановок и сочетаний, основы теории вероятностей, графы и деревья, а также арифметику остатков. Некоторые курсы добавляют рекуррентные соотношения и булеву алгебру.
- Нужна ли дискретная математика для информатики?
- Да. Почти любая программа по информатике требует её, обычно на первом или втором курсе, потому что алгоритмы, структуры данных и теория вычислений опираются на неё. Программировать можно начать и без неё, но логика, множества и подсчёт появляются в повседневном коде раньше, чем многие ожидают.
- Чем дискретная математика отличается от непрерывной?
- Дискретная математика имеет дело со значениями, которые можно перечислить по одному, например с целыми числами, с истиной и ложью или с узлами сети. Непрерывная математика, например математический анализ, имеет дело с величинами, которые могут принимать любое значение в промежутке, например со временем, расстоянием или температурой.
- Что такое таблица истинности?
- Таблица, в которой перечислены все сочетания истины и лжи для входов логического высказывания и значение высказывания для каждого из них. При двух входах p и q в ней четыре строки. Таблицей истинности доказывают, что два высказывания равносильны: если их столбцы совпадают в каждой строке, они всегда согласны.
