Контрольная работа: Свойства бинарных отношений

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

для всех (рефлексивность)

Если и , то (антисимметричность)

Если и , то (транзитивность)

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

Предикат данного отношения есть просто утверждение .

Пример 4. Рассмотрим на множестве всех сотрудников некоторого предприятия отношение, задаваемое следующим образом: сотрудник предшествует сотруднику тогда и только тогда, когда выполняется одно из условий:

является начальником (не обязательно непосредственным)

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

2.1.3 Функциональное отношение

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

Если и , то (однозначность функции).

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

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

2.1.4 Еще пример бинарного отношения

Пример 5. Пусть множество есть следующее множество молодых людей: {Вовочка, Петя, Маша, Лена}, причем известны следующие факты:

Вовочка любит Вовочку (эгоист).

Петя любит Машу (взаимно).

Маша любит Петю (взаимно).

Маша любит Машу (себя не забывает).

Лена любит Петю (несчастная любовь).

Информацию о взаимоотношения данных молодых людей можно описать бинарным отношением "любить", заданном на множестве . Это отношение можно описать несколькими способами.

Способ 1. Перечисление фактов в виде произвольного текста (как это сделано выше).

Способ 2. В виде графа взаимоотношений:

Рисунок 1 Граф взаимоотношений

Способ 3. При помощи матрицы взаимоотношений:

Таблица 1. Матрица взаимоотношений

Кого Кто	Вовочка	Петя	Маша	Лена
Вовочка	Любит
Петя	Любит
Маша	Любит	Любит
Лена	Любит