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

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

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

---

Если А = {1, 2, 3, 4, 5}, B = {7, 8, 9}, то здесь множества А и В не имеют общих элементов, как показано на рис. 1.3(b), A ∪ B = {1, 2, 3, 4, 5, 7, 8, 9}.

Если А = {1, 2, 3, 4, 5, 6,}, B = {1, 2, 3}, A ∪ B = {1, 2, 3, 4, 5, 6}, то в этом случае B ⊂ A,т. е. A ∪ B = A, как на рис. 1.3(с).

Операция пересечения множеств

Пересечением двух множеств А и В (обозначается A ∩ B) называется множество элементов, которые принадлежат и А, и В, т. е.

A ∩ B = { x: x ∈ A и x ∈ B}.

Пересечение представлено на диаграммах Венна заштрихованной областью (рис. 1.4). Здесь, как и в случае с операцией объединения, также имеется три случая.

Если А ={1, 2, 3, 4, 5}, B = {2, 3, 6, 7, 8}, A ∩ B ={2, 3}, рис. 1.4(a).

Если A ={1, 2, 3, 4}, B ={6, 7, 8, 9 }, A ∩ B = Ø, т. е.множества А и В не пересекаются, рис. 1.4(b).

Если А ={1, 2, 3, 4, 5, 6}, B ={4, 5, 6}, A ∩ B = B = {4, 5, 6}, рис. 1.4(с).

Рис. 1.4

Теорема 1.1. Следующие соотношения эквивалентны:

A ⊂ B, A ∩ B = A, и A ∪ B = B.

Следует заметить, что вопрос о том, является ли А собственным или несобственным подмножеством В, в общем, не существен, и поэтому можно записать теорему следующим образом:

A ⊆ B, A ∩ B =A, и A ∪ B = B.

Операция дополнения множеств

Если все множества рассматриваются в некоторое определенное время и являются подмножествами фиксированного универсального множества U, тогда можно определить универсальное дополнение, или просто дополнение множества А, обозначается Ас, как множество элементов, которые принадлежат U, но не принадлежат А, т. е.

Aс ={x: x ∈ U, x ∉ A}.

В некоторых текстах дополнение A обозначается как A’ или Ᾱ. На рис. 1.5(а) дополнение Ас показано заштрихованной областью.

Операция разности множеств

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

А\В = { x: x ∈ A, x ∉ B}.

Иногда множество А\В читается как «А минус В» и обозначается А – В. На рис. 1.5(b) разность А\В заштрихована.

Рис. 1.5

Нетрудно заметить, что для любых двух множеств А и В выполняется тождество А\В =А ∩ Вс.

Пример 1.5

Пусть универсальное множество U = N = {1, 2, 3, 4,…} является множеством натуральных чисел и пусть

А = {1, 2, 3, 4, 5}, B = {4, 5, 6, 7, 8}, C = {7, 8, 9},

и пусть D = {1, 3, 5, 7, 9,…}, множество нечетных чисел. Тогда дополнения

Ас = {6, 7, 8, 9,…}, Bc = {1, 2, 3, 9, 10, 11,…}, Cc = {1, 2, 3, 4, 5, 6, 10, 11,…},

и разности множеств

А\В = {1, 2, 3}, А\C = {1, 2, 3, 4, 5}, B\C = {4, 5, 6}, C\B = {9},

B\A = {6, 7, 8}, A\D = {2, 4}, Dc = {2, 4, 6, 8, 10,…}, множество четных чисел.

Симметрическая разность множеств

Симметрической разностью множеств А и В (обозначается A

 B) называется множество, которое состоит из элементов либо А, либо B, но не входящих в оба эти множества одновременно. Иначе говоря, это объединение этих множеств, из которого удалено их пересечение:

A

B = (A ∪ B)\(A ∩ B).

Можно также показать, что

A

B = (А\В) ∪ (В\А).

Например, пусть А = (1, 2, 3, 4, 5, 6}, B = {4, 5, 6, 7, 8}. Тогда

А\В = {1, 2, 3}, B\A = {7, 8} и тогда A

B = {1, 2, 3, 7, 8}.

На рис. 1.6 на диаграмме Венна множество A

B заштриховано.

A

B заштриховано

Рис. 1.6

1.6. Фундаментальное произведение множеств

Операции над множествами позволяют образовывать из исходных множеств новые множества. При этом операция пересечения множеств применяется для различных практических задач, таких как классификация каких-либо объектов, анализ различного рода социологических опросов или исследований, анализ данных, из которых необходимо выбрать данные, характеризуемые заданными свойствами. Рассмотрим следующий пример. Пусть имеется список студентов группы, успешно решивших первую задачу контрольной работы (обозначим множество их фамилий как А). Пусть также имеется список всех тех, кто успешно решил вторую задачу (множество В), и всех тех, кто решил третью (множество С). Если теперь потребуются сведения о тех, кто успешно решил и первую и вторую задачи одновременно, то необходимо будет выбрать тех, кто входит одновременно и в первый и во второй списки. Для этого надо найти новое множество, являющееся пересечением исходных множеств А и В, т. е. найти множество А ∩ B. Однако это множество не содержит информации о том, решили или нет данные студенты третью задачу. Ясно, что для этого потребуется найти еще одно множество, являющееся пересечением всех трех множеств, т. е. множество А ∩ В ∩ С.

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

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

Пусть имеется n различных множеств А1, А2,А3, …, Аn. Фундаментальным произведением множеств называется множество вида

где Аi* – это либо Аi, либо Аic. Заметим также, что:

1) имеется точно 2n таких фундаментальных произведений;

2) любые два таких фундаментальных произведения не пересекаются;

3) универсальное множество является объединением всех таких фундаментальных произведений.

Рассмотрим пример из трех множеств А, В и С и дадим геометрическую интерпретацию их фундаментальных произведений (рис. 1.7):

А = {1, 2, 3, 6, 7},

B = {3, 4, 5, 6},

C = {5, 6, 7, 8}.

Имеется ровно восемь фундаментальных произведений из трех множеств:

P0 = Ac ∩ Bc ∩ Cc = {9}

P1 = Ac ∩ Bc ∩ C = {8}

P2 = Ac ∩ B ∩ Cc = {4}

P3 = Ac ∩ B ∩ C = {5}

P4 = A ∩ Bc ∩ Cc = {1, 2}

P5 = A ∩ Bc ∩ C = {7}

P6 = A ∩ B ∩ Cc = {3}

P7 = A ∩ B ∩ C = {6}

Рис. 1.7

1.7. Классы множеств, степенные множества и разбиения

Для данного множества S можно рассматривать множество всех его подмножеств. При этом придется рассматривать множество, элементами которого будут также множества, т. е. множество множеств. Чтобы избегать путаницы, часто бывает более удобно говорить о классе множеств или о семействе множеств. Если необходимо рассмотреть множества из данного класса, то можно говорить о подклассе или подсемействе. Например, рассмотрим множество S = {a, b, c, d}. Пусть А класс подмножеств S из трех элементов. Тогда

А = [{a, b, c}, {a, b, d}, {a, c, d}, {d, c, d}].

Элементами класса А являются множества {a, b, c}, {a, b, d}, {a, c, d} и {b, c, d}].