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

Чтение книги онлайн.

СКАЧАТЬ ⊆ 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, то он СКАЧАТЬ