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

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.

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

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

Пример 1.6. Проверим первый дистрибутивный закон:

А(ВС)=(АВ)(АС) (рис.1.4).

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

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

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

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

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

Пример 1.7. Докажем первый дистрибутивный закон:

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

Обозначим левую часть тождества А(ВС) через 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, т.е. х А(ВС), тогда по определению операции объединения, (хА) или (хВС).

   1. Если элемент хА, то, по определению операции объединения множеств,

(хАВ) и (хАС), следовательно х  (АВ)(АС), т.е. хDr;

2. Если элемент хВС, то, по определению операции пересечения множеств, (хВ) и (хС), отсюда, по определению операции объединения, (хАВ) и (хАС), следовательно х(АВ)(АС), т.е. хD_r;.

Так как для любого хD_l следует, что хD_r, то, по определению отношения включения, D_lD_r.

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

Таким образом, между множествами D_l и D_r существуют отношение взаимного включения, значит D_l=D_r, что и требовалось доказать.

Пример 1.8. Докажем первый закон двойственности:

Обозначим D_l= и D_r=  _.

1. Пусть элемент xD_l , т.е. x . Тогда xU и (x АВ), значит x А и х В (тонкий момент в доказательстве: х не принадлежит ни А, ни В), следовательно х и х , т.е. х  . Значит D_l  D_r.

2. Пусть теперь элемент хD_r , т.е. х  . Тогда (х ) и (х ), значит xU и x одновременно не принадлежит ни А, ни В, т.е. х (А или В), следовательно х АВ, т.е. х  . Из этого следует, что D_r  D_l.

Таким образом, между множествами D_l и D_r существуют отношение взаимного включения, значит D_l=D_r, что и требовалось доказать.

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

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

правой частей

тождества совпадают, значит

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

Пример 1.9. Докажем второй закон поглощения: А(АВ)=А путем преобразования левой части тождества к правой с использованием других тождеств:

А(АВ) = (А)(АВ) = (А(B)) = А = А.

   

свойство пустого по дистрибутивному свойства пустого

множества закону множества