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

Автор: Александр Анатольевич Казанский
Издательство: Проспект
Серия:
Жанр произведения: Математика
Год издания: 0
isbn: 9785392196043
Скачать книгу
в частности и с множеством С, т. е. x ∈ (BC). В связи с тем, что x входит в множество A и в множество (BC), то он входит и в их пересечение. Если же x ∈ (AC), то тогда xA и xС. Но поскольку xС, то он принадлежит и объединению В с любым другим множеством, т. е. x ∈ (BC). Поскольку и в этом случае x входит в оба множества: и в А и в (BC), то он входит и в их пересечение xA ∩ (BC), поэтому(AB) ∪ (A ∩ ∩ C) ⊆ A ∩ (BC).

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

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

      A ∩ (AB) = A,

      A ∪ (AB) = A.

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

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

      Докажем теперь, что всякий элемент х из множества AC ∪ BC принадлежит и множеству (AB)С. Если xAС, то тогда xA и поэтому х не может принадлежать пересечению xAB. Если xВС, то тогда xВ и поэтому х также не может принадлежать пересечению xAB. В любом из этих случаев xAB и потому x ∈ (AB)С.

      Докажем двойственный закон де Моргана (AB)C= = АC ∩ ВC. Поскольку элемент х принадлежит множеству (AB)C тогда и только тогда, когда он не принадлежит ни множеству А, ни множеству В, то из этого следует,