Введение в дискретную математику

Дискретная математика изучает математические структуры, которые по своей природе дискретны — не непрерывны. Там, где математический анализ работает с гладкими кривыми, дискретная математика оперирует с различимыми, отделёнными значениями: целыми числами, графами, логическими высказываниями.

Пропозициональная логика

Высказывание — это повествовательное предложение, которое является либо истинным, либо ложным, но не тем и другим одновременно.

Логические связки

Высказывания можно комбинировать с помощью логических связок:

• Конъюнкция ($p \land q$): истинна только когда оба $p$ и $q$ истинны
• Дизъюнкция ($p \lor q$): истинна когда хотя бы одно из $p$, $q$ истинно
• Отрицание ($\lnot p$): меняет значение истинности на противоположное
• Импликация ($p \to q$): ложна только когда $p$ истинно, а $q$ ложно

Законы де Моргана

Основы теории множеств

Множество — это неупорядоченная коллекция различных объектов, называемых элементами.

A = {1, 2, 3, 4, 5}
B = {3, 4, 5, 6, 7}

# Принадлежность
print(3 in A)       # True  (3 ∈ A)

# Операции над множествами
объединение = A | B   # {1, 2, 3, 4, 5, 6, 7}  (A ∪ B)
пересечение = A & B   # {3, 4, 5}               (A ∩ B)
разность = A - B      # {1, 2}                  (A \ B)

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

Для конечных множеств $A$ и $B$:

Методы доказательств

Прямое доказательство

Чтобы доказать $p \to q$: предположим, что $p$ истинно, и покажем, что из этого следует $q$.

Доказательство от противного

Чтобы доказать $p$: предположим $\lnot p$ и выведем противоречие.

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

1. Базовый случай: покажем, что $P(n_0)$ истинно
2. Индуктивный шаг: покажем, что $P(k) \to P(k+1)$ для всех $k \geq n_0$

Дальше

Имея в арсенале логику, множества и методы доказательств, вы готовы перейти к Основным концепциям — где мы подробно изучим отношения, функции и комбинаторику.