Основные понятия алгебры отношений

Из определения понятия «множество», сформулированного Н. Бурбаки, видно, что отношения между элементами множеств имеют основополагающее значения в теории множеств. Поэтому для усиления описательных возможностей теоретико-множественного языка многие математики используют алгебру отношений. Кроме того, алгебра отношений позволяет решать задачи формализации не только хорошо структурированных – математических задач, используя при этом строгие отношения, такие как равно (=), больше (>), меньше (<), включение и др., но и слабоструктурированные, связанные со сложными межличностными отношениями, например, между преподавателем и обучающимися («быть преподавателем»), между преподавателями и администрацией вуза («быть начальником» или «быть подчиненным») и др. Последние отношения называют родовидовыми.

Понятие «отношение» является философской категорией и объединяет такие понятия как «соответствие», «отображение», «функция».

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

Элементарным примером бинарных отношений может служить отношение обучающихся к знаниям по конкретной учебной дисциплине, выраженных в оценках, полученных ими в течение семестра. Обозначим – множество обучающихся в учебной группе в количестве n человек, – множество оценок в количестве h, полученных обучающимися за семестр (будем различать два класса оценок – удовлетворительных и неудовлетворительных), G – множество пар, которое ставит в соответствие каждого обучающегося оценкам, полученным в семестре. В данном случае учебный журнал можно интерпретировать как матрицу отношений, ставя на пересечении строк (фамилий обучающихся) и столбцов (порядковый номер контрольного занятия, где всем обучающимся выставляются оценки) «1», если обучающийся имеет удовлетворительные знания и «0», если неудовлетворительные. Такое задание отношений называется матричным. Часто бинарные отношения задают не в виде таблицы (матрицы отношений), а правил, общий вид которых имеет вид

Другой способ задания бинарных отношений является графический (в виде графа). Здесь точками (вершинами) задаются элементы множества, например, А, ребрами (линиями соединяющими эти вершины) множество отношений Е. Такие графы называются неориентированными. Если ребра обозначают стрелками, то их называют дугами. В этом случае графы принимает вид ориентированного или орграфа. Формальная запись графа отношений имеет следующий вид.

На рис. 3 иллюстрируются декомпозиция сложного отношения «взаимодействие обучающихся в учебной группе», обозначим его Е, на типовые отношения, которые возникают в процессе учебы в вузе. Из рисунка видно, что множество вершин имеют одну природу. В этом случае говорят, что построены графы отношений в множестве А.

Дадим краткую характеристику графам отношений, приведенных на рис. 3 (а–е).

Характерной особенностью графа (см. рис. 3 а) является отсутствие, каких либо отношений, связанных с учебной деятельностью обучающихся.

Граф, изображенный на рис.3 б) в теории графов называется «графом Понтрягина - Куратовского». Особенностью этого неориентированного графа является то, что его ребра пересекаются и поэтому он называется неплоским. Плоские графы отношений показаны на остальных рисунках. На рис. 3 в) показан двудольный орграф. Подобным графом можно интерпретировать, например, отношения преподавателя (Р) с обучающимися (А) на лекционных занятиях. Для этого необходимо вершину обозначить другой буквой, например «» и считать, что является одноэлементным множеством. В данном случае говорят, что построен граф отношений от Р к А. Рассматриваемым биграфом можно интерпретировать и другие отношения преподавателя с обучающимися, например, на семинарских занятиях. Для этого необходимо поменять одинарные стрелки на двойные, что будет обозначать отношение диалога между преподавателем и обучающимися.

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

На рис. 3 е) изображен граф особенностью, которого является то, что у него имеется два множества связанных вершин, каждое из которых изолированы друг от друга. Такие графы, вершины которых принадлежат одному и тому же множеству, а также дуги множеству однородных отношений, называются частями общего графа или суграфом. В нашем случае - суграф, где,. Аналогично суграфом является и, где,. Очевидно, что.

От графического представления отношений в виде графов легко перейти к матричному представлению. В теории графов различают два вида матричного представления графов – матрицами смежности и инцидентности.

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

Очевидно, что в случае (см. рис. 3 а) матрица смежности равна нулю, а в случае (см. рис. 3 б) единице, т.е. их элементы принимают значения «0» или «1» соответственно.

Задание отношений матрицами инцидентности основывается на понятии «инцидентность», которое определяется как отношение между разнородными объектами (вершинами и ребрами) графа. В то время как смежность представляет собой отношение между однородными объектами (вершинами).

Говорят, если вершина является концом ребра, то они инцидентны: вершина инцидентна ребру и обратно.

При переходе от орграфов к матрицам инцидентности различают положительную инцидентность (дуга исходит из вершины) и отрицательную (дуга заходит в вершину). Для примера (см. рис. 3. е) матрица инцидентности имеет вид

.

Важным понятием в алгебре отношений является понятие «функциональное отношение». Оно определяется как отношение, если все его элементы (упорядоченные пары) имеют различные первые координаты. Иначе, каждому элементу x из X такому, что соответствует один и только один элемент y из Y.

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

Любое функциональное отношение в алгебре отношений рассматривается как функция. Первую координату x упорядоченной пары называют аргументом (переменной), а вторую y – образом (значением) функции. Традиционная запись функции соответствует соотношению, или. Множество Н тех пар, для которых выполнено соотношение называют графиком функции.

Если функциональное отношение всюду определено на X, т.е. его область определения совпадает с множеством X, то его называют отображением множества X в Y и записывают. Отображение можно рассматривать как функцию f, определенную на множестве X и принимающую значения в множестве Y.

Из вышесказанного видно, что различие между отображением и функцией сводится к способу определения этих отношений на множестве X, причем отображение рассматривается как частный случай функции. Большинство авторов не различают понятия отображения и функции, оставляя открытым вопрос об области определения. В этом случае, если f – отображение или функция, то пишут.

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

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

Такие функциональные отношения могут быть представлены в учебной базе данных вуза для формирования соответствующих логических выводов, например, если соискатель за интервал времени выполнил и опубликовал научных трудов, то можно считать, что он выполнил минимальные требования ВАК по опубликованию научных результатов на соискание ученой степени доктора наук.

Большое значение в алгебре отношений имеют типы отображений. Различают отображения X в Y, где каждый элемент имеет один и только один образ из Y. Примером такого отображения может служить рассмотренный выше пример (см. рис. 4).

Говорят, что имеет место отображение X на Y в том случае, если любой элемент из Y есть образ, по крайней мере, одного элемента из X. Такое отображение получило название сюрьекция или накрытие.

Если для любых двух и более различных элементов из Х их образы также различны, то отображение f называется инъекцией.

Отображение, которое одновременно является сюрьекцией и инъекцией называется биекцией или наложением. В этом случае принято говорить, что есть взаимно-однозначное отображение, а между элементами X и Y имеется взаимно-однозначное соответствие.

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

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

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

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

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

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

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

Дата добавления: 2014-01-03