Xreferat.com » Рефераты по математике » Свойства бинарных отношений

Сколько стоит написать твою работу?

Работа уже оценивается. Ответ придет письмом на почту и смс на телефон.

?Для уточнения нюансов.
Мы не рассылаем рекламу и спам.
Нажимая на кнопку, вы даёте согласие на обработку персональных данных и соглашаетесь с политикой конфиденциальности

Спасибо, вам отправлено письмо. Проверьте почту .

Если в течение 5 минут не придет письмо, возможно, допущена ошибка в адресе.
В таком случае, пожалуйста, повторите заявку.

Спасибо, вам отправлено письмо. Проверьте почту .

Если в течение 5 минут не придет письмо, пожалуйста, повторите заявку.
Хотите промокод на скидку 15%?
Успешно!
Отправить на другой номер
?Сообщите промокод во время разговора с менеджером.
Промокод можно применить один раз при первом заказе.
Тип работы промокода - "дипломная работа".

Свойства бинарных отношений

Введение


1. Рефлексивность:


Свойства бинарных отношений


2. Слабая рефлексивность:


Свойства бинарных отношений


3. Сильная рефлексивность:


Свойства бинарных отношений


4. Антирефлексивность:


Свойства бинарных отношений


5. Слабая антирефлексивность:


Свойства бинарных отношений


6. Сильная антирефлексивность:


Свойства бинарных отношений


7. Симметричность:


Свойства бинарных отношений


8. Антисимметричность:


Свойства бинарных отношений


9. Асимметричность:


Свойства бинарных отношений


10. Сильная линейность:


Свойства бинарных отношений


11. Слабая линейность:


Свойства бинарных отношений


12. Транзитивность:


Свойства бинарных отношений


Рефлексивность, свойство бинарных (двуместных, двучленных) отношений, выражающее выполнимость их для пар объектов с совпадающими членами (так сказать, между объектом и его "зеркальным отражением"): отношение R называется рефлексивным, если для любого объекта х из области его определения выполняется xRx. Типичные и наиболее важные примеры рефлексивных отношений: отношения типа равенства (тождества, эквивалентности, подобия и т.п.: любой предмет равен самому себе) и отношения нестрогого порядка (любой предмет не меньше и не больше самого себя). Интуитивные представления о "равенстве" (эквивалентности, подобии и т.п.), очевидным образом наделяющие его свойствами симметричности и транзитивности, "вынуждают" и свойство Р., поскольку последнее свойство следует из первых двух. Поэтому многие употребительные в математике отношения, по определению Р. не обладающие, оказывается естественным доопределить таким образом, чтобы они становились рефлексивными, например, считать, что каждая прямая или плоскость параллельна самой себе, и т.п.

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


1.1 Множества


Наиболее простая структура данных, используемая в математике, имеет место в случае, когда между отдельными изолированными данными отсутствуют какие-либо взаимосвязи. Совокупность таких данных представляет собой множество. Понятие множества является неопределяемым понятием. Множество не обладает внутренней структурой. Множество можно представить себе как совокупность элементов, обладающих некоторым общим свойством. Для того чтобы некоторую совокупность элементов можно было назвать множеством, необходимо, чтобы выполнялись следующие условия:

Должно существовать правило, позволяющее определить, принадлежит ли указанный элемент данной совокупности.

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

Множества обычно обозначаются заглавными латинскими буквами. Если элемент Свойства бинарных отношенийпринадлежит множеству Свойства бинарных отношений, то это обозначается:


Свойства бинарных отношений


Если каждый элемент множества Свойства бинарных отношенийявляется также и элементом множества Свойства бинарных отношений, то говорят, что множество Свойства бинарных отношенийявляется подмножеством множества Свойства бинарных отношений:


Свойства бинарных отношений

Подмножество Свойства бинарных отношениймножества Свойства бинарных отношенийназывается собственным подмножеством, если


Свойства бинарных отношений


Используя понятие множества можно построить более сложные и содержательные объекты.


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


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

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


Свойства бинарных отношений


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


Свойства бинарных отношений


Определение 3. Разностью двух множеств называется новое множество


Свойства бинарных отношений


Если класс объектов, на которых определяются различные множества обозначить Свойства бинарных отношений (Универсум), то дополнением множества Свойства бинарных отношенийназывают разность


Свойства бинарных отношений

1.3 Декартово произведение множеств


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

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

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


Свойства бинарных отношений


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

Замечание. Если все множества Свойства бинарных отношенийодинаковы, то используют обозначение


Свойства бинарных отношений.


1.4 Отношение


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

Определение 7. Мощность множества кортежей, входящих в отношение Свойства бинарных отношений, называют мощностью отношения Свойства бинарных отношений.

Замечание. Понятие отношения является очень важным не только с математической точки зрения. Понятие отношения фактически лежит в основе всей реляционной теории баз данных. Как будет показано ниже, отношения являются математическим аналогом таблиц. Сам термин "реляционное представление данных", впервые введенный Коддом [43], происходит от термина relation, понимаемом именно в смысле этого определения.

Т. к. любое множество можно рассматривать как декартовое произведение степени 1, то любое подмножество, как и любое множество, можно считать отношением степени 1. Это не очень интересный пример, свидетельствующий лишь о том, что термины "отношение степени 1" и "подмножество" являются синонимами. Нетривиальность понятия отношения проявляется, когда степень отношения больше 1. Ключевыми здесь являются два момента:

Во-первых, все элементы отношения есть однотипные кортежи. Однотипность кортежей позволяет считать их аналогами строк в простой таблице, т.е. в такой таблице, в которой все строки состоят из одинакового числа ячеек и в соответствующих ячейках содержатся одинаковые типы данных. Например, отношение, состоящее из трех следующих кортежей { (1, "Иванов", 1000), (2, "Петров", 2000), (3, "Сидоров", 3000) } можно считать таблицей, содержащей данные о сотрудниках и их зарплатах. Такая таблица будет иметь три строки и три колонки, причем в каждой колонке содержатся данные одного типа.

В противоположность этому рассмотрим множество { (1), (1,2), (1, 2,3) }, состоящее из разнотипных числовых кортежей. Это множество не является отношением ни в Свойства бинарных отношений, ни в Свойства бинарных отношений, ни в Свойства бинарных отношений. Из кортежей, входящих в это множество нельзя составить простую таблицу. Правда, можно считать это множество отношением степени 1 на множестве всех возможных числовых кортежей всех возможных степеней

Свойства бинарных отношений,


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

Во-вторых. За исключением крайнего случая, когда отношение есть само декартово произведение Свойства бинарных отношений, отношение включает в себя не все возможные кортежи из декартового произведения. Это значит, что для каждого отношения имеется критерий, позволяющий определить, какие кортежи входят в отношение, а какие - нет. Этот критерий, по существу, определяет для нас смысл (семантику) отношения.

Действительно, каждому отношению можно поставить в соответствие некоторое логическое выражение Свойства бинарных отношений, зависящее от n параметров (n-местный предикат) и определяющее, будет ли кортеж Свойства бинарных отношенийпринадлежать отношению Свойства бинарных отношений. Это логическое выражение называют предикатом отношения Свойства бинарных отношений. Более точно, кортеж Свойства бинарных отношенийпринадлежит отношению Свойства бинарных отношенийтогда и только тогда, когда предикат этого отношения Свойства бинарных отношенийпринимает значение "истина". В свою очередь, каждый n-местный предикат задает некоторое n-арное отношение. Таким образом, существует взаимно однозначное соответствие между n-арными отношениями и n-местными предикатами.

Если это не вызывает путаницы, удобно и отношение, и его предикат обозначать одной и той же буквой. Например, отношение Свойства бинарных отношенийимеет предикат Свойства бинарных отношений.

2. Примеры отношений


2.1 Бинарные отношения (отношения степени 2)


В математике большую роль играют бинарные отношения, т.е. отношения, заданные на декартовом произведении двух множеств Свойства бинарных отношений.


2.1.1 Отношение эквивалентности

Определение 8. Отношение Свойства бинарных отношенийна множестве Свойства бинарных отношенийназывается отношением эквивалентности, если оно обладает следующими свойствами:

Свойства бинарных отношенийдля всех Свойства бинарных отношений (рефлексивность)

Если Свойства бинарных отношений, то Свойства бинарных отношений (симметричность)

Если Свойства бинарных отношенийи Свойства бинарных отношений, то Свойства бинарных отношений (транзитивность)

Обычно отношение эквивалентности обозначают знаком Свойства бинарных отношенийили Свойства бинарных отношенийи говорят, что оно (отношение) задано на множестве Свойства бинарных отношений (а не на Свойства бинарных отношений). Условия 1-3 в таких обозначениях выглядят более естественно:

Свойства бинарных отношенийдля всех Свойства бинарных отношений (рефлексивность)

Если Свойства бинарных отношений, то Свойства бинарных отношений (симметричность)

Если Свойства бинарных отношенийи Свойства бинарных отношений, то Свойства бинарных отношений (транзитивность)

Легко доказывается, что если на множестве Свойства бинарных отношенийзадано отношение эквивалентности, то множество Свойства бинарных отношенийразбивается на взаимно непересекающиеся подмножества, состоящие из эквивалентных друг другу элементов (классы эквивалентности).

Пример 1. Рассмотрим на множестве вещественных чисел Свойства бинарных отношенийотношение, заданное просто равенством чисел. Предикат такого отношения:

Свойства бинарных отношений, или просто Свойства бинарных отношений

Условия 1-3, очевидно, выполняются, поэтому данное отношение является отношением эквивалентности. Каждый класс эквивалентности этого отношения состоит из одного числа.

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

Условия 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. Отношение Свойства бинарных отношенийна множестве Свойства бинарных отношенийназывается отношением порядка, если оно обладает следующими свойствами:

Свойства бинарных отношенийдля всех Свойства бинарных отношений (рефлексивность)

Если Свойства бинарных отношенийи Свойства бинарных отношений, то Свойства бинарных отношений (антисимметричность)

Если Свойства бинарных отношенийи Свойства бинарных отношений, то Свойства бинарных отношений (транзитивность)

Обычно отношение порядка обозначают знаком Свойства бинарных отношений. Если для двух элементов Свойства бинарных отношенийи Свойства бинарных отношенийвыполняется Свойства бинарных отношений, то говорят, что Свойства бинарных отношений"предшествует" Свойства бинарных отношений. Как и для отношения эквивалентности, условия 1-3 в таких обозначениях выглядят более естественно:

Свойства бинарных отношенийдля всех Свойства бинарных отношений (рефлексивность)

Если Свойства бинарных отношенийи Свойства бинарных отношений, то Свойства бинарных отношений (антисимметричность)

Если Свойства бинарных отношенийи Свойства бинарных отношений, то Свойства бинарных отношений (транзитивность)

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

Предикат данного отношения есть просто утверждение Свойства бинарных отношений.

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

Свойства бинарных отношений

Свойства бинарных отношенийявляется начальником (не обязательно непосредственным) Свойства бинарных отношений

Назовем такое отношение "быть начальником". Легко проверить, что отношение "быть начальником" является отношением порядка. Заметим, что в отличие от предыдущего примера, существуют такие пары сотрудников Свойства бинарных отношенийи Свойства бинарных отношений, для которых не выполняется ни Свойства бинарных отношений, ни Свойства бинарных отношений (например, если Свойства бинарных отношенийи Свойства бинарных отношенийявляются сослуживцами). Такие отношения, в которых есть несравнимые между собой элементы, называют отношениями частичного порядка.


2.1.3 Функциональное отношение

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

Если Свойства бинарных отношенийи Свойства бинарных отношений, то Свойства бинарных отношений (однозначность функции).

Обычно, функциональное отношение обозначают в виде функциональной зависимости - Свойства бинарных отношенийтогда и только тогда, когда Свойства бинарных отношений. Функциональные отношения (подмножества декартового произведения!) называют иначе графиком функции или графиком функциональной зависимости.

Предикат функционального отношения есть просто выражение функциональной зависимости Свойства бинарных отношений.


2.1.4 Еще пример бинарного отношения

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

Вовочка любит Вовочку (эгоист).

Петя любит Машу (взаимно).

Маша любит Петю (взаимно).

Маша любит Машу (себя не забывает).

Лена любит Петю (несчастная любовь).

Информацию о взаимоотношения данных молодых людей можно описать бинарным отношением "любить", заданном на множестве Свойства бинарных отношений. Это отношение можно описать несколькими способами.

Способ 1. Перечисление фактов в виде произвольного текста (как это сделано выше).

Способ 2. В виде графа взаимоотношений:


Свойства бинарных отношений

Рисунок 1 Граф взаимоотношений

Способ 3. При помощи матрицы взаимоотношений:


Таблица 1. Матрица взаимоотношений

Кого

Кто

Вовочка Петя Маша Лена
Вовочка Любит
Петя Любит
Маша Любит Любит
Лена Любит

Способ 4. При помощи таблицы фактов:


Таблица 2 Таблица фактов

Кто любит Кого любят
Вовочка Вовочка
Петя Маша
Маша Петя
Маша Маша
Лена Петя

С точки зрения реляционных баз данных наиболее предпочтительным является четвертый способ, т.к он допускает наиболее удобный способ хранения и манипулирования информацией. Действительно, перечисление фактов как текстовая форма хранения информации уместна для литературного произведения, но с трудом поддается алгоритмической обработке. Изображение в виде графа наглядно, и его удобно использовать как конечную форму представления информации для пользователя, но хранить данные в графическом виде неудобно. Матрица взаимоотношений уже больше соответствует требованиям информационной системы. Матрица удобна в обработке и компактно хранится. Но одно небольшое изменение, например, появился еще Вася и влюбился в несчастную Лену, требует перестройки всей матрицы, а именно, добавления и колонок, и столбцов. Таблица фактов свободна от всех этих недостатков - при добавлении новых действующих лиц просто добавляются новые строки.

Что касается предиката данного отношения, то он