Лекция 1 Введение в дискретную математику. Элементы теории множеств. Дискретная математика Лектор : Данилова Соелма Доржигушаевна, доцент кафедры систем информатики, к. т. н.

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

Историческая справка Дискретная математика, по - существу, стала активно развиваться с начала XX века, когда стали изучаться возможности формализации математики и были получены фундаментальные результаты в области математической логики. Это результаты Поста, Клини и, особенно, Гёделя. Теорема неполноты Гёделя имеет мировоззренческое значение – она показывает ограниченность формальных методов построения математической теории. Тесно связаны с математической логикой исследования в области теории алгоритмов Тьюринга, Поста, Чёрча ( также в начале XX века ). Информатизация и компьютеризация общества во второй половине XX века в значительной степени стимулировала развитие дискретной математики.

Теория множеств : основные понятия Основоположник теории множеств – немецкий математик Георг Кантор ( ) Содержание лекции : Интуитивное определение понятия множества Способы задания множеств Подмножество Равенство множеств Операции над множествами и диаграммы Венна Декартово произведение множеств

1.1. Понятие множества Принадлежность элемента а множеству A непринадлежность: Обозначение множеств:

Примеры множеств 1. Множество студентов одной группы, элементами которого являются студенты ; общий признак – обучение одной специальности. 2. Числовые множества : N – множество натуральных чисел, Z – множество целых чисел, Q – множество рациональных чисел, R – множество действительных чисел, C – множество комплексных чисел. 3. Множество всех решений уравнения. Элементы этого множества – вещественные числа, общий признак – обращение данного уравнения в верное равенство.

Способы задания множеств 1. Перечисление элементов множества : 2. Задание множества порождающей процедурой : 3. Задание множества описанием его свойств

Мощность множества, пустое множество, универсальное множество Опр.1 Мощность множества – | М | Опр.2 Пустое множество – Опр.3 Универсальное множество – U

1.2. Подмножества Знак нестрогого включения Знак строгого включения Опр.4 Подмножество: Опр.5 Равенство множеств: Опр.6 Собственное подмножество:

1.3. Операции над множествами и диаграммы Венна Джон Венн ( ) – английский ученый Диаграмма Венна – это замкнутая линия, внутри которой расположены элементы множества. Операции над множествами : Объединение Пересечение Разность Дополнение Симметрическая разность

Опр.7 Объединение множеств А B Объединение 2-х множеств: Объединение небольшого количества множеств: Объединение всех множеств, принадлежащих S :

Примеры объединения Вывод:

Опр.8 Пересечение множеств А B Пересечение 2-х множеств: Для произвольной совокупности множеств: Пример:

Опр.9 Разность множеств А B Пример:

Опр.10 Дополнение множества Пример:

Опр.11 Симметрическая разность А B Пример:

Свойства операций над множествами 1. Коммутативность : 2. Идемпотентность : 3. Ассоциативность : 4. Дистрибутивность :. 5. Законы поглощения : 6. Свойства нуля и единицы : 7. Инволютивность : 8. Свойства дополнения 9. Законы де Моргана

1.4. Декартово произведение множеств Вектор: Опр.12

Пример декартового произведения

Теорема Следствие