1.7. Алгебра множеств. Ее формулы, теоремы и законы

В математике алгеброй называют множество объектов с введенными на них операциями.

Определение. Алгеброй множеств называют совокупность множеств и операций над ними — предметных (,  , \, , ) и сравнения ( ,  , = ), а также отрицаний операций сравнения.

В алгебрах выражения над объектами, правильно записанные при помощи введенных операций, называют формулами.

Определение. Формулой алгебры множеств называют любое выражение вида А  В, где А, В — формулы множеств,  — операция сравнения либо ее отрицание.

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

Пример 1. Рассмотрим следующие выражения:

а)  (АВ) =  А В; б) АВ = АВ;

в) АВ  АВ; г) (АВ)  С = (АC)  (BС).

Выражение а) не является формулой алгебры множеств, так как в правой части его стоит выражение, не являющееся формулой множества. Выражения б) и в) — формулы алгебры множеств. Как нетрудно показать на примерах, равенство б) справедливо только в одном случае, когда А = В, в других случаях оно ложно. Поэтому оно не будет теоремой. Нестрогое включение в) и равенство г) выполняются всегда, поэтому они являются теоремами алгебры множеств.

Среди теорем особо выделяют такие, где используется операция сравнения «равенство» ( = ), поскольку такие теоремы задают эквивалентные преобразования формул (не нарушающие их истинности). Наиболее употребительные теоремы с равенствами называют законами алгебры множеств. В качестве законов обычно приводят следующие теоремы:

1. Коммутативные законы — действуют относительно операций объединения и пересечения.

АВ =ВА; АВ =ВА.

2. Ассоциативность (для операций объединения и пересечения).

(АВ)С =А(ВС) =АВС);

(АВ)С =А (ВС) =А ВС.

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

(АВ)С =(АC)(BС);

(АВ)С=(АC)(BС).

4. Идемпотентность.

АА =А ; АА =А.

5. Поглощение.

А(АВ)= АВ; А(АВ) =АВ.

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

 (АВ) =  А В;  (АВ)=  А В.

7. Закон исключения третьего.

 А = А.

8. Операции с пустым и универсальным множествами.

(АU) =U; (А) =A;

(АU) =A; (А) = ;

(U) =; (U) = U;

  =U;  U = .

Рассмотрим проверку правильности рассуждений о множествах, задаваемых формулами алгебры множеств. В общем случае она может быть выполнена с использованием полных диаграмм пересечений, а также с помощью векторов включений.

Пример 2. Проверить справедливость первого закона де Моргана:  (АВ) =  А  В.

Решение. Необходимо выяснить равенство в общем случае составных множеств, заданных формулами F₁ =  (АВ) и F₂ =  А  В. Построим на полных множествах элементарных пересечений векторы включения для F₁ и F₂:

N	А	В	АВ	F1	А	B	F2
0	0	0	0	1	1	1	1
1	0	1	1	0	1	0	0
2	1	0	1	0	0	1	0
3	1	1	1	0	0	0	0

Так как данные векторы совпадают, то составные множества, заданные формулами F₁ и F₂, равны при любых входящих в них множествах А и В. Рассмотренное равенство является теоремой алгебры множеств.

Также строгое доказательство закона можно дать на полной диаграмме пересечений для двух множеств (рис.1.2).

Для доказательства того, что некоторая формула не является теоремой алгебры множеств, достаточно указать хотя бы один случай её нарушения — например, на конкретных множествах или на диаграммах Венна, которые не обязательно должны быть полными диаграммами пересечений.

Пример 3. Будет ли теоремой формула А\В = (АВ)?

Решение. Проверка на диаграмме Венна для произвольных множеств U, A, B (рис. 1.3) показывает, что формула дала неверный результат, следовательно, она не будет теоремой.

Рис.1.3

Замечание Доказанный выше факт не означает, что конкретные составные множества, задаваемые формулами (АВ) и А\В, всегда не равны. Например, в частном случае при A=U равенство выполняется, поскольку А\В= В, (АВ) = В.

ЗАДАЧИ

1. Выразить аналитически в виде формул множества а)—ж) (рис.1.4), указанные на диаграммах Венна штриховкой:

Рис. 1.4.

2. Изобразить, используя полные диаграммы пересечений Венна, множества, заданные формулами:

а) (АВ)  (СВ), б) А  (ВС), в) АВ, г)  ( (А\В)\С), д)  ( А В), е)  ( А \  В), ж)  ( ( АВ)\ С), з)  А  (С В) , и) (АВ)  (В С).

3. Сравнить следующие пары составных множеств, заданные формулами:

а)  (АВ) и А   B, б) (АВ)  (AC) и (BA)  (BC), в) (A\B)  B и  А   B, г) АB и (А\B)  B, д) (AB)\С и (А\(BC))  (В\ (AC)).

4. Проверить (доказать или опровергнуть), будут ли приведенные ниже формулы теоремами алгебры множеств:

а) (AB)   (AВ) = ( АВ), б) А(В\A) =  , в) А\(ВС) = А (ВС), г) (AB) A = A, д) (A B)\С = (А\(BC))  (В\ (AC)), е) A  B  АB , ж) А\(BC)   В, з) АВ  (AB)  C, и) АВ   (ABC).