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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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