Контрольная работа на тему Свойства бинарных отношений
Работа добавлена на сайт bukvasha.net: 2014-11-20Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
от 25%
договор
Введение
1. Рефлексивность:2. Слабая рефлексивность:
3. Сильная рефлексивность:
4. Антирефлексивность:
5. Слабая антирефлексивность:
6. Сильная антирефлексивность:
7. Симметричность:
8. Антисимметричность:
9. Асимметричность:
10. Сильная линейность:
11. Слабая линейность:
12. Транзитивность:
Рефлексивность, свойство бинарных (двуместных, двучленных) отношений, выражающее выполнимость их для пар объектов с совпадающими членами (так сказать, между объектом и его "зеркальным отражением"): отношение R называется рефлексивным, если для любого объекта х из области его определения выполняется xRx. Типичные и наиболее важные примеры рефлексивных отношений: отношения типа равенства (тождества, эквивалентности, подобия и т.п.: любой предмет равен самому себе) и отношения нестрогого порядка (любой предмет не меньше и не больше самого себя). Интуитивные представления о "равенстве" (эквивалентности, подобии и т.п.), очевидным образом наделяющие его свойствами симметричности и транзитивности, "вынуждают" и свойство Р., поскольку последнее свойство следует из первых двух. Поэтому многие употребительные в математике отношения, по определению Р. не обладающие, оказывается естественным доопределить таким образом, чтобы они становились рефлексивными, например, считать, что каждая прямая или плоскость параллельна самой себе, и т.п.
Глава 1. Элементы теории множеств
1.1 Множества
Наиболее простая структура данных, используемая в математике, имеет место в случае, когда между отдельными изолированными данными отсутствуют какие-либо взаимосвязи. Совокупность таких данных представляет собой множество. Понятие множества является неопределяемым понятием. Множество не обладает внутренней структурой. Множество можно представить себе как совокупность элементов, обладающих некоторым общим свойством. Для того чтобы некоторую совокупность элементов можно было назвать множеством, необходимо, чтобы выполнялись следующие условия:Должно существовать правило, позволяющее определить, принадлежит ли указанный элемент данной совокупности.
Должно существовать правило, позволяющее отличать элементы друг от друга. (Это, в частности, означает, что множество не может содержать двух одинаковых элементов).
Множества обычно обозначаются заглавными латинскими буквами. Если элемент
Если каждый элемент множества
Подмножество
Используя понятие множества можно построить более сложные и содержательные объекты.
1.2 Операции над множествами
Основными операциями над множествами являются объединение, пересечение и разность.Определение 1. Объединением двух множеств называется новое множество
Определение 2. Пересечением двух множеств называется новое множество
Определение 3. Разностью двух множеств называется новое множество
Если класс объектов, на которых определяются различные множества обозначить
1.3 Декартово произведение множеств
Одним из способов конструирования новых объектов из уже имеющихся множеств является декартово произведение множеств.Пусть
Определение 4. Декартовым (прямым) произведением множеств
Определение 5. Степенью декартового произведения
Замечание. Если все множества
1.4 Отношение
Определение 6. ПодмножествоОпределение 7. Мощность множества кортежей, входящих в отношение
Замечание. Понятие отношения является очень важным не только с математической точки зрения. Понятие отношения фактически лежит в основе всей реляционной теории баз данных. Как будет показано ниже, отношения являются математическим аналогом таблиц. Сам термин "реляционное представление данных", впервые введенный Коддом [43], происходит от термина relation, понимаемом именно в смысле этого определения.
Т. к. любое множество можно рассматривать как декартовое произведение степени 1, то любое подмножество, как и любое множество, можно считать отношением степени 1. Это не очень интересный пример, свидетельствующий лишь о том, что термины "отношение степени 1" и "подмножество" являются синонимами. Нетривиальность понятия отношения проявляется, когда степень отношения больше 1. Ключевыми здесь являются два момента:
Во-первых, все элементы отношения есть однотипные кортежи. Однотипность кортежей позволяет считать их аналогами строк в простой таблице, т.е. в такой таблице, в которой все строки состоят из одинакового числа ячеек и в соответствующих ячейках содержатся одинаковые типы данных. Например, отношение, состоящее из трех следующих кортежей { (1, "Иванов", 1000), (2, "Петров", 2000), (3, "Сидоров", 3000) } можно считать таблицей, содержащей данные о сотрудниках и их зарплатах. Такая таблица будет иметь три строки и три колонки, причем в каждой колонке содержатся данные одного типа.
В противоположность этому рассмотрим множество { (1), (1,2), (1, 2,3) }, состоящее из разнотипных числовых кортежей. Это множество не является отношением ни в
но такая трактовка ничего нового, по сравнению с понятием подмножества, не дает.
Во-вторых. За исключением крайнего случая, когда отношение есть само декартово произведение
Действительно, каждому отношению можно поставить в соответствие некоторое логическое выражение
Если это не вызывает путаницы, удобно и отношение, и его предикат обозначать одной и той же буквой. Например, отношение
2. Примеры отношений
2.1 Бинарные отношения (отношения степени 2)
В математике большую роль играют бинарные отношения, т.е. отношения, заданные на декартовом произведении двух множеств2.1.1 Отношение эквивалентности
Определение 8. ОтношениеЕсли
Если
Обычно отношение эквивалентности обозначают знаком
Если
Если
Легко доказывается, что если на множестве
Пример 1. Рассмотрим на множестве вещественных чисел
Условия 1-3, очевидно, выполняются, поэтому данное отношение является отношением эквивалентности. Каждый класс эквивалентности этого отношения состоит из одного числа.
Пример 2. Рассмотрим более сложное отношение эквивалентности. На множестве целых чисел
Условия 1-3 легко проверяются, поэтому равенство по модулю является отношением эквивалентности. Предикат этого отношения имеет вид:
Классы эквивалентности этого отношения состоят из чисел, дающих при делении на n одинаковые остатки. Таких классов ровно n:
[0] = {0, n, 2n, …}
[1] = {1, n+1, 2n+1, …}
…
[n-1] = {n-1, n+n-1, 2n+n-1, …}
2.1.2 Отношения порядка
Определение 9. ОтношениеЕсли
Если
Обычно отношение порядка обозначают знаком
Если
Если
Пример 3. Простым примером отношения порядка является отношение, задаваемое обычным неравенством
Предикат данного отношения есть просто утверждение
Пример 4. Рассмотрим на множестве
Назовем такое отношение "быть начальником". Легко проверить, что отношение "быть начальником" является отношением порядка. Заметим, что в отличие от предыдущего примера, существуют такие пары сотрудников
2.1.3 Функциональное отношение
Определение 10. ОтношениеЕсли
Обычно, функциональное отношение обозначают в виде функциональной зависимости -
Предикат функционального отношения есть просто выражение функциональной зависимости
2.1.4 Еще пример бинарного отношения
Пример 5. Пусть множествоВовочка любит Вовочку (эгоист).
Петя любит Машу (взаимно).
Маша любит Петю (взаимно).
Маша любит Машу (себя не забывает).
Лена любит Петю (несчастная любовь).
Информацию о взаимоотношения данных молодых людей можно описать бинарным отношением "любить", заданном на множестве
Способ 1. Перечисление фактов в виде произвольного текста (как это сделано выше).
Способ 2. В виде графа взаимоотношений:
Рисунок 1 Граф взаимоотношений
Способ 3. При помощи матрицы взаимоотношений:
Таблица 1. Матрица взаимоотношений
Кого Кто | Вовочка | Петя | Маша | Лена |
Вовочка | Любит | | | |
Петя | | | Любит | |
Маша | | Любит | Любит | |
Лена | | Любит | | |
Таблица 2 Таблица фактов
Кто любит | Кого любят |
Вовочка | Вовочка |
Петя | Маша |
Маша | Петя |
Маша | Маша |
Лена | Петя |
Что касается предиката данного отношения, то он имеет следующий вид (дизъюнктивная нормальная форма):
R (x,y) = { (x = "Вовочка" AND y = "Вовочка") OR (x = "Петя" AND y = "Маша") OR (x = "Маша" AND y = "Петя") OR (x = "Маша" AND y = "Маша") OR (x = "Лена" AND y = "Петя") }
Замечание. Приведенное отношение не является ни транзитивным, ни симметричным или антисимметричным, ни рефлексивным, поэтому оно не является ни отношением эквивалентности, ни отношением порядка, ни каким-либо другим разумным отношением.
Замечание. Большая часть мировой литературы существует и имеет смысл лишь постольку, поскольку бинарное отношение "любить" не является отношением эквивалентности. В частности, по этой причине человечество не разбивается на классы эквивалентности взаимно любящих особей. Изучением характеристик данного отношения и соответствующего ему предиката занималось (и продолжает заниматься) большое количество экспертов, таких как Толстой Л.Н., Шекспир В. и др.
2.2 n-арные отношения (отношения степени n)
В математике n-арные отношения рассматриваются относительно редко, в отличие от баз данных, где наиболее важными являются именно отношения, заданные на декартовом произведении более чем двух множеств.Пример 6. В некотором университете на математическом факультете учатся студенты Иванов, Петров и Сидоров. Лекции им читают преподаватели Пушников, Цыганов и Шарипов, причем известны следующие факты:
Пушников читает лекции по алгебре и базам данных, соответственно, 40 и 80 часов в семестр.
Цыганов читает лекции по геометрии, 50 часов в семестр.
Шарипов читает лекции по алгебре и геометрии, соответственно, 40 и 50 часов в семестр.
Студент Иванов посещает лекции по алгебре у Шарипова и по базам данных у Пушникова.
Студент Петров посещает лекции по алгебре у Пушникова и по геометрии у Цыганова.
Студент Сидоров посещает лекции по геометрии у Цыганова и по базам данных у Пушникова.
Для того чтобы формально описать данную ситуацию (например, в целях разработки информационной системы, учитывающей данные о ходе учебного процесса), введем три множества:
Множество преподавателей
Множество предметов
Множество студентов
Имеющиеся факты можно разделить на две группы.1 группа (факты 1-3) - факты о преподавателях, 2 группа (факты 4-6) - факты о студентах.
Для того чтобы отразить факты 1-3 (характеризующие преподавателей и читаемые ими лекции), введем отношение на декартовом произведении , где - множество рациональных чисел. А именно, упорядоченная тройка тогда и только тогда, когда преподаватель читает лекции по предмету в количестве часов в семестр. Назовем такое отношение "Читает лекции по…". Множество кортежей, образующих отношение удобно представить в виде таблицы:
Таблица 3 Отношение "Читает лекции по…"
Для того чтобы отразить факты 4-6 (характеризующие посещение студентами лекций), введем отношение на декартовом произведении . Упорядоченная тройка тогда и только тогда, когда студент посещает лекции по предмету у преподавателя . Назовем это отношение "Посещать лекции". Его также представим в виде таблицы:
Таблица 4 Отношение "Посещать лекции"
Рассмотрим отношение подробнее. Оно задано на декартовом произведении . Это произведение, содержащее 3*3*3=27 кортежей, можно назвать "Студенты-Лекции-Преподаватели". Множество представляет собой совокупность всех возможных вариантов посещения студентами лекций. Отношение же показывает текущее состояние учебного процесса. Очевидно, что отношение является изменяемым во времени отношением.
Итак, факты о ходе учебного процесса удалось отразить в виде двух отношений третьей степени (3-арных), а сами отношения изобразить в виде таблиц с тремя колонками.
Удобство использования табличной формы для задания отношения определяется в данном случае следующими факторами:
Все используемые множества конечны.
При добавлении или удалении студентов, предметов, преподавателей просто добавляются или удаляются соответствующие строки в таблице.
Нас сейчас не интересует вопрос, хороши ли полученные отношения. Заметим пока только, что, как показывают следующие замечания, не любую строку можно добавить в таблицу "Посещать лекции".
Замечание. В таблицу "Посещать лекции" нельзя добавить две одинаковые строки, т.к таблица изображает отношение , а в отношении (как и в любом множестве) не может быть двух одинаковых элементов. Это пример синтаксического ограничения - такое ограничение задано в определении понятия отношение (одинаковых строк не может быть ни в одной таблице, задающей отношение).
Замечание. В таблицу "Посещать лекции" нельзя добавить кортеж (Иванов, Геометрия, Пушников). Действительно, из таблицы "Читает лекции по…", представляющей отношение , следует, что Пушников не читает предмет "Геометрия". Оказалось, что таблицы связаны друг с другом, и существенным образом! Это пример семантического ограничения - такое ограничение является следствием нашей трактовки данных, хранящихся в отношении (следствием понимания смысла данных).
Определение 11. Пусть отношение задано на декартовом квадрате некоторого множества . Транзитивным замыканием отношения называется новое отношение , состоящее из кортежей , для которых выполняется:
либо кортеж ,
либо найдется конечная последовательность элементов , такая, что все кортежи принадлежат отношению .
Очевидно, что .
Пример 7. Пусть множество представляет собой следующее множество деталей и конструкций:
= {Болт, Гайка, Двигатель, Автомобиль, Колесо, Ось}
причем некоторые из деталей и конструкций могут использоваться при сборке других конструкций. Взаимосвязь деталей описывается отношением ("непосредственно используется в") и состоит из следующих кортежей:
Таблица 5 Отношение R
Транзитивное замыкание состоит из кортежей (добавленные кортежи помечены серым цветом):
Таблица 6 Транзитивное замыкание отношения R
Очевидный смысл замыкания состоит в описании включения деталей друг в друга не только непосредственно, а через использование их в промежуточных деталях, например, болт используется в автомобиле, т.к он используется в двигателе, а двигатель используется в автомобиле.
Новые множества можно строить при помощи понятия декартового произведения (конечно, есть и другие способы, но они нас в данный момент не интересуют). Декартово произведение нескольких множеств - это множество кортежей, построенный из элементов этих множеств.
Отношение - это подмножество декартового произведения множеств. Отношения состоят из однотипных кортежей. Каждое отношение имеет предикат отношения и каждый n-местный предикат задает n-арное отношение.
Отношение является математическим аналогом понятия "таблица".
Отношения обладают степенью и мощностью. Степень отношения - это количество элементов в каждом кортеже отношения (аналог количества столбцов в таблице). Мощность отношения - это мощность множества кортежей отношения (аналог количества строк в таблице).
В математике чаще всего используют бинарные отношения (отношения степени 2). В теории баз данных основными являются отношения степени . В математике, как правило, отношения заданы на бесконечных множествах и имеют бесконечную мощность. В базах данных напротив, мощности отношений конечны (число хранимых строк в таблицах всегда конечно).
Таблица 3 Отношение "Читает лекции по…"
A (Преподаватель) | B (Предмет) | Q (Количество часов) |
Пушников | Алгебра | 40 |
Пушников | Базы данных | 80 |
Цыганов | Геометрия | 50 |
Шарипов | Алгебра | 40 |
Шарипов | Геометрия | 50 |
Таблица 4 Отношение "Посещать лекции"
C (студент) | B (предмет) | A (Преподаватель) |
Иванов | Алгебра | Шарипов |
Иванов | Базы данных | Пушников |
Петров | Алгебра | Пушников |
Петров | Геометрия | Цыганов |
Сидоров | Геометрия | Цыганов |
Сидоров | Базы данных | Пушников |
Итак, факты о ходе учебного процесса удалось отразить в виде двух отношений третьей степени (3-арных), а сами отношения изобразить в виде таблиц с тремя колонками.
Удобство использования табличной формы для задания отношения определяется в данном случае следующими факторами:
Все используемые множества конечны.
При добавлении или удалении студентов, предметов, преподавателей просто добавляются или удаляются соответствующие строки в таблице.
Нас сейчас не интересует вопрос, хороши ли полученные отношения. Заметим пока только, что, как показывают следующие замечания, не любую строку можно добавить в таблицу "Посещать лекции".
Замечание. В таблицу "Посещать лекции" нельзя добавить две одинаковые строки, т.к таблица изображает отношение
Замечание. В таблицу "Посещать лекции" нельзя добавить кортеж (Иванов, Геометрия, Пушников). Действительно, из таблицы "Читает лекции по…", представляющей отношение
3. Транзитивное замыкание отношений
Введем понятие транзитивного замыкания, связанное с бинарными отношениями, которое понадобится в дальнейшем.Определение 11. Пусть отношение
либо кортеж
либо найдется конечная последовательность элементов
Очевидно, что
Пример 7. Пусть множество
причем некоторые из деталей и конструкций могут использоваться при сборке других конструкций. Взаимосвязь деталей описывается отношением
Таблица 5 Отношение R
Конструкция | Где используется |
Болт | Двигатель |
Болт | Колесо |
Гайка | Двигатель |
Гайка | Колесо |
Двигатель | Автомобиль |
Колесо | Автомобиль |
Ось | Колесо |
Таблица 6 Транзитивное замыкание отношения R
Конструкция | Где используется |
Болт | Двигатель |
Болт | Колесо |
Гайка | Двигатель |
Гайка | Колесо |
Двигатель | Автомобиль |
Колесо | Автомобиль |
Ось | Колесо |
Болт | Автомобиль |
Гайка | Автомобиль |
Ось | Автомобиль |
Выводы
Множество - это неопределяемое понятие, представляющее некоторую совокупность данных. Элементы множества можно отличать друг от друга, а также определять, принадлежит ли данный элемент данному множеству. Над множествами можно выполнять операции объединения, пересечения, разности и дополнения.Новые множества можно строить при помощи понятия декартового произведения (конечно, есть и другие способы, но они нас в данный момент не интересуют). Декартово произведение нескольких множеств - это множество кортежей, построенный из элементов этих множеств.
Отношение - это подмножество декартового произведения множеств. Отношения состоят из однотипных кортежей. Каждое отношение имеет предикат отношения и каждый n-местный предикат задает n-арное отношение.
Отношение является математическим аналогом понятия "таблица".
Отношения обладают степенью и мощностью. Степень отношения - это количество элементов в каждом кортеже отношения (аналог количества столбцов в таблице). Мощность отношения - это мощность множества кортежей отношения (аналог количества строк в таблице).
В математике чаще всего используют бинарные отношения (отношения степени 2). В теории баз данных основными являются отношения степени