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

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.6.Проверим первый дистрибутивный закон:

АÈ(ВÇС)=(АÈВ)Ç(АÈС) (рис.1.4).

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

АÈ(ВÇС)=(АÈВ)Ç(АÈС).

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

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

(хÎАÈВ) и (хÎАÈС), следовательно х Î (АÈВ)Ç(АÈС), т.е. хÎDr;

b) Если элемент хÎВÇС, то, по определению операции пересечения множеств, (хÎВ) и (хÎС), отсюда, по определению операции объединения, (хÎАÈВ) и (хÎАÈС), следовательно хÎ(АÈВ)Ç(АÈС), т.е. хÎ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)) = АÈÆ = А.

Ý Ý Ý Ý

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

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

Упорядоченные множества

Понятие вектора

Под вектором понимается упорядоченный набор элементов. Определение является не строгим (интуитивным), так же как и определение множества.

Элементы, образующие вектор, называются координатами или компонентами вектора. Число координат вектора называется его длиной или размерностью. Синонимом понятия «вектор» является «кортеж».

Для обозначения вектора обычно используются скобки, например (1, 2, 1, 3). Иногда скобки и даже запятые в обозначении вектора опускаются.

Примером векторов могут служить целые числа, при этом отдельные цифры числа являются координатами этого вектора.

Замечание. В отличие от элементов множеств, некоторые координаты вектора могут совпадать.

Векторы длины два называются упорядоченными парами (или просто парами), длины три – тройками, …, длины n – n-ками и т.д.

Два вектора равны, если они имеют одинаковую длину и соответствующие их координаты равны, т.е.

(а₁, а₂, …, а_m)=(b₁, b₂,…,b_n), если m=n и a₁=b₁, a₂=b₂, …, a_m=b_m.

Векторы (кортежи) образуют особый класс множеств, называемых упорядоченными. В отличии от множеств, элементы которых могут быть перечислены в произвольном порядке, для элементов (координат) вектора существенным является их положение внутри вектора. В связи с этим множества, содержащие одинаковые элементы, но в различном порядке, равны {a, b}={b, a}, а вектора – не равны (a, b) ¹ ( b, a).