Дискретная математика. Лекция 1. Введение

Введение
Дискретная математика - это часть математики, спецификой которой является дискретность - антипод непрерывности. Она включает: теорию чисел, алгебру, математическую логику, теорию множеств, комбинаторику, теорию графов и сетей, теорию алгоритмов, формальные грамматики, теорию игр, теорию кодирования и т.д.

Теория множеств
Создатель теории множеств немецкий математик Георг Кантор (1845 – 1918) писал: «Под многообразием или множеством я понимаю вообще всякое многое, которое можно мыслить как единое, т.е. всякую совокупность определенных элементов, которая может быть связана в одно целое с помощью некоторого закона».

Кратко это формулируют так: «Множество — есть многое, мыслимое нами как единое». Но это не определение. Множество — одно из основных математических понятий, оно не определяется через другие. Мы должны его чувствовать интуитивно.
Группа студентов, спортивная команда, стая птиц, букет цветов, колония микробов — различные примеры множеств. Но множества могут состоять и из совершенно разнородных предметов.

Способы задания множеств

Операции над множествами

Каждый объект (сущность) характеризуется упорядоченной последовательностью значений реквизитов (кортежем). Каждый реквизит принимает значение из определенного множества - домена. Таким образом, объект определен на декартовом произведении доменов.
Введенные операции над множествами обладают следующими свойствами, которые доказываются взаимным включением.

Работа с множествами в Python
Множество в Python – неупорядоченная последовательность уникальных элементов.Рассмотрим примеры задания множества в Python (рис. 8).
Рис. 8. Задание множеств.

После выполнения фрагмента кода убеждаемся, что множества содержат только уникальные элементы.
Приведем примеры создания пустого множества (рис. 9).
Рис. 9. Варианты создания пустого множества
Сразу же возникает вопрос, как добавить элемент в множество. Напомню, что множества в языке Python являются объектами и, следовательно, обладают методами.

Рис. 10. Добавление элемента к множеству
Итак, для добавления элемента к множеству служит метод add(<элемент>). Рассмотрите пример. Объясните результат работы.
Рассмотрим теперь удаление элемента из множества.
Для этой цели предусмотрены два метода – remove(<элемент>) (рис. 11, 12) и discard(<элемент>) (рис. 13, 14).

Рис. 11 Удаление из множества наличествующего в нем элемента
Выполните фрагмент кода. Убедитесь, что элемент 7 будет удален.
Рис. 12. Попытка удаления из множества отсутствующего в нем элемента
В этом случае получаем аварийное сообщение.

Рис. 13. Удаление из множества наличествующего в нем элемента
Выполните фрагмент кода. Убедитесь, что элемент 7 будет удален.
Рис. 14. Попытка удаления из множества отсутствующего в нем элемента
В этом случае просто ничего не происходит.

Рассмотрим создание копии множества. Обратим внимание на типичную ошибку.
Рис. 15. Неудачная попытка копирования множества
Убедитесь, что действия над копией (множеством t) приводят к изменению оригинала (множества s).
Для корректного копирования множеств надо использовать метод copy() (рис. 16).

Рис. 16. Корректное копирование множества
Для удаления элементов множества служит метод clear() (рис. 17).
Рис. 17. Очистка множества

Для определения количества элементов множества служит функция len(<множество>) (рис. 18).
Рис. 18. Определение количества элементов множества
Обратите внимание. Данная функция не является методом объекта типа множество!

Мы можем в цикле перебрать все элементы множества (рис. 19).
Рис. 19. Циклический перебор элементов множества
Мы рассмотрели «технические» операции над множествами. Перейдем к рассмотрению теоретико-множественных операций

Эти операции могут выполняться с помощью «традиционных» функций и с помощью методов.
Объединение множеств (рис. 20).
Рис. 20. Объединение множеств
Объединение множеств выполняется с помощью операции “|” и метода union(<множество>). При этом множества – операнды p и q не изменяются.

Рассмотрим операцию добавления элементов одного множества в другое (рис. 21, 22).
Рис. 21. Добавление элементов множества q в множество p (1 способ)
Рис. 22. Добавление элементов множества q в множество p (2 способ)

Пересечение множеств также выполняется двумя способами (рис. 23).
Рис. 23. Пересечение множеств
Пересечение множеств выполняется с помощью операции “&” и метода intersection(<множество>). При этом множества – операнды p и q не изменяются.
Рассмотрим еще два способа реализации пересечения множеств (рис. 24, 25).

Рис. 24. Построение пересечения множеств (способ 1).
Рис. 25. Построение пересечения множеств (способ 2).
Рассмотрим два способа построения разности множеств (рис. 26).

Рис. 26. Разность множеств
Существуют еще два способа получить разность множеств - с помощью операции «-=» и метода difference_update(<множество>). Студенты смогут изучить их самостоятельно.
Такой же набор способов существует для получения симметрической разности.

Рис. 27. Симметричная разность множеств
Существуют еще два способа получить симметричную разность множеств - с помощью операции «^=» и метода symmetric_difference_update(<множество>). Студенты смогут изучить их самостоятельно.
Рассмотрим операции сравнения множеств.

Рис. 28 Проверка принадлежности элемента множеству
Рис. 29. Проверка равенства множеств
Рис. 30. Проверка того, что множество является подмножеством другого
/

В итоге рассмотренной операции возвращается True и в случае равенства множеств-операндов. При использовании операции «<» d в случае равенства множеств возвращается False.
Операции «>=»,issuperset(<множество>), «>» предназначены для проверки включения второго множества-операнда в первое. Студенты могут изучить их самостоятельно.

Для проверки, является ли пересечение множеств пустым служит метод isdisjoint(<множество>) (рис. 30).
Рис. 31. Проверка наличия пустого пересечения множеств
Перечисление всех элементов множества часто неудобно или даже невозможно. Рассмотрим некоторые способы генерации множеств.