То есть

АЦИКЛИЧЕСКОЕ БИНАРНОЕ ОТНОШЕНИЕ

Ациклическим бинарным отношением называется такое отношение Р, если оно не содержит циклов, т.е. не существует t>1 такого, что а₁Pa₂, a₂Pa_3,…,a_1-tPa_t и a_tPa₁. Если указанный цикл существует, то его длина равна t. Соответствующий ациклическому бинарному отношению граф также называется ациклическим. Такой граф представлен ниже. Пример такого графа представлен на рисунке а. Пример графа, имеющего цикл на рисунке б

ЧАСТИЧНЫЙ ПОРЯДОК, СЛАБЫЙ ПОРЯДОК, ЛИНЕЙНЫЙ ПОРЯДОК

Для того, чтобы дать определения следующим порядкам необходимо дать определения следующие условия рациональности:

Транзитивность:

Если для любых трех у, y1,y2, y предпочтительнее у1, y1предпочтительнее y2, то у предпочтительнее y2.

То есть

Связность:

ОТРИЦАТЕЛЬНАЯ ТРАНЗИТИВНОСТЬ:

Р отрицательно транзетивно если существуют x, y, zпринадл. А, которые (x,y)не принадлежат. P и (y,z) не принадлежат. P, должны быть (x,z) не принадл.P

Р отрицательно транзетивно, если Рс(дополнение графа)-транзитивно.

Раскрыв смысл этих условий дадим определния специальным классам отношений:

Частичный порядок –это ациклическое и транзитивное бинарное отношение

Слабый порядок – это отрицательно транзитивный частичный порядок

Линейный порядок – связный слабый порядок.

Из определений очевидно, что:

Где LO-линейный порядок, WO-слабый порядок, PO-частичны порядок, AC- множество ациклических отношений.

Для того, чтобы дать определения отношениям несравнимости и толерантности необходимо исследовать свойства отношений несравнимости:

Отшношением несравнимости для б.о. Р является отношение вида

Где I_p-отношение несравнимости. Отношение несравнимости для слабого порядка является отношением эквивалентности.

Дата добавления: 2015-10-13