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

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.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, т.е. х Î А È ( В Ç С ), тогда по определению операции объединения, ( х Î А ) или ( х Î В Ç С ).

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 ).

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: