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

1). Коммутативные (переместительные) законы: AB= BA; AB= BA.

2). Ассоциативные (сочетательные) законы: 

A  (BC)=(AB)  C; A  (BC)=(AB)  C.

3). Дистрибутивные (распределительные) законы:

A(B  C) = (AB) (AC); A  (BC) = (AB)  (AC).

Замечание. Эти законы выражают дистрибутивность объединения относительно пересечения (для первого) или дистрибутивность пересечения относительно объединения (для второго) слева. Операции объединения и пересечения обладают также свойством дистрибутивности справа:

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

4). Законы тавтологии (идемпотентности): AA= A; AA= A.

5). Законы двойственности (де Моргана):

Следствия из законов двойственности:

6). Законы поглощения: А (АВ)=А; А(АВ)=А.

7). Закон инволютивности: .

8) Закон противоречия: А =.

9) Закон «третьего не дано» (исключенного третьего): А =U.

10) Свойства универсального множества: АU=U; АU=А.

11) Свойства пустого множества: А=А; А=.

Дополнительные тождества для операций объединения, пересечения и дополнения множеств:

12) Законы склеивания:

13) Законы сокращения (законы Порецкого):

Следствия из законов сокращения:

14) Дополнительные тождества (законы) для операции разности (относительного дополнения) множеств: A\(B\C)=(A\B)  (AC); (A\B)\C=(A\C)\(B\C);

A\(BC)=(A\B)\C; A\(BC)=(A\C)\(B\C).

15) Дополнительные тождества (законы) для операции симметрической разности:

AΔ(BΔC)=(AΔB) ΔC; A(BΔC)=(AB) Δ(AC).

Замечание. Практически все основные тождества (законы) множеств представлены парами, которые характеризуются своей симметричностью в отношении операций объединения и пересечения. Подобное свойство законов называется дуальностью (двойственностью). С учетом этого свойства можно выразить один закон пары из другого путем замены операции объединения на операцию пересечения и наоборот. Это относится к законам 1-6. Что касается законов 8-11, то их также можно представить парами, но в отличии от законов 1-6 один закон пары получается из другого не только заменой операций, но и стандартных множеств (универсума и пустого) на противоположное.

Кроме того, свойством дуальности обладают также законы 12 и 13.

О гастес де Морган, (1806-1871) шотландский математик и логик.

Порецкий Платон Сергеевич (1846 -1907) русский математик, астроном и логик.

Способы доказательства тождеств

Убедиться в справедливости тождеств можно с помощью диаграмм Эйлера-Венна. Для этого необходимо изобразить на диаграммах левую и правую части тождеств и сравнить их. Такой способ доказательства принято называть геометрическим. Этот способ является наглядным, но не обладает достаточной строгостью.

Пример 6. Проверим первый дистрибутивный закон: А(ВС)=(АВ)(АС) (рис.4).

Диаграммы левой и правой частей тождества совпадают,

значит оно справедливо.

ВС А(ВС)

АВ АС (АВ)(АС)

Рис. 4. Проверка дистрибутивного закона на диаграммах Эйлера-Венна

Пример 7. Проверим справедливость правила де Моргана на диаграммах Эйлера-Венна (рис. 5).

Диаграммы левой и правой

частей тождества совпадают,

значит оно справедливо.

АВ



Рис. 5. Проверка правила де Моргана на диаграммах Эйлера-Венна

Доказательство справедливости проверяемых тождеств можно проводить одним из двух методов:

• методом взаимного включения;

• алгебраическим методом.

Метод взаимного включения базируется на определении равенства двух множеств, между которыми существует отношение взаимного включения: А=В АВ и ВА.

Пример 8. Докажем первый дистрибутивный закон: А(ВС)=(АВ)(АС).

Обозначим левую часть тождества А(ВС) через D_l, а правую – (АВ)(АС) через D_r.

В соответствии с принятым методом доказательство разделяется на две части:

1) берется произвольный элемент множества D_l (хD_l) и доказывается, что он принадлежит также и множеству D_r, откуда следует: D_lD_r;

2) берется произвольный элемент множества D_r и доказывается, что он принадлежит также и множеству D_l, откуда следует: D_r D_l.

1. Пусть элемент х D_l, т.е. х А(ВС), тогда по определению операции объединения (хА) или (хВС).