Свойства операций над множествами

Свойства операций над множествами

План

1. Ассоциативные, коммутативные и дистрибутивные законы теории множеств.

2. Законы идемпотентности, поглощения, законы де Моргана.

1.Ассоциативные, коммутативные и дистрибутивные законы теории множеств

Для любых подмножеств , , универсального множества имеют место следующие свойства ( здесь понимается как ):

1. 1-а.

2. 2-а.

3. 3-а.

4. 4-а.

5. 5-а.

Законы 1 и 1-а называются ассоциативными законами для объединения и пересечения.

Законы 2 и 2-а называются коммутативными законами; 3 и 3-а – дистрибутивными законами для объединения и пересечения.

Докажем для примера утверждение 3, воспользовавшись для этого способом доказательства, вытекающим из принципа объемности (лекция 1). Для этого:

1. Возьмем и покажем, что этот элемент . Действительно: если , то или . Если , то и , но тогда . Если же , то и , а тогда и , а значит .

2. Возьмем теперь и покажем, что . Действительно, если , то и , следовательно, или же и , т.е. .

Согласно закону 1 объединение множеств можно записывать без скобок: . Полученный вывод можно обобщить: все множества, получаемые при помощи операции объединения из заданных множеств , взятых в фиксированном порядке, равны друг другу. Будем обозначать такое множество: .

Аналогичное утверждение справедливо и для пересечения: .

Общие ассоциативные законы позволяют установить общие коммутативные законы: если - это числа 1,2,…,n, взятые в произвольном порядке, то:

,

.

Аналогичным образом можно сформулировать общие дистрибутивные законы:

.

2.Законы идемпотентности, поглощения, законы де Моргана

Для любых подмножеств , универсального множества имеют место следующие свойства ( здесь понимается как ):

1. Если для любого имеет место 1-а. Если для любого имеет место

равенство: , то . равенство: , то .

2. Если и , то .

3. .

4. . 4-а. .

5. 5-а. .

6. 6-а. .

7. 7-а. .

8. 8-а. .

Законы 5 и 5-а называются законами идемпотентности, 7 и 7-а – законы поглощения, 8 и 8-а – законы де Моргана.

Закон 2 утверждает, что любое множество имеет единственное дополнение.

Докажем для примера закон 8. Для этого:

1. Возьмем произвольный элемент и покажем, что . Действительно, если , то , следовательно, и , а значит и , т.е. .

2. Возьмем произвольный элемент и покажем, что . Действительно, если , то и , следовательно, и , а потому не может принадлежать , т.е. .

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

(І) ;

(ІІ) ;

(ІІІ) .

Вопросы

1. Какие законы объединения и пересечения множеств называются коммутативными, общими коммутативными?

2. Какие законы объединения и пересечения множеств называются ассоциативными, общими ассоциативными?

3. Какие законы объединения и пересечения множеств называются дистрибутивными, общими дистрибутивными?

4. Сформулировать и доказать законы де-Моргана.

5. Доказать законы поглощения.