К. И. Костенко

Элементы дискретной математики

1. Начальные понятия и модели

1.1. Множества

1.1.1. Понятие множества

Множеством называется всякая совокупность объектов.

При этом, как правило, можно указать общее свойство, которым обладают или которым характеризуются элементы, входящие во множество. Например, множество писателей, книги которых имеются в продаже в некотором магазине. Элементами данного множества являются люди, характеризующиеся общим свойством: авторы книг, продаваемых в данном магазине.

Множествами можно также считать следующие совокупности:

1. всех рек, впадающих в Черное море;

2. видов птиц, гнездящихся на данной территории;

3. сортов картофеля, районированных в некотором регионе;

4. студентов первого курса факультета прикладной математики.

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

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

Пусть элемент a входит в некоторое множество A. Данный факт будем записывать с помощью выражения: a A. Здесь  специальный символ принадлежности элемента множеству, а запись a A понимается как "a является элементом множества A" или "элемент a принадлежит множеству A".

Если объект a не содержится во множестве A, то запись этого факта имеет вид: a A.

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

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

1.1.2. Представление множеств

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

1. Непосредственное задание

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

Например, множество областных и краевых центров юга России можно задать как {АСТРАХАНЬ, ВОЛГОГРАД, КРАСНОДАР, РОСТОВ, СТАВРОПОЛЬ}.

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

Например, множество всех целых неотрицательных чисел можно задать как: N = {0, 1, 2, ... }. Множество всех четных натуральных чисел может быть записано {0, 2, 4, ... }, где многоточие понимается как слова " и так далее ".

2.Задание множества указанием характеристического

свойства

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

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

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

Например. Множество всех пар людей, знакомых между собой, может быть задано так: {(x, y) | x знает y}  это множество пар людей, первый из которых знает второго.

Множество {2n | n N}  это множество всех четных натуральных чисел.

3. Задание множества указанием его имени

Например. Множество A, список № 5 или 5-й класс А средней школы № 1.

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

4. Задание множеств с помощью диаграмм Венна

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

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

Например, диаграммы Венна для произвольных двух и трех множеств имеют вид:

A A C

B B

Множество B называется подмножеством множества A, если каждый элемент множества B является элементом множества A.

Если B является подмножеством A, то в этом случае говорят о включении B в A и используют символическое обозначение B A, где  символ включения множеств. Пусть B A и дополнительно известно, что A не содержится в B. В этом случае говорят, что множество B строго включено во множество A. Для обозначения строгого включения множеств используют специальный символ .

Заметим, что для любого множества A справедливо включение: A.

Множества называются равными, если они состоят из одних и тех же элементов. Очевидно, что множества A и B являются равными тогда и только тогда, когда A B и B A.