Текст книги "Дискретная математика. Краткий курс. Учебное пособие"

А. А. Казанский
ДИСКРЕТНАЯ МАТЕМАТИКА
Краткий курс
Учебное пособие

[email protected]

Глава 1
ТЕОРИЯ МНОЖЕСТВ

Введение

Понятие множества используется во всех математических дисциплинах. Сама идея о существовании соотношения между величинами различной природы возникла, по-видимому, во времена античности, однако потребовалось много столетий, чтобы это первоначальное представление привело к современному теоретико-множественному понятию отображения, которое каждому элементу одного множества ставит в соответствие элемент другого множества. Античные математики использовали различные таблицы, например астрономические таблицы Птолемея, но эти таблицы понимались как соотношения между конечными дискретными множествами постоянных величин и предназначались только для вычисления числовых значений. В многочисленных трудах греческих математиков, включая и Архимеда, не используется идея функциональной зависимости. Эта идея сформировалась лишь в начале XVII в., когда научились представлять функциональные зависимости с помощью формул. В работах Декарта, Ньютона, Лейбница, Эйлера для записи различных зависимостей стали использовать не громоздкие таблицы, а компактные алгебраические выражения. Эти работы привели к значительным успехам в математике и благодаря им в XVIII в. главным объектом становится не число, а функция.

Понятия, связанные с множествами, введены немецким математиком Дедекиндом в 1871 г. в работе по теории алгебраических чисел и теории полей. Общие принципы множеств, или совокупностей, сформулированы Георгом Кантором в эти же годы, однако его основные работы посвящены свойствам бесконечных множеств. Кантор показал, что свойства бесконечных и конечных множеств значительно различаются.

1.1. Множество и его элементы

Понятие множества не имеет строгого определения. Оно выведено из понятия совокупности, образованной из конечного числа предметов, которые необходимо рассмотреть как единое целое. Например, можно говорить о множестве различных студентов, которых объединяет то, что они учатся в одной учебной группе, или о множестве граждан одной страны, или о множестве всех точек, лежащих на одной прямой. При этом, чтобы выделить эти предметы, необходимо указать свойства, которыми они обладают, а также указать признаки, по которым можно будет отличить предметы одной совокупности от другой. В 1872 г. Кантор определил множество как «объединение в одно целое объектов, хорошо различимых нашей интуицией». В книге Бурбаки «Теория множеств», изданной в 1939 г., имеется такое определение: «множество образуется из элементов, обладающих некоторыми свойствами и находящихся в некоторых отношениях между собой или с элементами других множеств».

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

Множество однозначно задано, если определены его элементы.

Для обозначения множеств обычно используются большие латинские буквы A, B, С, X, Y,…, а элементы обозначаются строчными буквами a, b, с, x, y,… Утверждение «x является элементом A», или «x принадлежит A» записывается как x ∈ A.

Если x не является элементом A, тогда пишут x ∉ A.

Определение. Два множества А и Вравны, если они состоят из одних и тех же элементов.

Запись A = B означает, что множество А равно множеству В, а запись A ≠ B означает, что они не равны. Каждый элемент в одном множестве является элементом только один раз, даже если он и повторяется в записи множества многократно. Элементы одного множества принято заключать в круглые скобки. Например, множество букв {ТЕОРИЯ МНОЖЕСТВ} и множество букв {ВИНЕР МОНЖ СМИТ ЯН} равны, поскольку они задают одно и то же множество букв {В Е Ж И М Н О Р С Т Я}, однако если рассматривать в качестве элементов не буквы а слова, тогда это будет два различных множества. Очень часто в приложениях используются числовые множества, для обозначения которых выделены специальные символы:

N = {1, 2, 3,}, множество натуральных чисел;

Z = {…, – 2, – 1, 0, 1, 2…}, множество целых чисел;

Q = {множество рациональных чисел};

R = {множество вещественных чисел};

С = {множество комплексных чисел}.

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

для любого множества Х и любого свойства Р имеется множество А, такое что элементы А являются элементами Х и обладают свойством Р.

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

Пример 1.1

(а) М = {x: x – нечетное целое число и x > 1}.

Здесь М является множеством, состоящим из положительных целых чисел, которые больше 1 и нечетные.

(в) А = {x: x – гласная буква английского алфавита}.

Здесь, a ∈ A, e ∈ A, но b ∉ A. Нетрудно заметить, что это множество можно задать и перечислением его элементов, т. е. А = {a, e, i, o, u, y}.

(с) Пусть В = {x: x2 + x – 2 = 0 },

C = {–2, 1 }, D = {–2, –2, 1, 1}.

В этом случае все три множества равны, т. е. B = C = D, поскольку множество не зависит ни от того, в каком порядке показаны его элементы, ни от того, сколько раз они повторяются, ни от того, как они получены.

(d) Пусть A = {2, 3, 4, 5}, B = {5, 7, 8}, C = {A, B}.

Множества А и В являются числовыми, а элементами множества С являются уже не числа, а множества, т. е. С является множеством множеств и состоит из двух элементов. Элемент 2 ∉ C, несмотря на то что 2 ∈ A и A ∈ C.

Кроме этого, множество можно задать, определяя каждый его элемент по некоторому уже известному множеству. Например, N = {1, 2, 3, …} – множество натуральных чисел. Определим новое множество, как множество степеней числа 3 {31, 32, 33, …}.

Множество может быть также задано при помощи операций над множествами.

1.2. Универсальное множество и пустое множество

При задании множества в любом приложении теории множеств обычно приходится сталкиваться с вопросом, к какому основному или универсальному множеству принадлежит рассматриваемое множество. Например, когда мы говорим о множестве студентов какой-либо группы, то универсальным множеством может быть как множество всех студентов университета, в котором учатся студенты этой группы, так и множество всех людей на планете. Это определяется целями конкретной задачи. Если надо найти некоторое множество точек на плоскости, то универсальным множеством будет множество всех точек плоскости. Универсальное множество обычно обозначается символом U.

Множество, в котором нет ни одного элемента, называется пустым или несуществующим множеством и обозначается Ø.

Для любого элемента x можно сказать, что пустое множество обладает свойством x ∉ Ø. Пустое множество может возникнуть при задании множества U и некоторого свойства A – такого, что в U нет ни одного элемента со свойством A, например множество М = {x: x – натуральное число, для которого ex < 2x} не имеет ни одного элемента, т. е. является пустым. Имеется только одно пустое множество, и если М и S пустые множества, то М = S, поскольку они состоят из одних и тех же элементов, а именно из никаких элементов.

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}.

Если А = {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}, BC = {4, 5, 6}, CB = {9},

BA = {6, 7, 8}, AD = {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}, BA = {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}].

Пусть теперь В класс подмножеств 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

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

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