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

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

В пособии изложены основные разделы современной дискретной математики. Рассматриваются вопросы, связанные с теорией множеств, теорией отношений, теорией графов и логикой. Материал построен на основе курса лекций, читаемого автором в технических вузах. В каждой главе рассмотрено большое число задач с подробными решениями и примерами, что позволяет эффективно и быстро осваивать изучаемую тему. Для студентов, обучающихся по специальности «Прикладная математика», а также для студентов технических и экономических факультетов, изучающих курс «Дискретная математика» и компьютерные технологии. Представляет интерес для тех, кто связан с использованием методов дискретной математики.

---

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

Пусть 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)С = 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 тогда и только тогда, когда он не принадлежит ни множеству А, ни множеству В, то из этого следует, что он должен входить и в множество А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С и т. д. Чтобы по диаграмме Венна проверить ассоциативность пересечения, можно использовать следующую идею. Заменим множества A, B и С и их пересечения на соответствующие им множества из областей разбиения на этой диаграмме. Множество А заменяется на {4, 5, 6, 7}, В – на {2, 3, 6, 7} и С – на {1, 3, 5, 7}, A ∩ B – на {6, 7}, B ∩ C – на {3, 7}.

Рис. 1.10

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