Задание отношений.

Отношения на конечных множествах обычно задаются:

1. Правилом (например, многоугольники, имеющие одинаковое число вершин).

2. Перечислением пар, для которых это отношение выполняется.

3. Матрицей бинарного отношения. Для отношения R, заданного на множестве M ={a₁, a₂, . . . , a_n}, - это квадратная матрица C порядка m, элементы которой находятся по правилу:

Пример 1.13. С помощью матрицы задано отношение ≥ на множестве A={1, 2, 3}

4. Графом (для бинарных отношений).

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

Для каждого отношения можно задать обратное отношение.

Любое отношение между элементами X и Y полностью характеризуется подмножеством декартова произведения X и Y. Различных отношений столько, сколько подмножеств в этом декартовом произведении. В декартовом произведении А×А содержится 25 (5*5) элементов, значит оно имеет 2²⁵ подмножеств (3355442). Столько отношений может существовать между элементами множества А.

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

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

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

Свойства отношений.

1. Рефлексивность. Бинарное отношение R на множестве A обладает свойством рефлексивности, если для всех .
2. Симметричность. Бинарное отношение R на множестве A обладает свойством симметричности, если для x≠y и для всех .
3. Транзитивность. Бинарное отношение R на множестве A обладает свойством транзитивности, если и , то и для всех .

Кроме этих, основных, возможно наличие других свойств, противоположных, не совпадающих или с более суженными по сравнению с ними свойствами.

1. Антирефлексивность. Бинарное отношение R на множестве A обладает свойством антирефлексивности, если для всех .
2. Асимметричность(несимметричность). Бинарное отношение R называется асимметричным(несимметричным), если , при этом x≠y, то для любых элементов , т.е. входит не более одной из каждых двух пар (x, y) или (y, x).
3. Антисимметричность. Бинарное отношение R на множестве A обладает свойством антисимметричности, если и , то из этого следует что x=y.
4. Связность. Бинарное отношение R на множестве A обладает свойством связанности, если или для всех .

Отношения делятся на различные виды в зависимости от того, обладают или не обладают они некоторыми свойствами.

Рассмотрим некоторые виды отношений.

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

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

Примерами отношений эквивалентности являются:

· отношение «быть на одном курсе» на множестве студентов факультета;

· отношение «иметь одинаковый остаток при делении на 3» на множестве натуральных чисел;

· отношение параллельности на множестве прямых плоскости;

· отношение подобия на множестве треугольников и т. п.

Термин «отношение эквивалентности» применим только в том случае, если выполняются следующие три условия:

1) каждый элемент эквивалентен самому себе;

2) высказывание, что два элемента являются эквивалентными, не требует уточнения, какой из элементов рассматривается первым и какой вторым;

3) два элемента, эквивалентные третьему, эквивалентны между собой.

В качестве общего символа отношения эквивалентности используется символ (иногда ~). Тогда общее определение эквивалентности получим, записав три вышеприведенных условия в виде следующих соотношений:

1) х х (рефлексивность);

2) х у→ у х (симметричность);

3) х у и y z→x z (транзитивность).

Таким образом, отношение называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

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

Подмножество элементов, эквивалентных некоторому элементу х Х, называют классом эквивалентности. Так, группа, в которой учится студент Иванов, будет классом эквивалентности, эквивалентным студенту Иванову.

Пусть J — некоторое множество индексов. Обозначим через множество классов эквивалентности для множества X. Очевидно, что все элементы одного класса эквивалентности эквивалентны между собой (свойство транзитивности) и всякий элемент x X может находиться в одном и только в одном классе. Но в таком случае X является объединением непересекающихся множеств A_j, так что полная система классов является разбиением множества X. Таким образом, каждому отношению эквивалентности на множестве X соответствует некоторое разбиение множества X на классы А_j.

Для отдельных частных отношений эквивалентности используются символы: = — для обозначения равенства, ||—для обозначения параллельности, ↔ — для обозначения логической эквивалентности.

Отношение порядка

Часто приходится сталкиваться с отношениями, которые определяют некоторый порядок расположения элементов множества. Так, мы отличаем понятия «раньше» и «позже», «больше» и «меньше» и пользуемся при этом символами > или <, если элементы множества являются числами. Мы отличаем понятия множества и подмножества, пользуясь символами или .

Во всех этих случаях можно расположить элементы множества X или группы элементов в некотором порядке или, другими словами, ввести отношение порядка на множестве X.

Различают отношение нестрогого порядка, для которого используется символ ≤, и отношение строгого порядка, для которого используется символ <. Опишем эти отношения путем перечисления свойств, которыми они обладают.

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

x≤x — рефлексивность;

x≤y и y≤x→x=у – антисимметричность;

х≤у и у≤z→x≤z – транзитивность.

Множество, удовлетворяющее приведенным свойствам, называется частично упорядоченным.

Отношение упорядочения можно определить как между элементами, так и между элементом и подмножеством и между подмножествами:

(a ≤ M₁)|"a,bÎM₁:(a ≤ b)

(M₁ ≤ M₂)|"aÎM₁,bÎM₂:(M₁≤ M₂) ® (a ≤ b).

Кроме этого отношения упорядочения ≤, которое называют прямым, существует отношение обратного упорядочения с символом ≥ ("больше или равно") с теми же свойствами.

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

х<х — ложно (антирефлексивность);

х<у и у<х взаимоисключаются (несимметричность);

х<у и y<z→x<z (транзитивность).

Множество называется совершенно упорядоченным (другое название – цепь) если между любыми его элементами существует отношение упорядоченности.

С отношением упорядочения связано трехместное отношение "находиться между". Пусть a < b < c или c < b < a. Тогда говорится, что элемент b находится между элементами a и c и записывается как <a,b,c> или <c,b,a>.

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

Точной верхней (нижней) гранью подмножества В А называется наименьшая верхняя (наибольшая нижняя) грань для В. Точная верхняя и точная нижняя грани множества В А обозначаются через sup В и inf В, соответственно.

Отношением упорядочения множество M можно разделить на два непересекающихся подмножества M₁ и M₂ такие, что:

"a,b:(aÎM₁) и (bÎM₂) ® (a ≤ b),

"c:(c > M₁) ® (cÎM₂),

"c:(c < M₂) ® (cÎM₁)..

Такое разделение называется сечением множества.