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

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

Пусть 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 ) и поэтому в каждом из этих случаев любой элемент из правого множества входит в левое множество, что и требовалось доказать.

Докажем законы поглощения.

A ∩ ( A ∪ B ) = A,

A ∪ ( A ∩ B ) = A .

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

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

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

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