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

Пересечение и объединение множеств обладают, коммутативнымсвойством: для любых множествА,Ввыполняются равенства:АВ=ВА;АВ=ВА. Это следует из того, что в определениях пересечения и объединения множеств не фиксируется порядок оперирования множествами. Например, выполняя объединение, можно к элементам одного множества присоединить элементы другого, а можно поступить наоборот: к элементам второго множества присоединить элементы первого.

Разность множеств не обладает коммутативнымсвойством. Это видно из диаграммы:

А\В

В\А

Пересечение и объединение множеств обладают также ассоциативнымсвойством: для любых множествА,ВиСвыполняются равенства:

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

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

АВ

(АВ) С

ВС

А(ВС)

Разность множеств не обладает ассоциативнымсвойством. Это видно из диаграммы:

(А\В)\С

А\(В\С)

Задание: для каких множеств А, В, и С справедливо равенство: (А\В)\С= А\(В\С)?

Однако, на диаграммах можно лишь проиллюстрировать то или иное свойство операций на множествах. Для строгого доказательства этих свойств необходимо рассмотреть все случаи взаимоотношений между множествами. Это не сложно, когда речь идет о двух множествах, но достаточно трудоемко уже для трех.

Рассмотрим аналитическое доказательство свойства ассоциативности одной из операций над множествами, например объединения, т.е. докажем, что для любых множеств А, Ви С справедливо равенство (АВ)С=А(ВС).

Доказательство. Вспомним определение равенства множеств. Чтобы доказать равенство двух множеств, надо убедиться в том, что каждый элемент множества АВ) С содержится в множестве А(ВС), и наоборот каждый элемент множества А(ВС) содержится в множестве АВ) С. Таким образом доказательство будет состоять их двух частей.

1 часть. Пусть х – любой элемент множества (АВ) С, тогда, по определению объединения х принадлежит хотя бы одному из объединяемых множеств, то есть х  (АВ) или хС.

Если х  (АВ), то, по определению объединения, х  А или х В.

Итак, из того что х  (АВ) С следует, что х принадлежит хотя бы одному из множеств А, В или С. Рассмотрим все полученные случаи.

• если х  А, то, по определению объединения, х принадлежит объединению А с любым другим множеством, то есть х  А(ВС).

• если хВ, то, по определению объединения, х принадлежит объединению В с любым другим множеством, то есть х  ВС. Из того что х принадлежит ВС следует что х принадлежит и объединению ВС с любым другим множеством, то есть х  А(ВС).

• если хС, то, по определению объединения, х принадлежит объединению В с любым другим множеством, то есть х  ВС. Из того что х принадлежит ВС следует что х принадлежит и объединению ВС с любым другим множеством, то есть х  А(ВС).

Из доказанного видно, что каждый элемент множества (АВ)С содержится в множестве А(ВС).

2 часть. Пусть х – любой элемент множества А(В С), тогда, по определению объединения х принадлежит хотя бы одному из объединяемых множеств, то есть х  А или хВС.

Если х  (ВС), то, по определению объединения, х  В или хС.

Итак, из того что х  А(В С) следует, что х принадлежит хотя бы одному из множеств А, В или С. Рассмотрим все полученные случаи.

• если хА, то, по определению объединения, х принадлежит объединению А с любым другим множеством, то есть х  АВ. Из того что х принадлежит АВ следует что х принадлежит и объединению АВ с любым другим множеством, то есть х  (АВ)С.

• если хВ, то, по определению объединения, х принадлежит объединению В с любым другим множеством, то есть х  АВ. Из того что х принадлежит АВ следует что х принадлежит и объединению АВ с любым другим множеством, то есть х  (АВ)С.

• если хС, то, по определению объединения, х принадлежит объединению С с любым другим множеством, то есть х(АВ)С.

Из доказанного видно, что каждый элемент множества А(ВС) содержится в множестве (АВ)С. Согласно определению равных множеств заключаем, что (АВ)С=А(ВС).Свойство доказано.

Задание: проведите строгое доказательство ассоциативности операции объединения: (АВ) С=А(ВС)

Взаимосвязь пересечения и объединения и разности множеств отражается в дистрибутивныхсвойствах этих операций:

• (АВ)С=(АВ)(АС) –дистрибутивность пересечения относительно объединения;

• (АВ) С=(АВ)  (АС) –дистрибутивность объединения относительно пересечения;

• (АВ)\С=(А\В)(А\С) –дистрибутивность вычитания относительно объединения;

• (А\В)С=(АВ)\(АС) –дистрибутивность пересечения относительно вычитания.

Заметим, что если в выражении есть знаки пересечения и объединения множеств и нет скобок, то сначала выполняют пересечение, так как считают, что пересечение более «сильная» операция, чем объединение. (Например, умножение чисел более «сильная» операция чем сложение) Таким образом можно записать свойства дистрибутивности сократив количество скобок:

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

Проиллюстрируем свойство дистрибутивности пересечения относительно объединения ((АВ)С=АВАС) на диаграммах:

АВ

(АВ)С

АВ

АС

(АВ)(АС)

Задание: Проиллюстрируйте на диаграммах остальные свойства дистрибутивности.

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

• – дополнение объединения множеств равно пересечению дополнений этих множеств;

• – дополнение пересечения множеств равно объединению дополнений этих множеств.

Докажем первый закон:

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

1. является подмножеством;

2. является подмножеством.

1 часть. Множество является подмножеством множестваесливсеэлементы множестваявляются так же и элементами множества.

Возьмем произвольный элемент хиз множества. Из того чтохследует чтох . Еслих , то это значитх не является элементом ни множества А, ни множества В, то естьх их .

Так как х не является элементом множества А, тохявляется элементом множества.

Так как х не является элементом множества В, тох является элементом множества.

Из того что хи одновременнохследует чтох.

Таким образом любой произвольный элемент хиз множестваявляется также и элементом множества. Следовательно, множествоявляется подмножеством множества, что и требовалось доказать в первой части.

2 часть. Множество является подмножеством множестваесливсеэлементы множестваявляются так же и элементами множества.

Возьмем произвольный элемент хиз множества. Из того чтохследует чтохи одновременнох.

Если хявляется элементом множества, тох не является элементом множества А, то естьх .

Если хявляется элементом множества, тох не является элементом множества В, то естьх .

Из того что х их следует, чтох . А следовательно х является элементом дополнения множества, то естьх

Таким образом любой произвольный элемент хиз множестваявляется также и элементом множества. Следовательно, множествоявляется подмножеством множества, что и требовалось доказать во второй части.

На основании определения равенства множеств заключаем, что.