Введение в теорию множеств и комбинаторику

Введение в теорию множеств и комбинаторику

2-е издание, исправленное

Князьков В.С.
Волченская Т.В.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Введение в теорию множеств и комбинаторику/ В.С. Князьков, Т.В. Волченская - М.: Национальный
Открытый Университет “ИНТУИТ”, 2016

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

(c) ООО “ИНТУИТ.РУ”, 2008-2016
(c) Князьков В.С., Волченская Т.В., 2008-2016

3

Теория множеств

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

Начальные сведения о множествах

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

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

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

Как правило, элементы множества обозначаются маленькими буквами, а сами
множества - большими. Принадлежность элемента 
 множеству 
 обозначается так:

, где знак 
 является стилизацией первой буквы греческого слова 
 (есть,

быть), знак непринадлежности - 
.

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

 - множество студентов потока 99ПС - конечное множество ;

 - множество звезд во Вселенной - бесконечное множество ;

 - множество студентов потока 98СП, хорошо знающих три иностранных языка

(японский, китайский и французский), видимо, пустое множество.

Множество 
 называют подмножеством множества 
 (обозначается 
 ), если

всякий элемент множества 
 является элементом множества 
: 

 (рис. 1.1).

4

Рис. 1.1. 

При этом говорят, что 
 содержит 
, или 
 покрывает 
. Невключение

подмножества  в множество 
 обозначается так: 
.

Множества 
 и 
 равны ( 
 ) тогда и только тогда, когда 
, и 
, т. е.

элементы множеств 
 и 
 совпадают.

Множество 
 называется собственным подмножеством множества 
, если 
, а 

. Обозначается так: 
.

Например: 
.

Мощностью конечного множества 
 называется число его элементов. Обозначается 

. Например, 
, 
.

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

Семейством множества 
 или булеаном 
 является множество, элементами

которого являются всевозможные подмножества множества 
.

Например,

В общем случае мощность булеана 
.

Универсальным множеством  называется множество всех рассматриваемых в
данной задаче элементов.

Способы задания множеств

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

5

арифметическими операциями, описанием свойств элементов или графическим
представлением.

1. Задание множеств списком предполагает перечисление элементов. Например,

множество  состоит из букв 
 или множество 
 включает

цифры 
.

Пример: 
.

2. Задание множеств порождающей процедурой или арифметическими операциями

означает описание характеристических свойств элементов множества: 

, т. е. множество 
 содержит такие элементы , которые

обладают свойством 
.

Например:

, 
 - множество всех натуральных чисел;

. или 
 ;

.

3. Задание множества описанием свойств элементов: например, 
 - это множество

чисел, являющихся степенями двойки.

К описанию свойств естественно предъявить требования точности и
недвусмысленности. Так, ” множество всех хороших песен 2003 года” каждый
составит по-разному. Надежным способом однозначного задания множества
является использование разрешающей процедуры, которая для любого объекта
устанавливает, обладает ли он данным свойством и соответственно является ли
элементом рассматриваемого множества.

Например, 
 - множество успевающих студентов. Разрешающей процедурой

включения в множество 
 является отсутствие неудовлетворительных оценок в

последней сессии.

4. Графическое задание множеств происходит с помощью диаграмм Эйлера-Венна.

Замкнутая линия-круг Эйлера - ограничивает множество, а рамка - универсальное
пространство 
 (рис. 1.2). Заданы два множества: 
 и 
.

Если элементов множеств немного, то они могут на диаграмме указываться явно.

6

Рис. 1.2. 

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

Рассмотрим такие операции над множествами, как объединение, пересечение,
разность, симметрическая разность и дополнение.

Объединением множеств  и  ( 
 ) называется множество, состоящее из всех

тех элементов, которые принадлежат хотя бы одному из множеств  или . (рис. 1.3).

Рис. 1.3. 

В общем случае операция объединения может быть использована для нескольких
множеств: 
 или 
.

Последнее можно представить в следующем виде:

7

где  - количество объединенных множеств.

Пример. Даны два множества: 
 и 
. Найдем множество

. 
.

Пересечением множеств  и  ( 
 ) называется множество, состоящее из

элементов, входящих как в множество , так и в множество  (рис. 1.4): 

.

Рис. 1.4. 

Операция пересечения так же может быть многоместной: 
 или

где  - количество объединенных множеств 
.

Пример. Даны множества 
 и 
. Найдем их пересечение: 

.

Разностью множеств  и  ( 
 ) называется множество всех элементов

множества , которые не содержатся в  ( рис. 1.5,а ):

 ( рис. 1.5,б ).

8

Рис. 1.5a. 

Рис. 1.5б. 

Пример. Даны два множества  и . Найдем их разность. 
.

Симметричная разность множеств  и , ( 
 ): 

 (рис. 1.6).

9

Рис. 1.6. 

Дополнением (до универсального множества ) множества  называется множество
всех элементов, не принадлежащих , но принадлежащих универсальному множеству
(рис. 1.7).

Рис. 1.7. 

Пример. Пусть универсальное множество  состоит из букв русского алфавита,  -
множество гласных букв, тогда 
 - множество согласных букв и букв ь и ъ.

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

10