Глава 1. Элементы теории множеств

Множества

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

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

Определение 1 . Объединением двух множеств называется новое множество...
Определение 2

Определение 2 . Пересечением двух множеств называется новое множество...
Определение 3

Определение 3 . Разностью двух множеств называется новое множество Если класс объектов, на которых определяются различные множества обозначить ( Универсум ), то дополнением множества называют разн...
Декартово произведение множеств

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

Определение 4 . Декартовым (прямым) произведением множеств называется множество упорядоченных n-ок (наборов, кортежей) вида...
Определение 5

Определение 5 . Степенью декартового произведения называется число множеств n, входящих в это декартово произведение. Замечание . Если все множества одинаковы, то используют обозначение ....
Определение 6

Определение 6 . Подмножество декартового произведения множеств называется отношением степени n ( n-арным отношением )....
Определение 7

Определение 7 . Мощность множества кортежей, входящих в отношение , называют мощностью отношения . Замечание . Понятие отношения является очень важным не только с математической точки зрения. Поня...
Примеры отношений Бинарные отношения (отношения степени 2)

Бинарные отношения (отношения степени 2) В математике большую роль играют бинарные отношения, т.е. отношения, заданные на декартовом произведении двух множеств ....
Определение 8

Определение 8 . Отношение на множестве называется отношением эквивалентности , если оно обладает следующими свойствами: для всех (рефлексивность) Если , то (симметричность) Если и , то (транзитивн...
Пример 1

Пример 1 . Рассмотрим на множестве вещественных чисел отношение, заданное просто равенством чисел. Предикат такого отношения: , или просто Условия 1-3, очевидно, выполняются, поэтому данное отноше...
Пример 2

Пример 2 . Рассмотрим более сложное отношение эквивалентности. На множестве целых чисел зададим отношение "равенство по модулю n" следующим образом: два числа и равны по модулю n , если их остатки...
Определение 9

Определение 9 . Отношение на множестве называется отношением порядка , если оно обладает следующими свойствами: для всех (рефлексивность) Если и , то (антисимметричность) Если и , то (...
Пример 3

Пример 3 . Простым примером отношения порядка является отношение, задаваемое обычным неравенством на множестве вещественных чисел . Заметим, что для любых чисел и выполняется либо , либо , т.е. лю...
Пример 4

Пример 4 . Рассмотрим на множестве всех сотрудников некоторого предприятия отношение, задаваемое следующим образом: сотрудник предшествует сотруднику тогда и только тогда, когда выполняется одно и...
Определение 10

Определение 10 . Отношение на декартовом произведении двух множеств называется функциональным отношением , если оно обладает следующим свойством: Если и , то (однозначность функции). Обычно, функц...
Пример 5

Пример 5 . Пусть множество есть следующее множество молодых людей: {Вовочка, Петя, Маша, Лена}, причем известны следующие факты: Вовочка любит Вовочку (эгоист). Петя любит Машу (взаимно). Маша люб...
Таблица 1

Таблица 1 Кого Кто Вовочка Петя Маша Лена Вовочка Любит Петя Любит Маша Любит Любит Лена Любит Таблица 1. Матрица взаимоотношений Способ 4. При помощи таблицы фактов:...
Таблица 2

Таблица 2 Кто любит Кого любят Вовочка Вовочка Петя Маша Маша Петя Маша Маша Лена Петя Таблица 2 Таблица фактов С точки зрения реляционных баз данных наиболее предпочтительным является четвертый с...
n-арные отношения (отношения степени n)

n-арные отношения (отношения степени n) В математике n-арные отношения рассматриваются относительно редко, в отличие от баз данных, где наиболее важными являются именно отношения, заданные на дека...
Пример 6

Пример 6 . В некотором университете на математическом факультете учатся студенты Иванов, Петров и Сидоров. Лекции им читают преподаватели Пушников, Цыганов и Шарипов, причем известны следующие фак...
Таблица 3

Таблица 3 A (Преподаватель) B (Предмет) Q (Количество часов) Пушников Алгебра 40 Пушников Базы данных 80 Цыганов Геометрия 50 Шарипов Алгебра 40 Шарипов Геометрия 50 Таблица 3 Отношение "Читает ле...
Таблица 4

Таблица 4 C (студент) B (предмет) A (Преподаватель) Иванов Алгебра Шарипов Иванов Базы данных Пушников Петров Алгебра Пушников Петров Геометрия Цыганов Сидоров Геометрия Цыганов Сидоров Базы данны...
Транзитивное замыкание отношений

Транзитивное замыкание отношений Введем понятие транзитивного замыкания , связанное с бинарными отношениями, которое понадобится в дальнейшем....
Определение 11.

Определение 11. Пусть отношение задано на декартовом квадрате некоторого множества . Транзитивным замыканием отношения называется новое отношение , состоящее из кортежей , для которых выполняется:...
Пример 7

Пример 7 . Пусть множество представляет собой следующее множество деталей и конструкций: = {Болт, Гайка, Двигатель, Автомобиль, Колесо, Ось} причем некоторые из деталей и конструкций могут использ...
Таблица 5

Таблица 5 Конструкция Где используется Болт Двигатель Болт Колесо Гайка Двигатель Гайка Колесо Двигатель Автомобиль Колесо Автомобиль Ось Колесо Таблица 5 Отношение R Транзитивное замыкание состои...
Таблица 6

Таблица 6 Конструкция Где используется Болт Двигатель Болт Колесо Гайка Двигатель Гайка Колесо Двигатель Автомобиль Колесо Автомобиль Ось Колесо Болт Автомобиль Гайка Автомобиль Ось Автомобиль...
Выводы

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