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

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

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

---

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

[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. Подмножества