1 ТЕОРИЯ МНОЖЕСТВ ОСНОВНЫЕ ПОНЯТИЯ ЛЕКЦИЯ 1 Факультет компьютерной инженерии и управления, кафедра АПВТ, ХНУРЭ Лектор – д.т.н., проф. Хаханов Владимир Иванович ДИСКРЕТНАЯ МАТЕМАТИКА
2 Цель лекции – изучение основных понятий теории множеств, способов задания множеств, законов алгебры множеств Содержание: Курс «Дискретная математика»: цель, структура Теория множеств как раздел дискретной математики Понятие множества Способы задания множеств Отношения принадлежности и включения Мощность множества. Пустое и универсальное множества Булеан и его мощность Операции над множествами Законы и тождества алгебры множеств Кантора Тема: Основные понятия теории множеств
3 Литература Горбатов В.А. Основы дискретной математики. М.: Высш. шк., 1986. C. 4-8. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Наука, 1984. C. 4-10. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергия, 1980. 344 с. Новиков Ф.А. Дискретная математика для программистов. С.-П., 2001. С. 4-24. Тевяшев А.Д., Гусарова И.Г. Основы дискретной математики в примерах и задачах. Харьков: ХТУРЭ, 2001. С. 4-7. Бондаренко М.Ф., Белоус Н.В., Руткас А.Г. Компьютерная дискретная математика. – Харьков: СМИТ, 2004. – 480 с. Хаханов В. І., Хаханова І.В., Кулак Е.М., Чумаченко С.В. Методичні вказівки до практичних занять з курсу “Дискретна математика”. Харків, ХНУРЕ. 2001. 87с. Хаханов В.И., Чумаченко С.В. Дискретная математика. Электронный учебник. ХНУРЭ: Электронная библиотека кафедры АПВТ (ауд. 320) NSERV\Library\ Чумаченко\Дискретная математика\...
4 Курс «Дискретная математика»: цель, структура Дискретная математика Прикладная теория цифровых автоматов Проектирование цифровых систем Техническая диагностика вычислительных систем и сетей Языки описания аппаратуры и программирования (Verilog, VHDL, C++, Java) Автоматизация проектирования цифровых систем и сетей Логическое моделирование Теория множеств Булева алгебра Теория графов Комбинаторный анализ Дискретная оптимизация Компьютерная инженерия Цель курса – формирование базовых знаний в области ДМ, необходимых для освоения методов анализа и синтеза аппаратных и программных средств цифровых вычислительных систем и сетей различного назначения, изучения теоретической базы информационных технологий, математических способов представления дискретных информационных процессов
5 Курс «Дискретная математика»: знания, умения, навыки Знания математический аппарат дискретной математики – множества и отношения, операции над ними, графы и операции над ними, формальные правила представления, минимизации и реализации логических функций; комбинаторика в части применения основных формул, методов оптимальных решений и их оценки при рассмотрении типовых задач Умения формулировать и решать практические задачи разработки программного обеспечения автоматизированных систем, синтеза и анализа цифровых дискретных объектов на основе выбора наиболее рационального математического аппарата дискретной математики с целью их оптимального решения Навыки вычисление теоретико-множественных операций, применение операций минимизации и поглощения, составление матриц для графов, правила минимизации булевых функций, определение полноты булевых функций
6 Немецкий ученый, математик, создатель теории множеств Родился в Петербурге в 1845г. В 1867 г. окончил Берлинский университет В 1872-1913 гг. – профессор университета в Галле Сформулировал общее понятие мощности множества (1878) Развил принципы сравнения мощностей множеств Систематически изложил принципы своего учения Созданная Кантором теория множеств, некоторые идеи которой имелись у его предшественников, послужила причиной общего пересмотра логических основ математики и оказала влияние на всю современную ее структуру Георг Кантор ( XIX-XX вв.) Историческая справка
7 Сегодня мы знаем, что, логически говоря, возможно вывести почти всю современную математику из единого источника – теории множеств Н. Бурбаки Никто не может изгнать нас из рая, который создал нам Кантор… Д. Гильберт Теория множеств как раздел дискретной математики
8 Термины Ключевые слова: подмножество принадлежность включение мощность пустое множество универсум булеан объединение пересечение дополнение симметрическая разность Базовые понятия: множество/ совокупность/набор элемент/объект операции над множествами
9 Множество является первичным понятием Множество рассматривается как совокупность объектов той или иной природы Объекты, которые образуют множество, называются его элементами Понятие множества Множество есть многое, мыслимое как единое Г. Кантор • Точка Информация Множество
10 Способы задания множеств Х A B C Способ Пример Перечисление элементов {a,b,c}, A={ 1, 3, 5, 7 } Характеристическое свойство A ={ a | a, обладающие свойством Q }, M={ x | P(x) } A={x | x=2k, k N }; M={x | sinx =1} Порождающая процедура (операции над множествами) X=(A B ) C Графически при помощи диаграмм Эйлера
11 Отношение принадлежности устанавливает связь между множеством и его элементами Объект принадлежит множеству, если он является его элементом Принадлежность элемента x множеству X обозначается при помощи символа : xX Пример Отношение принадлежности • m M • a • s m M s M a M d M • d
12 Отношение включения Устанавливает связь между двумя множествами: ( A B ) ( mA mB ) Обозначение: – строгое включение; – нестрогое включение А – подмножество множества В В – надмножество множества А Множества равны, если они состоят из одних и тех же элементов А В A B
13 Отношения принадлежности и включения: пример Дано множество A= {1, 2, 3, {3}, {4} }. Какие из следующих утверждений выполняются? 2 A – верно, так как в множестве А есть элемент 2 ; {1,2} A – верно, так как в множестве А имеются элементы 1,2, т.е. 1 A, 2 A ; 3 A – верно, поскольку в множестве А есть элемент 3 ; {3} A – верно, так как в множестве А есть элемент {3}; 4 A – не выполняется, так как в множестве А нет элемента 4 ; {4} A – верно, так как в множестве А имеется элемент {4} ; {4} A – не выполняется, поскольку в множестве А нет элемента 4, т.е. 4A. A • 2 • 1 • 3 •3 • 4 2 A {1,2} A 3 A {3} A 4A {4}A {4} A
14 Time Out
15 Мощность множества. Пустое и универсальное множества Мощность множества или кардинальное число определяет количество элементов данного множества Обозначения: |M|, card M Пустое множество не содержит ни одного элемента: ||=0 Универсальное множество U – надмножество всех множеств: М U
16 Булеан – множество всех подмножеств данного множества M Обозначение: B(M) Пример : дано множество A={a, b, c}. Найти В(А). B(A)={ , {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} } Мощность булеана определяется по формуле: |B(M)|=2 |M| Если А В и А ≠ В, то А – собственное подмножество множества В Пустое множество и само множество являются несобственными подмножествами множества М Остальные подмножества – собственные Булеан. Мощность булеана
17 Операции над множествами Название операции Определение Диаграммы Эйлера Пересечение A B={ x | xA и xB } Объединение A B={ x | xA или xB } Разность A\B={ x | x A и xB } Дополнение A= U \A={ x | x U и xA } Симметрическая разность A ∆B=(A\B) (B\A) = =( A B )\( A B ) А В A B A A A B
18 Законы и тождества алгебры множеств Кантора. 1 Название Формула Коммутативность A B=BA, AB=BA Ассоциативность ( A B ) С = A ( B С), ( AB ) С = A ( B С) Дистрибутивность ( A B )С=(АС)(ВС) ( A B )С=(АС)(ВС) Идемпотентность А А=А, АА=А Действия с константами А =А, А=, А U = U, AU=A Закон противоречия А А= Закон исключенного третьего A A = U Инволюция А=А
19 Законы и тождества алгебры множеств Кантора. 2 Название Формула Закон де Моргана А В=АВ, АВ=АВ Элиминация (А В)А=А, (АВ)А=А Склеивание (АВ)(АВ)=А, (АВ)(АВ)=А Законы Блэйка-Порецкого А(АВ)=АВ, А(АВ)=АВ А(АВ)=АВ, А(АВ)=АВ Формулы для определения мощности | A B | = |A|+|B|–| AB |, | A B | = |A|+|B|–| AB |
20 Алгебра множеств Кантора. Выводы Алгебра – совокупность носителя и сигнатуры Обозначение: А= <N, S> Замкнутость относительно операций Алгебра множеств Кантора: носитель – множества, сигнатура – набор операций Обозначение: A k =<N k, S k > Множества Операции Законы Алгебра множеств Кантора
21 Тест-вопросы 1. Могут ли повторяться элементы множества? а) да; б) нет. 2. Является ли множество несобственным подмножеством самого себя? а) да; б) нет. 3. Множества равны, если они содержат а) одни и те же элементы; б) одинаковое количество элементов. 4. Являются ли понятия «мощность» и «кардинальное число» идентичными? а) да; б) нет. 5. Определить мощность булеана множества F={a, {d, c} }: А) |B(F)|= 2; Б) |B(F)|= 4; В) |B(F)|= 0; Г) |B(F)|= 3.
22 Тест-вопросы 6. Что является константами в теории множеств: а) любое множество, б) булеан, в) любой элемент булеана, г) пустое множество, д) универсальное множество? 7. Какие формулы определяют закон элиминации? а) (А В)А=А, (АВ)А=А; б) A B=BA, AB=BA. 8. Как определяется дополнение множества а) A= U \A ; б) А= U ∆ А ? 9. Мощность множества вычисляется по формуле: а) |B(M)|=2 · |M| ; б) |B(M)|=2 |M|. 10. Какие подмножества являются собственными для множества F={a, {d, c} }: А) {a, {d, c} }, Б) {a}, В) {d, c}, Г) {{d, c}}, Д) ?
