- •Элементы дискретной математики
- •1. Начальные понятия и модели
- •1.1. Множества
- •1.1.1. Понятие множества
- •1.1.2. Представление множеств
- •1.1.3. Операции над множествами
- •1. Объединение множеств
- •2. Пересечение множеств
- •3. Разность множеств
- •5. Степень множества
- •1.1.4. Мощность множеств
- •Определение
- •Определение
- •Упражнение. Показать, что если a равномощно b, а b равномощно c, то a равномощно c.
- •Теорема 1.1
- •Доказательство
- •Упражнение
- •Теорема 1.3
- •1.2.1. Основные понятия
- •1.2.2. Произведение отображений
- •1.3. Логика доказуемости и истинности
- •1.3.1. Высказывания
- •1.3.2. Парадоксы
- •Квантор существования
- •Квантор всеобщности
- •1.3.4. Доказуемость и выводимость
- •1.3.5. Структура утверждений и доказательств
1.1.3. Операции над множествами
Пусть A и B некоторые множества. Над этими множествами могут выполняться следующие основные операции.
1. Объединение множеств
Объединением множеств A и B называется множество C, определяемое соотношением: {x | x A или x B}, т.е. в объединение двух множеств входят те и только те элементы, которые содержатся хотя бы в одном из объединяемых множеств. Для обозначения операции пересечения используется специальный символ , а объединение множеств A и B записывается как A B.
Диаграмма Венна для объединения множеств имеет вид:
A A B
A B
2. Пересечение множеств
Пересечением множеств A и B называется множество {x | x A и x B}, т.е. в пересечение двух множеств A и B входят только такие элементы, которые содержатся в обоих множествах. Для обозначения операции пересечения используется специальный символ , а пересечение множеств A и B записывается как A B.
Соответствующая диаграмма Венна имеет вид:
A B
A B
3. Разность множеств
Разностью множеств A и B называется множество:
{x | x A и x B}, т.е. в разность множеств A и B входят только те элементы A, которые не содержатся в B. Для обозначения операции разности множеств используется специальный символ \, а разность множеств A и B записывается как A \ B.
Диаграмма Венна для разности множеств A и B имеет вид:
A B
A \ B
В определенных случаях приходится рассматривать все возможные элементы или объекты, которые не содержатся в некотором множестве A. Для такой ситуации разность между Универсумом U и данным множеством A называется дополнением множества A. Дополнение A обозначается как .
4. Произведение множеств
Произведением множеств A и B называется множество {(x, y) | x A и y B}, т.е. A B состоит из всевозможных пар элементов, в которых первая компонента является элементом A, а вторая элементом B. Для обозначения операции произведения множеств используется специальный символ , а произведение A и B обозначается как A B.
Операцию произведения множеств можно продемонстрировать на примере произведения двух подмножеств множества вещественных чисел, представляемых отрезками на числовой оси.
B
A
Здесь множества A и B представлены отрезками числовых осей. Тогда произведение этих множеств это множество точек плоскости, образующее прямоугольник, проекции которого на оси совпадают с отрезками, представляющими A и B.
Заметим, что если R это множество всех вещественных чисел, то R R или R2 представляет собой множество всех пар вещественных чисел. Это множество принято отождествлять с двумерной координатной плоскостью.
Аналогично, R3 обозначает множество троек вещественных чисел. Это множество отождествляется с множеством точек в трехмерном пространстве.