Дискретная математика для IT
Все объяснения, задачи и лабораторная в одном месте.
Можно сохранить страницу в PDF через печать браузера. Для печати разборы ответов раскрываются автоматически.
1. Логика высказываний и таблицы истинности
Объяснение
Импликация A⇒B ложна только при истинном A и ложном B. Она не утверждает причинность. Для отрицания составного условия применяются законы де Моргана: не(A и B) равносильно не A или не B.
Задача для самостоятельного решения
Постройте отрицание условия «авторизован и владелец».
Показать разбор ответа
Отказ разрешён, когда пользователь не авторизован или не владелец. Для четырёх комбинаций разрешение истинно только в случае (истина, истина).
2. Множества, отношения и функции
Объяснение
Множество не содержит повторений. Отношение задаёт пары элементов; функция сопоставляет каждому входу ровно один выход. Эквивалентность требует рефлексивности, симметричности и транзитивности.
Задача для самостоятельного решения
Является ли отношение «одинаковый остаток по модулю 3» эквивалентностью?
Показать разбор ответа
Да: число имеет собственный остаток; равенство остатков симметрично и транзитивно. Классы: остатки 0, 1, 2; числа 2 и 8 принадлежат одному классу.
3. Комбинаторика и принцип Дирихле
Объяснение
При независимом последовательном выборе число вариантов перемножается. Перестановки учитывают порядок, сочетания — нет. Принцип Дирихле гарантирует повторение, если объектов больше, чем ящиков.
Задача для самостоятельного решения
Сколько неупорядоченных пар можно выбрать из пяти серверов?
Показать разбор ответа
C(5,2)=5×4/2=10. Деление на два убирает повтор пары A,B и B,A. При шести объектах в пяти корзинах хотя бы одна корзина содержит два объекта.
4. Индукция, инварианты и доказательства
Объяснение
Индукция состоит из базы и перехода от n к n+1. Проверка множества примеров не заменяет переход. Инвариант цикла связывает состояние до итерации, сохранение свойства и результат при остановке.
Задача для самостоятельного решения
Докажите сумму 1+…+n=n(n+1)/2.
Показать разбор ответа
База n=1 верна. Добавляем n+1 к n(n+1)/2: получаем (n+1)(n+2)/2, то есть формулу следующего шага. Это доказательство для всех натуральных n.
5. Графы, деревья и маршруты
Объяснение
Дерево — связный неориентированный граф без циклов. У дерева из n вершин n−1 ребро. Ориентированный ациклический граф допускает топологический порядок, удобный для зависимостей сборки.
Задача для самостоятельного решения
Можно ли выполнить зависимости A→B, B→C, C→A?
Показать разбор ответа
Топологический порядок невозможен: есть цикл. Алгоритм удаления вершин без входящих рёбер застрянет сразу. Нужно изменить зависимости, а не случайно переставлять задачи.
6. Вероятность и статистическое мышление
Объяснение
Условная вероятность меняется при получении наблюдения. Базовая частота влияет на полезность классификатора: высокая чувствительность сама по себе не означает достоверность положительного результата.
Задача для самостоятельного решения
Из 1000 событий 10 опасны. Детектор находит все 10, но ошибочно отмечает 99 нормальных. Какова точность положительных ответов?
Показать разбор ответа
Precision=10/(10+99)≈9,17%. Recall=100%. Это разные характеристики: система не пропускает опасные события, но создаёт много ложных тревог.
Лабораторная работа
Подготовка
Python 3; используем полный перебор как проверку конечного случая, не как замену доказательству.
Учебный пример
from itertools import product
for a,b in product([False,True], repeat=2):
left = not (a and b)
right = (not a) or (not b)
assert left == right
print(a,b,left)Как работает пример и что ожидать
Строки для False/False, False/True и True/False дают True; True/True даёт False. Это полная таблица истинности двух булевых переменных. Для утверждения о всех натуральных числах конечного перебора недостаточно: используйте базу и переход индукции.
Итоговая работа
Оформите решения по логике доступа, сочетаниям, индукции и графу зависимостей. Для каждого укажите область допустимых входов и доказательство. Программой проверьте малые случаи и специально найдите контрпример ложному утверждению.
Проверка результата
1. Опишите исходные данные и условия запуска, чтобы другой человек мог повторить работу.
2. Приложите результат обычного сценария и сравните его с ожидаемым.
3. Проверьте неверный вход, граничный случай и отказ зависимости, если она есть.
4. Объясните выбранное решение и известное ограничение.
5. Сохраните исправления после самопроверки вместе с примером, который раньше не работал.
Как оценить работу
По каждому пункту поставьте 0 (не выполнено), 1 (выполнено с пробелами) или 2 (результат воспроизводим и объяснён). Если обязательный сценарий не работает, вернитесь к нему независимо от общей суммы. Это рубрика самопроверки: сайт не исполняет присланный код и не выдаёт автоматическую оценку проекта.