Множества
Множества Наиболее простая структура данных, используемая в математике, имеет место в случае, когда между отдельными изолированными данными отсутствуют какие-либо взаимосвязи. Совокупность таких д... Операции над множествами
Операции над множествами Основными операциями над множествами являются объединение , пересечение и разность .... Определение 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 Конструкция Где используется Болт Двигатель Болт Колесо Гайка Двигатель Гайка Колесо Двигатель Автомобиль Колесо Автомобиль Ось Колесо Болт Автомобиль Гайка Автомобиль Ось Автомобиль... Выводы
Выводы Множество - это неопределяемое понятие, представляющее некоторую совокупность данных. Элементы множества можно отличать друг от друга, а также определять, принадлежит ли данный элемент данн...