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

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

СКАЧАТЬ ∩ 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 тогда и только тогда, когда он не принадлежит ни множеству А, ни множеству В, то из этого следует, что он должен входить и в множество АC, и в множество ВC, т. е. в их пересечение АC ∩ ВC. С другой стороны, если х входит в пересечение АC ∩ ВC, то он не может входить ни в А, ни в В, потому что в пересечении дополнений множеств ни могут находиться элементы самих этих множеств. Но тогда х входит в дополнение к их объединению, т. е. x ∈ (A ∪ B)С, что и требовалось доказать.

      Доказательство закона инволюции (AC)C = A следует из того факта, что любой элемент из U принадлежит либо А, либо AC. Поэтому когда берется дополнение к множеству А, то получается множество АС, а когда берется дополнение к АС, то снова получается множество А.

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

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

      Докажем, например, закон де Моргана (A ∩ B)С = AC ∪ BC. На рис. 1.9 представлены три случая: (а) когда А и В не пересекаются, (b) когда А включается в В и (с) когда в пересечение входят элементы и из А, и из В (имеется и случай, когда В включается в А, но он аналогичен случаю (b)). На рис. 1.9 (d), (e) и (f) показаны их дополнения. Далее на (а1), (b1) и (с1) показаны множества (AC ∪ BC) для каждого из этих случаев. Можно видеть, что на каждом рисунке области для множества (A ∩ B)С и множества (AC ∪ BC) одинаковые во всех трех случаях и поэтому эти множества равны.

      Рис. 1.9

      Рассмотрим табличный метод доказательства равенства множеств. Докажем ассоциативность пересечения (A ∩ B) ∩ C = A ∩ (B ∩ C). Пусть имеется диаграмма Венна для трех множеств A, B и С из универсального множества U на рис. 1.10. Три овальные области представляют собой множества A, B и С. Прямоугольная область определяет множество U, и она разбита на восемь областей, которые помечены цифрами от 0 до 7. Можно видеть, что область разбиения 7 определяет множество A ∩ B ∩ C, область 6 – множество A ∩ B ∩ CС и т. д. Чтобы по диаграмме Венна проверить ассоциативность пересечения, можно использовать следующую идею. Заменим множества СКАЧАТЬ