![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Задание отношений. ⇐ ПредыдущаяСтр 6 из 6 Отношения на конечных множествах обычно задаются: 1. Правилом (например, многоугольники, имеющие одинаковое число вершин). 2. Перечислением пар, для которых это отношение выполняется. 3. Матрицей бинарного отношения. Для отношения R, заданного на множестве M ={a1, a2, . . . , an}, - это квадратная матрица C порядка m, элементы которой находятся по правилу:
Пример 1.13. С помощью матрицы задано отношение ≥ на множестве A={1, 2, 3} 4. Графом (для бинарных отношений). 5. Таблично. Все элементы отношения есть однотипные кортежи. Однотипность кортежей позволяет считать их аналогами строк в простой таблице, т.е. в такой таблице, в которой все строки состоят из одинакового числа ячеек и в соответствующих ячейках содержатся одинаковые типы данных. Например, отношение, состоящее из трех следующих кортежей {(1, "Иванов", 10000), (2, "Петров", 20000), (3, "Сидоров", 30000)} можно считать таблицей, содержащей данные о сотрудниках и их зарплатах. Такая таблица будет иметь три строки и три колонки, причем в каждой колонке содержатся данные одного типа. Для каждого отношения можно задать обратное отношение. Любое отношение между элементами X и Y полностью характеризуется подмножеством декартова произведения X и Y. Различных отношений столько, сколько подмножеств в этом декартовом произведении. В декартовом произведении А×А содержится 25 (5*5) элементов, значит оно имеет 225 подмножеств (3355442). Столько отношений может существовать между элементами множества А. За исключением крайнего случая, когда отношение есть само декартово произведение, отношение включает в себя не все возможные кортежи из декартового произведения. Это значит, что для каждого отношения имеется критерий, позволяющий определить, какие кортежи входят в отношение, а какие – нет. Этот критерий, по существу, определяет для нас смысл (семантику) отношения. Действительно, каждому отношению можно поставить в соответствие некоторое логическое выражение, зависящее от n параметров (n-местный предикат) и определяющее, будет ли кортеж принадлежать отношению. Это логическое выражение называют предикатом отношения. Более точно, кортеж принадлежит отношению Понятие отношения является очень важным не только с математической точки зрения. Понятие отношения фактически лежит в основе всей реляционной теории баз данных. Свойства отношений.
Кроме этих, основных, возможно наличие других свойств, противоположных, не совпадающих или с более суженными по сравнению с ними свойствами.
Отношения делятся на различные виды в зависимости от того, обладают или не обладают они некоторыми свойствами. Рассмотрим некоторые виды отношений. Отношение эквивалентности Элементы множества можно рассматривать как эквивалентные в том случае, когда любой из этих элементов при некотором рассмотрении может быть заменен другим. В этом случае говорят, что данные элементы находятся в отношении эквивалентности. Примерами отношений эквивалентности являются: · отношение «быть на одном курсе» на множестве студентов факультета; · отношение «иметь одинаковый остаток при делении на 3» на множестве натуральных чисел; · отношение параллельности на множестве прямых плоскости; · отношение подобия на множестве треугольников и т. п. Термин «отношение эквивалентности» применим только в том случае, если выполняются следующие три условия: 1) каждый элемент эквивалентен самому себе; 2) высказывание, что два элемента являются эквивалентными, не требует уточнения, какой из элементов рассматривается первым и какой вторым; 3) два элемента, эквивалентные третьему, эквивалентны между собой. В качестве общего символа отношения эквивалентности используется символ 1) х 2) х 3) х Таким образом, отношение называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. Легко доказывается, что если на множестве задано отношение эквивалентности, то множество разбивается на взаимно непересекающиеся подмножества, состоящие из эквивалентных друг другу элементов (классы эквивалентности). Например, X—множество студентов курса, а отношением эквивалентности является отношение «быть в одной группе». Подмножество элементов, эквивалентных некоторому элементу х Пусть J — некоторое множество индексов. Обозначим через Для отдельных частных отношений эквивалентности используются символы: = — для обозначения равенства, ||—для обозначения параллельности, ↔ — для обозначения логической эквивалентности. Отношение порядка Часто приходится сталкиваться с отношениями, которые определяют некоторый порядок расположения элементов множества. Так, мы отличаем понятия «раньше» и «позже», «больше» и «меньше» и пользуемся при этом символами > или <, если элементы множества являются числами. Мы отличаем понятия множества и подмножества, пользуясь символами Во всех этих случаях можно расположить элементы множества X или группы элементов в некотором порядке или, другими словами, ввести отношение порядка на множестве X. Различают отношение нестрогого порядка, для которого используется символ ≤, и отношение строгого порядка, для которого используется символ <. Опишем эти отношения путем перечисления свойств, которыми они обладают. Отношением нестрогого порядка называется отношение М, обладающее следующими тремя свойствами: x≤x — рефлексивность; x≤y и y≤x→x=у – антисимметричность; х≤у и у≤z→x≤z – транзитивность. Множество, удовлетворяющее приведенным свойствам, называется частично упорядоченным. Отношение упорядочения можно определить как между элементами, так и между элементом и подмножеством и между подмножествами: (a ≤ M1)|"a,bÎM1:(a ≤ b) (M1 ≤ M2)|"aÎM1,bÎM2:(M1≤ M2) ® (a ≤ b). Кроме этого отношения упорядочения ≤, которое называют прямым, существует отношение обратного упорядочения с символом ≥ ("больше или равно") с теми же свойствами. Отношением строгого порядка называется отношение, обладающее следующими тремя свойствами: х<х — ложно (антирефлексивность); х<у и у<х взаимоисключаются (несимметричность); х<у и y<z→x<z (транзитивность). Множество называется совершенно упорядоченным (другое название – цепь) если между любыми его элементами существует отношение упорядоченности. С отношением упорядочения связано трехместное отношение "находиться между". Пусть a < b < c или c < b < a. Тогда говорится, что элемент b находится между элементами a и c и записывается как <a,b,c> или <c,b,a>. Элемент а Точной верхней (нижней) гранью подмножества В Отношением упорядочения множество M можно разделить на два непересекающихся подмножества M1 и M2 такие, что: "a,b:(aÎM1) и (bÎM2) ® (a ≤ b), "c:(c > M1) ® (cÎM2), "c:(c < M2) ® (cÎM1).. Такое разделение называется сечением множества.
|