Отношение «Читает лекции по…»

Преподаватель	Предмет	Количество часов
Ковалёв	Математика	40
Ковалёв	Базы данных	80
Резников	Экономика	50
Ткачёв	Математика	51
Ткачёв	Менеджмент	51

Для того, чтобы определить факты, характеризующие посещение студентами лекций, введём отношение . Упорядоченная тройка тогда и только тогда, когда студент посещает лекции по предмету у преподавателя . Назовём это отношение «Посещать лекции». Его также представим в виде таблицы 2.3.

Таблица 2.3

Отношение «Посещать лекции»

Преподаватель	Предмет	Преподаватель
Иванов	Математика	Ткачёв
Иванов	Базы данных	Ковалёв
Петров	Математика	Ковалёв
Петров	Экономика	Резников
Сидоров	Экономика	Резников
Сидоров	Базы данных	Ковалёв

Рассмотрим отношение подробнее. Оно задано на декартовом произведении . Это произведение содержит кортежей. Множество представляет собой совокупность всех возможных вариантов посещений студентами лекций. Отношение же показывает текущее состояние учебного процесса. Очевидно, что отношение является изменяемым во времени отношением. Итак, факты о ходе учебного процесса удалось отразить в виде двух отношений третьей степени (3-арных), а сами отношения удалось представить в виде таблиц с тремя колонками. Удобство использования табличной формы для задания отношения определяется следующими факторами:

1. Все используемые множества конечны.

2. При добавлении или удалении фамилий студентов, наименований предметов, фамилий преподавателей просто добавляются или удаляются соответствующие строки в таблице.

2.20. Бинарные отношения

Бинарным отношением, заданным на множестве , называется подмножество его декартового квадрата . Формально бинарное отношение представляется кортежем , первая компонента которого называется носителем бинарного отношения, а вторая – сигнатурой. Совокупность множества с заданным на нём бинарным отношением называется графом. Формально граф, также как и бинарное отношение, описывается кортежем . Высказывательная форма бинарного отношения имеет вид: . Таким образом, элементами бинарного отношения являются упорядоченные пары. Если элементы и находятся в отношении , то используется запись или соотношение . Рассмотрим способы задания бинарных отношений.

2.20.1. Матричный способ задания отношений

При матричном способе задания бинарных отношений используют матрицу смежности и матрицу инциденций . Матрица смежности строится следующим образом. Перенумеруем элементы множества целыми числами от 1 до : . Построим квадратную матрицу размером . Её строка соответствует элементу множества , а столбец соответствует элементу множества . На пересечении строки и столбца ставится единица, если в , или в другой форме . Общее правило задания матрицы смежности бинарного отношения можно формально записать:

Матрица смежности содержит всю информацию о том, для каких пар элементов из выполнено отношение . Произвол состоит в выборе нумерации на множестве . Является очевидным, что можно выбрать различных нумераций и, соответственно, матриц, описывающих данное отношение. Если задана матрица размером из нулей и единиц и выбрана нумерация на множестве , то тем самым на этом множестве задаётся некоторое отношение . Матрица смежности , для которой все , , задаёт пустое отношение , которое не выполняется ни для одной пары. Матрица смежности , для которой все , , задаёт полное отношение , которое выполняется ни для всех пар. Особую роль играют матрицы , элементы которой принимают следующие значения:

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

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