Предыдущая страница реферата | 3  4  5  6  7  8  9  10  11  12  13 | Следующая страница реферата

2.5. Отношения на множестве

Определение отношения степени n. Подмножество R декартового произведения множеств A1 A2… An называется отношением степени n (n-арным отношением).

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

Замечание. Понятие отношения является очень важным не только с математической точки зрения. Как будет показано ниже, отношения являются математическим аналогом таблиц.

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

Во-первых, все элементы отношения есть однотипные кортежи. Если же множество состоит из разнотипных числовых кортежей, то это множество не является отношением ни в R1, ни в R2, ни в Rn.

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

Действительно, каждому отношению можно поставить в соответствие некоторое логическое выражение P(x1 ,x2, … , xn), зависящее от n параметров и определяющее, будет ли кортеж (a1, a2, … ,an) принадлежать отношению R. Это логическое выражение называют предикатом отношения R. Более точно, кортеж (a1, a2, … ,an) принадлежит отношению R тогда и только тогда, когда предикат этого отношения P(a1, a2, … ,an) принимает значение “истина”. Таким образом, существует взаимно однозначное соответствие между n-арными отношениями и n-местными предикатами.

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

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

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

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

(x, x)R для всех xA (рефлексивность).

Если (x, y)R, то (y, x)R (симметричность).

Если (x, y)R и (y, z)R, то (x, z)R (транзитивность).

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

x=x для всех xA (рефлексивность).

Если x=y, то y=x (симметричность).

Если x=y и y=z, то x=z (транзитивность).

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

Если (x, y)R и (y, x)R, то x=y (антисимметричность).

Если (x, y)R и (y, z)R, то (x, z)R (транзитивность).

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

xx для всех xA (рефлексивность).

Если x  y и y  x, то x = y (антисимметричность).

Рекомендуем скачать другие рефераты по теме: ответы на сканворды в одноклассниках, реферат на тему технология.





Предыдущая страница реферата | 3  4  5  6  7  8  9  10  11  12  13 | Следующая страница реферата