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

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

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

---

1.3. Подмножества

Выбирая из множества М какие-либо элементы, можно получить новое множество S, которое будет частью множества М или, как еще говорят, подмножеством множества М. Иначе говоря, множество М является подмножеством множества М, если каждый элемент S является также и элементом М. Это отношение записывается так:

S ⊆ M или M ⊇ S,

что иногда читают, как Sсодержится в М или МсодержитS.

Обычно принято считать, что часть «меньше» целого, однако в теории множеств это не так, поскольку каждое множество является подмножеством самого себя, т. е. M ⊆ M. Это свойство называют рефлексивностью.

Пример 1.2

(а) Рассмотрим множества:

Х = {1, 2, 3, 4, 7, 8}, Y = {2, 3, 8, 9}, Z = {2, 8}.

Здесь Z ⊆ X и Z ⊆ Y, но Y не является подмножеством Х, поскольку имеет элемент 9, которого нет в множестве Х. Кроме того, поскольку эти множества определяют одну и ту же задачу, то все они должны принадлежать к универсальному множеству U и это множество U должно содержать по крайней мере следующие элементы {1, 2, 3, 4, 7, 8, 9}.

(в) Пусть N, Z, Q, R – множества, о которых упоминалось выше. Тогда

N ⊆ Z ⊆ Q ⊆ R.

(с) Каждое множество Х является подмножеством универсального множества U, поэтому по определению все элементы Х принадлежат U. Пустое множество Ø также является подмножеством Х.

(d) Если каждый элемент А принадлежит множеству В, а каждый элемент В принадлежит множеству С, тогда каждый элемент А принадлежит С, т. е. если A ⊆ B и B ⊆ C, тогда A ⊆ C.

(e) Если A ⊆ B и B ⊆ A, тогда А и В имеют те же самые элементы и А = В. Обратно, если А = В, тогда A ⊆ B и B ⊆ A, так как каждое множество является подмножеством самого себя.

Формально последние три примера можно записать следующим образом:

1) для любого множества А всегда Ø ⊆ A ⊆ U;

2) для любого множества А выполняется A ⊆ A;

3) если A ⊆ B и B ⊆ C, тогда A ⊆ C;

4) A = B, только если A ⊆ B и B ⊆ A.

Если A ⊆ B и A = B, то A называют несобственным подмножествомB. Когда A ⊆ B и A≠B, т. е. в B содержится по крайней мере один элемент, которого нет в A, то A называют собственным подмножествомB и пишут A ⊂ B. Пусть, например,

A ={1, 2}, B = {1, 2, 3, 4, 5}, C = {5, 4, 3, 2, 1}.

Здесь A и B являются подмножествами C, но A – собственное подмножество, а B – несобственное подмножество C.

1.4. Диаграммы Венна

Диаграмма Венна позволяет получить визуальное представление множеств в виде замкнутых областей на плоскости. Универсальное множество представляется внутренними точками прямоугольника, а другие множества представляются точками кругов (или каких-либо других областей, ограниченных замкнутыми кривыми), лежащих внутри этого прямоугольника. Фактически эти множества являются подмножествами универсального множества и поэтому между ними может существовать взаимосвязь в том смысле, что они имеют общие элементы. Например, для двух множеств A и B возможны три случая взаимосвязи по отношению включения. Если эти множества не имеют общих элементов, т. е. множества не пересекаются, тогда диск, представляющий A, будет отделен от диска, представляющего B, как на рис. 1.1(а). Если A ⊂ B, т. е. все элементы A являются также и элементами B, тогда диск, представляющий A, будет полностью лежать внутри диска для B, как на рис 1.1(b) (в случае, когда A ⊆ B и A = B, диск, представляющий A, будет совпадать с диском для B).

Третий случай взаимосвязи множеств A и B показан на рис. 1.1(с), при этом:

– некоторые элементы имеются в A, но их нет в B;

– есть элементы B, которых нет в А;

– есть элементы, которые принадлежат и A и B одновременно;

– есть элементы, которых нет ни в A, ни в B.

Рис. 1.1

Выводы диаграммы Венна

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

Следовательно, диаграммы Венна можно использовать для проверки правильности выводов.

Пример 1.3

Показать, что следующий аргумент правильный:

A: Компьютеры, которые установлены на кафедре программирования, имеют LCD-дисплеи.

B: Компьютеры университета, которые используются в учебном процессе, соединены с Интернетом.

C: Ни один компьютер кафедры программирования не соединен с Интернетом.

D: Все компьютеры, которые используются в учебном процессе, не имеют LCD-дисплеев.

Здесь утверждения А, В и С означают посылки, а утверждение D ниже линии означает заключение. Вывод правильный, если заключение D логически следует из утверждений А, В и С.

Из утверждения А компьютеры с LCD-дисплеями входят в множество компьютеров университета, а из утверждения С следует, что множество компьютеров кафедры программирования и множество компьютеров, которые соединены с Интернетом, не пересекаются.

Из утверждения В следует, что компьютеры, которые используются в учебном процессе, образуют подмножество компьютеров, которые соединены с Интернетом, как это показано на рис. 1.2.

Рис. 1.2

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

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

1.5. Операции над множествами

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

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

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

A ∪ B = { x: x ∈ A или x ∈ B }.

Здесь союз «или» используется в смысле и/или. На рис. 1.3 объединение A ∪ B представлено на диаграммах Венна заштрихованной областью. Если А и В непустые множества и А не совпадает с В, то возможны три различные диаграммы для объединения.

Рис. 1.3

Пример 1.4

Пусть А = {1, 2, 3, 4, 5 }, B = {1, 3, 7, 8,}, A ∪ B = = {1, 2, 3, 4, 5, 7, 9}.

Этот случай показан на рис. 1.3(а), множества имеют общие элементы {1, 3}.

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