- •1. Элементы теории множеств
- •1.1 Множества. Основные понятия
- •1.2. Способы задания множеств
- •1.3. Операции над множествами. Диаграммы Венна
- •1.4. Свойства операций над множествами
- •1.5. Прямое (декартово) произведение множеств
- •1.6 Разбиения и покрытия
- •1.7. Замечание о мощности некоторых множеств
- •1.8 Представление множеств в эвм
- •1.9. Отношения
- •1.9.1.Определения
- •1.9.2 Бинарные отношения
- •1.9.3. Способы задания бинарных отношений
- •1.9.4 Свойства бинарных отношений
- •1.9.5. Отношение эквивалентности
- •1.9.5. Отношение порядка
- •1.9.6.1. Минимальные и максимальные элементы множества
- •1.9.6.2. Диаграммы Хассе
- •1.9.6.3. Принцип двойственности
- •1.9.7. Представление отношений в эвм
- •1.10. Соответствия. Функции. Операции. Отображения
- •1.10.1. Соответствия и их свойства
- •1.10.2 Функции и отображения
- •1.10.3. Инъекция, сюръекция и биекция
- •1.10.4. Композиция и суперпозиция функций. Способы задания функций
- •1.10.5. Представление функций в эвм
- •1.10.6. Операции
- •1.10.6.1. Способы задания операций
- •1.11. Алгебраические структуры
- •1.11.2. Замыкание и подалгебры
- •1.11.3. Гомоморфизм и изоморфизм
- •1.11.4. Алгебры с одной бинарной операцией
- •1.11.5. Алгебры с двумя бинарными операциями
- •1.11.6.Решетки
- •1.11.7. Булевы алгебры
- •2. Элементы математической логики и булевы функции
- •2.1. Операции над высказываниями
- •2.2. Логические операции (логические связки)
- •2.3. Элементарные булевы функции
- •2.3.1. Функции алгебры логики
- •2.3.2. Равносильность функций. Существенные и несущественные переменные
- •2.3.3. Реализация функций формулами. Суперпозиция функций
- •2.3.4. Подстановки и замены
- •2.3.5. Принцип двойственности
- •2.3.6. Нормальные формы в логике высказываний
- •2.3.6.1. Разложение булевых функций по переменным. Дизъюнктивно-нормалльная форма (днф)
- •2.3.6.2. Совершенная дизъюнктивная нормальная форма
- •2.3.7. Арифметические операции в алгебре логики. Полиномы Жегалкина
- •2.3.8. Монотонные функции алгебры логики
- •2.3.9. Функционально замкнутые классы
- •2.4. Полнота системы булевых функций. Теорема
- •2.5. Элементы логике предикатов
- •2.5.1. Определение предиката
- •2.5.2. Кванторы. Формулы логики предикатов
- •2.5.3. Равносильность формул
- •2.5.4. Предикаты на конечных областях. Логика одноместных предикатов
- •2.6. Операции над предикатами и кванторами
- •2.7. Построение доказательств в логике предикатов
- •1.6.2. Разбор решений задач по логике предикатов
- •1. Элементы теории множеств 3
- •1.1 Множества. Основные понятия 3
- •2.6. Операции над предикатами и кванторами 137
- •394026 Воронеж, Московский просп., 14
1.3. Операции над множествами. Диаграммы Венна
Для получения новых множеств из уже существующих используют операции над множествами. Рассмотрим основные из них. Пусть рассматриваемые множества .
1. Дополнением (до U) множества (обозначается ) называется множество всех элементов, не принадлежащих А (но принадлежащих U): .
2. Объединением множеств А и В (обозначается ) называется множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств А, В (входящих в множество А, или В, или оба). Другие обозначения: А+В, (или). Таким образом,
.
3. Пересечение множеств А и В (обозначается ) называется множество тех элементов, которые принадлежат и множеству А, и множеству В. Другие обозначения: ; (и). Таким образом,
.
4. Разностью множеств А и В (обозначается называется множество всех тех элементов А, которые не принадлежат В: .
5. Дизъюнктивной суммой (обозначается ; ) называется множеством элементов входящих или в А, или в В, но не одновременно в А и В. Эквивалентно «разделительному» «или»: ; иначе ; .
Пример 1. Пусть А={1, 2, 3} и В={3, 4, 5}.
Тогда ; ={3}; ; . .
Универсальное множество U здесь не определено, поэтому, строго говоря, операции дополнения над множествами А и В не могут быть выполнены. Для этого нужно дополнить условие: пусть U={1, 2, 3, 4, 5}. Тогда : ; .
Пример 2. Дано: U={1, 2, 3, 4}; A={1, 3, 4}; B={2, 3}; C={1, 4}
Найти: а) ; б) ; в) ; г) .
Решение:
а) .
б)
в)
г)
Различные операции с множествами удобно изображать с помощью диаграмм Венна (Эйлера). Построение диаграммы заключается в изображении большого прямоугольника, представляющего универсальное множество U, а внутри него – каких-нибудь замкнутых фигур (кругов, треугольников и
т. п.), представляющих множества. Результат выделяется штриховкой.
Пусть
А B
Тогда
Замечание 1. Операции объединения, пересечения и дополнения часто называют булевыми операциями над множествами.
Замечание 2. Операции объединения и пересечения в P(U), множестве всех частей множества U, аналогичны операциям сложения и умножения в Z.
1.4. Свойства операций над множествами
Операции над множествами обладают определёнными свойствами и удовлетворяют некоторым соотношениям.
1. Коммутативность операций и :
; .
2. Ассоциативность операций и :
;
.
3. Законы идемпотентности:
; .
4. Законы дистрибутивности:
А;
5. Законы поглощения:
;
6. Законы де Моргана
.
7. Операции с несобственными подмножествами:
, , , , , .
8. Инволюция (закон двойного отрицания):
В справедливости данных свойств можно убедиться, например, нарисовав диаграммы Венна для левой и правой частей равенства и проверить, что они совпадают.
Пример: Доказать с помощью диаграмм Венна справедливость соотношения:
(Свойство дистрибутивности 4 операции пересечения относительно объединения).
Из диаграмм видно равенство обеих частей.
Вообще же в теории множеств наиболее часто используются следующие приёмы доказательств:
1. Доказательство равенства соотношений типа X=Y.
2. Доказательство единственности и существования.
3. Доказательство от противного.
а ). A B A B
U C U C
(Левая часть)
б ). A B A B
U C U C
A B (Правая часть)
U C
Пример. Докажем справедливость предыдущего соотношения, используя второе определение равенства X=Y:
Решение. Множества равны, если и .
1. Сначала докажем, что
, (*)
т. е., что любой элемент а из множества, заданного левой частью соотношения (*), принадлежит и правому множеству соотношения. Пусть .
Тогда аА и аÎ А и (аÎ В или аÎ С)
(аÎ А и аÎ В) или (аÎ А и аÎ С) Þ или Þ .
Т. е.
2. Теперь покажем, что , т. е. любой элемент из множества, заданного правой частью (*), принадлежит и множеству, заданному левой частью.
Пусть . Тогда или
Þ (аÎ А и аÎ В) или (аÎ А и аÎ С) Þ аÎ А и (аÎ В или аÎ С) Þ аÎ А и (аÎ В или аÎ С) Þ аÎ А и
Þ .
Следовательно, .
Таким образом, , ч. т. д.
В качестве следующего примера докажем один из законов де Моргана.
Пример. Доказать
Решение. С одной стороны, Þ
.
С другой стороны,
.
Так как и , то , ч. т. д.
Утверждение 1. Следующие предположения о произвольных множествах попарно эквивалентны:
1) 2) Û 3) Û 4) А\В = Û 5) .
Доказательство: 12. Так как , то достаточно показать, что А В влечёт . Но если хА, то по условию хВ, следовательно .
23. Так как , то . По закону поглощения и закону коммутативности имеем . Тогда .
3 Þ 4. Пусть . Так как , то по свойству де Моргана, свойству ассоциативности, свойству коммутативности и правилам действия с несобственными множествами получим:
. =.
4Þ5. Пусть А\В = , т. е. . Тогда .
По закону де Моргана и свойству двойного отрицания получаем .
5Þ1. Пусть и предположим, что не выполняется условие АВ, т. е. найдется такой элемент х, что хÎ А и xÏ В. Тогда , значит, , а это противоречит равенству , ч. т. д.
Замечание. Пересечение и объединение могут быть определены для любого множества множеств Ai , где индексы i пробегают множество I. По определению
{x| xÎ Ai для всех iÎ I}
(пересечение) - .
{x| xÎ Ai для некоторых iÎ I}
(объединение) -.
Если I={1, 2, …, n}, то используют записи или .