1 теория множеств. Дискретная математика Лекция 1 Введение в дискретную математику
 Скачать 284.77 Kb.
|
|
Дискретная математика Лекция 1 Введение в дискретную математику. Элементы теории множеств. Лектор: Климова Елена Николаевна, доцент кафедры Математика и Информатика, к.ф-м.н. Введение в дискретную математику: понятие дискретности Дискретность – это свойство, позволяющее различать однотипные или однородные объекты. Дискретность – это прерывность, которая противопоставляется непрерывности, и означает скачкообразное (дискретное) изменение какой-либо величины во времени. Для компьютерных технологий “дискретный“ является синонимом “целочисленный“, например даже дробные числа должны получать особую форму дискретных чисел (кодов). Историческая справка Дискретная математика, по-существу, стала активно развиваться с начала XX века, когда стали изучаться возможности формализации математики и были получены фундаментальные результаты в области математической логики. Это результаты Поста, Клини и, особенно, Гёделя. Теорема неполноты Гёделя имеет мировоззренческое значение – она показывает ограниченность формальных методов построения математической теории. Тесно связаны с математической логикой исследования в области теории алгоритмов Тьюринга, Поста, Чёрча (также в начале XX века). Информатизация и компьютеризация общества во второй половине XX века в значительной степени стимулировала развитие дискретной математики. Теория множеств: основные понятия Основоположник теории множеств – немецкий математик Георг Кантор (1845-1918) Содержание лекции: Интуитивное определение понятия множества Способы задания множеств Подмножество Равенство множеств Операции над множествами и диаграммы Венна Декартово произведение множеств 1.1. Понятие множества Принадлежность элемента а множеству A непринадлежность: Обозначение множеств: Примеры множеств Множество студентов одной группы, элементами которого являются студенты; общий признак – обучение одной специальности. Числовые множества: N – множество натуральных чисел, Z – множество целых чисел, Q – множество рациональных чисел, R – множество действительных чисел, C – множество комплексных чисел. Множество всех решений уравнения. Элементы этого множества – вещественные числа, общий признак – обращение данного уравнения в верное равенство. Способы задания множеств Перечисление элементов множества: Задание множества порождающей процедурой: Задание множества описанием его свойств Мощность множества, пустое множество, универсальное множество Опр.1 Мощность множества – |М| Опр.2 Пустое множество – Опр.3 Универсальное множество – U 1.2. Подмножества Знак нестрогого включения Знак строгого включения Опр.4 Подмножество: Опр.5 Равенство множеств: Опр.6 Собственное подмножество: 1.3. Операции над множествами и диаграммы Венна Джон Венн (1894-1923) – английский ученый Диаграмма Венна – это замкнутая линия, внутри которой расположены элементы множества. Операции над множествами: Объединение Пересечение Разность Дополнение Симметрическая разность Опр.7 Объединение множеств А B Объединение 2-х множеств: Объединение небольшого количества множеств: Объединение всех множеств, принадлежащих S: Примеры объединения Вывод: Опр.8 Пересечение множеств А B Пересечение 2-х множеств: Для произвольной совокупности множеств: Пример: Опр.9 Разность множеств А B Пример: Опр.10 Дополнение множества Пример: Опр.11 Симметрическая разность А B Пример: Свойства операций над множествами Коммутативность: Идемпотентность: Ассоциативность: Дистрибутивность: . Законы поглощения: Свойства нуля и единицы: Инволютивность: Свойства дополнения Законы де Моргана 1.4. Декартово произведение множеств Вектор: Опр.12 Пример декартового произведения Теорема Следствие |