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

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

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

---

Пусть теперь В класс подмножеств S, который содержит элемент а и два других элемента из S. Тогда

В = {{a, b, c}, {a, b, d}, {a, c, d}]. Элементами В являются множества {a, b, c}, {a, b, d} и {a, c, d}]. Поэтому В является подклассом класса А.

Для данного множества S можно говорить о классе всех подмножеств S. Этот класс называют степенным множествомS и обозначают 2S. Если n(S) – число элементов множества S, то число элементов степенного множества n(2S) представляет собой степень 2 и равно n(2S) = 2 n(S). Например, если S = {a, b, c}, то степенное множество

2S = [Ø,{a}, {b}, {c}, {a, b},{a, c}, {b, c}, S].

Заметим, что пустое множество Ø принадлежит к 2S, так как пустое множество является подмножеством S и само S принадлежит 2S, поэтому число элементов n(2S) = 23 = 8.

Рассмотрим теперь еще одно важное понятие, которое называется разбиением множества S. Разбиением множества S называется семейство {Аi} непустых подмножеств S, для которых:

1) каждый элемент х из S принадлежит к одному из подмножеств Аi;

2) подмножества из {Аi} взаимно не пересекаются, т. е. если

Аi≠ Аj, тогда Аi ∩ Аj = Ø.

Подмножества в разбиении иногда называют клетками или блоками. На рис. 1.8 представлена диаграмма Венна, изображающая разбиение прямоугольного множества точек S на пять клеток А1, А2, А3, А4, А5.

Рис. 1.8

Фундаментальные произведения также представляют собой разбиение универсального множества.

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

1.8. Алгебра множеств и двойственность

Абстрактная алгебра занимается изучением операций, производимых над некоторыми элементами. К настоящему времени идеи абстрактной алгебры используются не только для математических методов, но и позволяют получать практические результаты. Операции объединения, пересечения и дополнения, производимые над множествами, удовлетворят определенным законам (или тождествам) и образуют алгебру множеств. Поскольку числовая алгебра появилась раньше, то возникает вопрос, какая из операций (пересечение или объединение) «похожа» на операцию сложения чисел и какая – на операцию умножения. Ответить на этот вопрос едва ли возможно. Для чисел, например, выполняется только дистрибутивность умножения относительно сложения, а в алгебре множеств рассматривают два закона дистрибутивности: пересечения относительно объединения и объединения относительно пересечения.

Важным при выполнении операций является их приоритет. Сначала выполняется операция дополнения, затем пересечения и затем объединения.

Множества удовлетворяют следующим законам (или тождествам):

Принцип двойственности алгебры множеств

Нетрудно заметить, что тождества в таблице располагаются парами, например первое тождество A ∩ B = B ∩ A имеет парное A ∪ B = B ∪ A, и это выполняется для всех остальных законов алгебры множеств.

Принцип двойственности состоит в том, что если верно какое-либо тождество, то тождество, полученное из него путем замены каждой из операций ∩, ∪, а также U и Ø на операции ∪, ∩, Ø и U, соответственно, будет также верно. Поэтому у любого тождества есть его «двойник», отличающийся тем, что у него каждая операция замена на парную ей (объединение на пересечение, а пересечение на объединение) и при этом пустое множество заменяется на универсальное, а универсальное на пустое. Принцип двойственности очень важен, поскольку если доказана истинность какого-либо выражения, то истинность двойственного ему можно не доказывать – оно будет истинно вследствие данного принципа. Например, для верного тождества

A = (A ∩ BC ∩ CC) ∪ (A ∩ (B ∪ C))

двойственное ему будет также верным тождеством

A = (A ∪ BC ∪ CC) ∩ (A ∪ (B ∩ C)).

Или для верного тождества

A = (A ∩ U) ∪ (A ∩ B ∩ C),

двойственное ему тождество A = (A ∪ Ø) ∩ (A ∪ B ∪ C).

1.9. Доказательство тождеств с множествами

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

1) элементный метод;

2) диаграммы Венна;

3) табличный метод;

4) алгебраический метод.

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

Докажем далее законы алгебры множеств.

Доказательство коммутативности (или сочетательного свойства) операций объединения и пересечения самоочевидно, поскольку ни в определении пересечения, ни в определении объединения ничего не говорится о порядке подмножеств.

Ассоциативность (или сочетательный закон) также просто доказывается. Покажем, что (A ∩ B) ∩ C ⊆ 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).