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

в частности и с множеством С, т. е. 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)С = AC ∪ BC покажем сначала, что левое множество включается в правое (A ∩ B) С ⊆ AC ∪ BC. Пусть x∈(A ∩ B)С. Тогда x ∉ A ∩ B. Из этого следует, что х не входит в оба множества одновременно, т. е. он не входит либо в А, либо в В. Если он не входит в А, то тогда он входит в АС, а если он не входит в В, то тогда он входит в ВС. Отсюда следует, что х ∈ AC ∪ BC и поэтому (A ∩ B) С ⊆ AC ∪ BC.

      Докажем теперь, что всякий элемент х из множества AC ∪ BC принадлежит и множеству (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 тогда и только тогда, когда он не принадлежит ни множеству А, ни множеству В, то из этого следует,