Над множествами

Множества. Основные операции

Теория множеств – раздел дискретной математики, в котором изучаются общие свойства множеств. Понятие множества принадлежит к числу фундаментальных неопределяемых математических понятий. Можно сказать, что множество – это любая определенная совокупность объектов. Объекты, из которых образовано множество, называются его элементами. Обычно множества обозначают прописными буквами латинского алфавита, а элементы множеств – строчными буквами. Для задания множеств используются два способа.

Первый способ задания заключается в записи всех элементов множества внутри фигурных скобок через запятые. Например, - множество, состоящее из n элементов

Второй способ состоит в указании общего свойства элементов, из которых образовано множество. Запись читается как “множество всех элементов , для которых верно ”. Например, обозначает множество четных чисел.

Выражение означает то, что элемент принадлежит множеству . Если не является элементом , то .

– пустое множество, т.е. множество, не содержащее ни одного элемента. – универсальное множество или универс, т.е. множество, содержащее все элементы.

Запись (A включено в B) означает, что множество является подмножеством множества , т.е. все элементы множества принадлежат множеству . Пустое множество является подмножеством любого множества.

означает, что множества A и равны, т.е. они состоят из одних и тех же элементов или оба пусты.

(A строго включено в B), если и , т.е. является собственным подмножеством множества .

Для конечного множества мощность – это число элементов в . Для обозначения мощности используется запись . Множества и B равномощны, если между элементами этих множеств существует взаимно-однозначное соответствие.

Теоретико-множественные операции над множествами

— дополнение множества , т.е. все элементы универса, не принадлежащие .

– объединение множеств и , т.е. все элементы универса, принадлежащие или .

– пересечение множеств и , т.е. все элементы универса, принадлежащие и .

– разность между множествами и , т.е. множество всех элементов множества , не принадлежащих множеству .

– симметрическая разность множеств и , т.е. все элементы универса, принадлежащие только множеству или только множеству .

С помощью теоретико-множественных операций над множествами можно строить формулы. Для упрощения записи формул скобки можно опускать, придерживаясь следующего правила: пересечение сильнее всех остальных операций. Знак пересечения в формулах можно опускать. Таким образом, формулу можно записать в виде .

Две формулы алгебры множеств и тождественно равны, если они задают одно и то же множество. Равносильность формул будем называть тождеством и записывать в виде .

Например, формулы и задают одно и то же множество .

Основные тождества алгебры множеств

1. Коммутативные законы:

а) ; б) .

2. Ассоциативные законы:

а) ; б) .

3. Дистрибутивные законы:

а) ; б) .

4. Законы де Моргана:

а) ; б) .

5. Законы поглощения:

а) ; б) .

6. Законы идемпотентности:

а) ; б) .

7. а) ; б) .

8. а) ; б) .

9. а) ; б) .

10. а) ; б) .

11. а) ; б) .

12. .

13. – коммутативность симметрической разности.

14. .

15. .

Множества в силу ассоциативных законов не зависят от порядка расстановки скобок, поэтому их можно записывать без скобок. Введём обозначения:

; .

Имеют место следующие обобщённые тождества:

16. Законы обобщённой дистрибутивности:

а) б) .

17. Законы обобщённой дистрибутивности:

а) ;

б) .

18. Обобщённые законы де Моргана:

а) ; б) .

Операция является двойственной к операции , и наоборот, операция двойственна к операции . Множество двойственно к Ø, а Ø двойственно к .

Если в формуле используются только операции и дополнение, а также множества U и Ø, тогда формула , которая получается из после замены каждого символа на двойственный, т.е. на , на , Ø на , на Ø, называется формулой двойственной к .

Если доказано тождество , то справедливо и двойственное тождество . Для его доказательства достаточно в доказательстве тождества каждый символ заменить на двойственный к нему. В соотношениях 1-11 и 16-18 попарно выписаны тождества и .

Для доказательства тождества достаточно показать, что и .

Лемма 1. .

Лемма 2. .

Лемма 3.

Лемма 4

Установленные выше тождества, а также леммы 1 – 4, позволяют доказывать более сложные утверждения и упрощать сложные условия, накладываемые на множества.

Пример 1. Доказать тождество:

Решение.1 способ. Справедливость утверждения можно проверить, показав, что множество, стоящее по одну сторону от знака равенства, включено в множество, стоящее по другую сторону от этого знака равенства, и наоборот.

(а) Докажем, что Пусть Если и то Значит, Если и то Значит, Показали, что

(б) Пусть теперь Тогда и Отсюда следует, что если то значит, но Если то , значит, но Тогда, и Тождество доказано.

2 способ. Этот способ основан на применении известных тождественных соотношений 1-18. Действительно, используя тождество 15, законы де Моргана 4б и дистрибутивность 3а, получаем в левой части доказываемого равенства:

Затем при помощи соответствующих тождеств приведём правую часть равенства к виду:

Сравнивая полученные выражения в левой и правой частях преобразованного равенства, заключаем, что тождество выполнено.

Пример 2. Упростить следующую систему условий:

Решение. Эти условия по лемме1 равносильны следующим:

Воспользуемся теперь основными тождествами 1-18 и первое условие заменим на более простое.

.

По лемме 3 получившиеся три условия равносильны одному:

Преобразуем левую часть полученного выражения:

Таким образом, система условий равносильна одному условию: . Ответ: .