Александр Казанский - Дискретная математика. Краткий курс. Учебное пособие

Важным при выполнении операций является их приоритет. Сначала выполняется операция дополнения, затем пересечения и затем объединения.

Множества удовлетворяют следующим законам (или тождествам):

Принцип двойственности алгебры множеств

Нетрудно заметить, что тождества в таблице располагаются парами, например первое тождество A ∩ B = B ∩ A имеет парное A ∪ B = B ∪ A, и это выполняется для всех остальных законов алгебры множеств.

Принцип двойственностисостоит в том, что если верно какое-либо тождество, то тождество, полученное из него путем замены каждой из операций ∩, ∪, а также U и Ø на операции ∪, ∩, Ø и U , соответственно, будет также верно. Поэтому у любого тождества есть его «двойник», отличающийся тем, что у него каждая операция замена на парную ей (объединение на пересечение, а пересечение на объединение) и при этом пустое множество заменяется на универсальное, а универсальное на пустое. Принцип двойственности очень важен, поскольку если доказана истинность какого-либо выражения, то истинность двойственного ему можно не доказывать – оно будет истинно вследствие данного принципа. Например, для верного тождества

A = ( A ∩ B C ∩ C C) ∪ ( A ∩ ( B ∪ C ))

двойственное ему будет также верным тождеством

A = ( A ∪ B C ∪ C C) ∩ ( A ∪ ( B ∩ C )).

Или для верного тождества

A = ( A ∩ U ) ∪ ( A ∩ B ∩ C ),

двойственное ему тождество A = ( A ∪ Ø ) ∩ ( A ∪ B ∪ C ).

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

1) элементный метод;

2) диаграммы Венна;

3) табличный метод;

4) алгебраический метод.

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

Докажем далее законы алгебры множеств.

Доказательство коммутативности(или сочетательного свойства) операций объединения и пересечения самоочевидно, поскольку ни в определении пересечения, ни в определении объединения ничего не говорится о порядке подмножеств.

Ассоциативность(или сочетательный закон) также просто доказывается. Покажем, что ( A ∩ B ) ∩ C ⊆ A ∩ ( B ∩ C ). Если x ∈ ( A ∩ B ) ∩ C , то x ∈ ( A ∩ B ) и x ∈ С , из x ∈ ( A ∩ B ) следует, что x ∈ А и x ∈ B , т. е. x принадлежит всем трем множествам A, B и C . Следовательно, x ∈ ( B ∩ C ) и x ∈ A ∩ ( B ∩ C ). Обратное включение показывается аналогично, поскольку множество в правой части тождества также образовано из элементов (и только из таких), которые входят в каждое из множеств A, B и C . Ассоциативность для операции объединения следует из того, что элементы в множестве левой части тождества и элементы в множестве правой части состоят из таких и только таких элементов, которые принадлежат по крайней мере одному из подмножеств A, B и C .

Идемпотентностьозначает, что если x ∈ A ∩ A , то, значит, x принадлежит пересечению множества A с самим собой, т. е. x принадлежит самому множеству A . Если элемент x ∈ A ∪ A , то x принадлежит объединению множества A с самим собой, т. е. и в этом случае он принадлежит только множеству A .

Докажем дистрибутивность пересечения относительно объединения.

A ∩ ( B ∪ C ) = ( A ∩ B ) ∪ ( A ∩ C )

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

A ∩ ( B ∪ C ) ⊆ ( A ∩ B ) ∪ ( A ∩ C ).

Пусть x ∈ A ∩ ( B ∪ C ). Тогда по определению операции пересечения x ∈ A и x ∈ ( B ∪ C ). Если x ∈ B , то тогда x принадлежит и A и B и поэтому он принадлежит и их пересечению x ∈ ( A ∩ B ). Но поскольку x принадлежит объединению B и C , то он может принадлежать не только B , но и С и даже обеим этим множествам. Если x ∈ С , тогда он принадлежит и пересечению А и С , т. е. x ∈ ( A ∩ C ). Но отсюда можно видеть, что в любом из этих случаев x принадлежит к какому-то из множеств: либо ( A ∩ B ), либо (A ∩ C ), и тогда в соответствии с определением операции объединения x принадлежит и объединению этих множеств x ∈ ( A ∩ B ) ∪ ( A ∩ C ) и поэтому A ∩ ( B ∪ C ) ⊆ ( A ∩ B ) ∪ ( A ∩ C ).

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

Пусть x ∈ ( A ∩ B ) ∪ ( A ∩ C ). Если x ∈ ( A ∩ B ), то отсюда x ∈ A и x ∈ В . Но поскольку x ∈ В , то он принадлежит и объединению множества В с любым другим множеством, в частности и с множеством С , т. е. x ∈ ( B ∪ C ). В связи с тем, что x входит в множество A и в множество ( B ∪ C ), то он входит и в их пересечение. Если же x ∈ ( A ∩ C ), то тогда x ∈ A и x ∈ С . Но поскольку x ∈ С , то он принадлежит и объединению В с любым другим множеством, т. е. x ∈ ( B ∪ C ). Поскольку и в этом случае x входит в оба множества: и в А и в ( B ∪ C ), то он входит и в их пересечение x ∈ A ∩ ( B ∪ C ), поэтому( A ∩ B ) ∪ ( A ∩ ∩ C ) ⊆ A ∩ ( B ∪ C ).

Докажем теперь двойственное тождество, т. е. дистрибутивность объединения относительно пересечения A ∪ ( B ∩ C ) = ( A ∪ B ) ∩ ( A ∪ C ). Для этого надо показать, что всякий элемент x множества A ∪ ( B ∩ C ) принадлежит и множеству ( A ∪ B ) ∩ ( A ∪ C ). Если элемент x принадлежит множеству А, то он принадлежит и множеству A ∪ ( B ∩ C ), потому что оно содержит множество А . В то же время если x ∈ A , то он входит и в пересечение ( A ∪ B ) ∩ ( A ∪ C ). Допустим, x не является элементом множества А . Тогда он должен принадлежать пересечению ( B ∩ C ), а также каждому из множеств B и C в отдельности. Тогда по определению операции объединения x ∈ ( A ∪ B ) и x ∈ ( A ∪ С ). Из этого следует, что x принадлежит и пересечению этих множеств ( A ∪ B ) ∩ ( A ∪ C ). И в том и в другом случае x из левого множества входит и в правое. Пусть x принадлежит правому множеству. Тогда если он принадлежит множеству А , то он принадлежит и множеству A ∪ ( B ∩ C ) по определению объединения. Если он не принадлежит А , то тогда он принадлежит и В и С в отдельности, а значит, он принадлежит и пересечению ( B ∩ C ) и поэтому в каждом из этих случаев любой элемент из правого множества входит в левое множество, что и требовалось доказать.