Введение в системы управления базами данных


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



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

Определение 9. Отношение

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

Обычно отношение порядка обозначают знаком

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

Пример 3. Простым примером отношения порядка является отношение, задаваемое обычным неравенством

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

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

.

Пример 4. Рассмотрим на множестве

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

Назовем такое отношение "быть начальником". Легко проверить, что отношение "быть начальником" является отношением порядка. Заметим, что в отличие от предыдущего примера, существуют такие пары сотрудников

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









Начало  Назад  Вперед