- •Введение
- •Предисловие
- •1. Теория множеств
- •1.1. Понятие множества
- •1.2. Операции над множествами
- •1.3. Основные тождества алгебры множеств
- •1.4. Кортежи и декартово произведение множеств
- •1.5. Бинарные отношения. Свойства отношений
- •1.6. Соответствия. Отображения. Функции
- •Вопросы для самопроверки
- •2. Элементы комбинаторики
- •Вопросы для самопроверки
- •3. Логические операции
- •3.1. Основные понятия
- •3.2. Простейшие связки (операции)
- •3.3. Другие связки (операции)
- •3.4. Основные законы, определяющие свойства введенных логических операций.
- •4. Булевы функции
- •4.1. Основные понятия
- •4.2. Свойства элементарных булевых функций
- •4.3. Дизъюнктивные и конъюнктивные нормальные формы алгебры высказываний
- •4.4. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы
- •Задачи по теме «Булевы функции.»
- •Вопросы для самопроверки
- •5. Теория графов
- •5.1. Ориентированные графы
- •5.2. Неориентированные графы
- •5.3. Матричное задание ориентированных графов
- •5.4. Матричное задание неориентированных графов
- •5.5. Изоморфизм графов
- •5.6. Операции над графами
- •5.7. Пути, контуры, маршруты, цепи, циклы
- •5.8. Расстояние в графах
- •5.9. Связность в неориентированных графах
- •5.10. Связность в ориентированных графах
- •5.11. Эйлеровы графы
- •5.12. Гамильтоновы графы
- •5.13. Деревья
- •5.14. Остовные деревья
- •5.15 Взвешенные графы. Экстремальные остовы графов
- •5.16 Поиск кратчайшего пути между вершинами. Алгоритм Дейкстры
- •5.17 Раскраска графов. Раскраска вершин графа
- •Вопросы для самопроверки
- •Библиографический список
- •Оглавление
- •Подписано к изданию «8» октября 2014.
- •394026 Воронеж, Московский просп., 14
1.2. Операции над множествами
Объединением (суммой) множеств А и В называется множество элементов, принадлежащих хотя бы одному из данных множеств. Множество содержит элементы, принадлежащие либо множеству А, либо множеству В, либо одновременно множествам А и В. Объединение множеств формально можно описать следующим образом:
.
Для наглядного представления операций с множествами используют диаграммы Венна. В диаграмме Венна все точки прямоугольника образуют универсальное множество U, а круги внутри прямоугольника являются подмножествами А и В.
Объединению множеств соответствует заштрихованная область на рис. 1. Операция объединения множеств коммутативна, т.е. .
Пересечением (произведением) множеств А и В называется множество элементов, принадлежащих одновременно множеству А и множеству В. Пересечение множеств формально можно описать следующим образом:
.
На диаграмме Венна (рис.2) пересечению множеств соответствует заштрихованная область.
Операция пересечения множеств коммутативна, т.е. .
Отметим, что выполняются включения
;
Если А и В — непустые множества, пересечение которых пусто, т. е. А В =Ø, то множества называют непересекающимися.
Разностью множеств А и В называется множество элементов, принадлежащих А и не принадлежащих В. Формально разность множеств описывается следующим образом
.
Разность множеств указана штриховкой на рис. 3
Пример 1.2. Пусть заданы множества , , . Тогда объединение множеств равно: , пересечение , разность множеств = .
Стоит отметить, что в отличие от предыдущих операций разность множеств является некоммутативной операцией, т.е. .
Пример 1.3. Пусть множество А представляет собой промежуток на числовой оси , а множество В-промежуток . Тогда разностью является множество , удовлетворяющее неравенству .
Дополнением множества А до множества U называется множество элементов, которые не содержатся в множестве А, но содержится в множестве U. Дополнение может быть представлено как разность множеств . Множество, соответствующее дополнению , заштриховано на рис. 4.
Пример 1.4. Пусть универсальное множество U-множество всех сотрудников предприятия, А - множество сотрудников старше 40 лет, В – множество менеджеров предприятия, С – множество сотрудников со стажем работы на предприятии более 5 лет. Тогда - множество менеджеров старше 40 лет, - множество сотрудников со стажем работы не более 5 лет, - множество менеджеров, имеющих стаж работы не более 5 лет, - множество сотрудников предприятия со стажем работы более 5 лет, не являющихся менеджерами.
1.3. Основные тождества алгебры множеств
Введенные операции над множествами подчинены некоторым очень простым абстрактным законам. Множество, его подмножества и законы сочетания подмножеств образуют алгебраическую систему, называемую булевой алгеброй. Ниже перечислены основные законы, действующие в булевых алгебрах для универсального множества U, и подмножеств А, В, С.
Законы для объединения и пересечения:
1. = (закон идемпотентности).
2. (закон идемпотентности).
3. (коммутативность операции объединения множеств).
4. (коммутативность операции пересечения множеств).
5. (ассоциативность операции объединения множеств).
6. (ассоциативность операции пересечения множеств).
7. (дистрибутивность операции пересечения относительно операции объединения)
8. (дистрибутивность операции объединения относительно операции пересечения)
9. .
10. Ø=Ø (свойство нуля).
11. .
12. Ø= (свойство нуля).
Законы для дополнений:
1. = (закон двойного отрицания).
2. (закон комплиментарности).
3. =Ø (закон комплиментарности).
4. (закон двойственности).
5. (закон двойственности).
6. =Ø.
Законы для разности множеств:
1. .
2. .
3. =Ø.
4. Ø= .
5. Ø/ =Ø.
6. =Ø.
7. .
8. .
9. .
10. .
Законы поглощения
Доказательство каждого из перечисленных законов основано на определении равенства множеств (взаимовключения множеств). Докажем один из законов двойственности для дополнений: = .
Пусть . По определению операции дополнения это означает, что , но . Следовательно, и одновременно . Таким образом, и х . Из определения операции пересечения получаем, что х . Поэтому, учитывая произвольность элемента х , имеем .
Пусть теперь . Это значит, что одновременно выполняются условия , x или, другими словами, и . Следовательно, .Таким образом, . Поскольку х — произвольный элемент из , то окончательно получаем .