Примеры решения

Задача 17.

Пусть (x, y)R₁R₂, тогда (x, y)R₁ или (x, y)R₂. В первом случае из рефлексивности R₂ следует (y, y)R₂ и, следовательно,

(x, y)R₁ o R₂. Аналогично для второго случая получим (x, x)R₁ и (x, y)R₁ o R₂, что и требовалось доказать.

Задача 21.

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

R(R  R^d ) = R  (R ) = R  (R(R )^-1) = R  (R )^s.

Покажем теперь, что отношение R  (R )^s полно. Для любых x, yA возможен один из трех случаев: 1) (x, y)R; 2) (y, x)R; 3) (x, y)R и (y, x)R. В первых двух случаях принадлежность (x,y) к рассматриваемому отношению очевидна. Рассмотрим третий случай. Так как (x,y)R и (x,y) ^-1, то (x,y)(R )^s. Следовательно, рассматриваемое отношение полно.

Задача 25.

Докажем необходимость. Предположим противное, что отношение Р негатранзитивно, но

xPy и   z : xP z и zP y. (1)

Так как Р негатранзитивно, то из (1) следует одновременное выполнение xРy и xy, а этого быть не может, поэтому из негатранзитивности следует

xPy   zА, xPz или zPy. (2)

Докажем обратное следствие. Предположим противное, т.е. что (2) выполнено, но Р не является негатранзитивным. Последнее означает, что

 x,y,zA : xPz, zPy, но (x, y) P,

т.е. (x, y)P. Таким образом, получаем, что xPy выполняется, а xPz и zPy не выполняется, и, значит, (4) неверно, что противоречит предположению. Полученное противоречие доказывает требуемое следствие.

Задача 29.

Пусть отношение R негатранзитивно, т.е. если (x, y)R и (y, z)R, то (x, z)R. Пусть для u, v, w выполнены условия (u, v)R^d и (v, w)R^d. Тогда, по определению двойственного отношения, (v, u)R и (w, v)R. Так как R негатранзитивно, то (w, u)R, что означает (u, w)R^d. Следовательно, R^d транзитивно.

Обратное следствие доказывается аналогично.

5. Специальные бинарные отношения. Упорядочение и безразличие

Для бинарных отношений нет устоявшейся терминологии. В данном пособии использованы названия специальных бинарных отношений из [4].

Бинарные отношения нас интересуют, прежде всего, с точки зрения теории принятия решений. Для этого необходимо построить такие отношения, свойства которых позволили бы их использовать в этой области. Для принятия решений, как минимум, надо уметь из 2-х элементов выбрать лучший, т.е. нужно построить такое отношение предпочтения, минимально необходимым свойством которого, является асимметричность.

Введем следующие отношения.

P_уп – отношение строгого упорядочения, обладающее свойством асимметричности.

I_уп – отношение безразличия. Это отношение исключает P^d_уп между двумя элементами, т.е.

x I_уп y  ( xP_уп у и yP_уп x ). (1)

Так как (x, y) и (y, x) не принадлежат P_уп, то нельзя сказать, что x лучше y, или x лучше y. Если воспользоваться понятием пересечения отношений, то I_уп можно также представить в виде

I_уп =P_уп P^d_уп. (2)

Покажем, что I_уп рефлексивно и симметрично.

Симметричность. Отношение xI_упy означает, что (x, y)P_уп и (y, x)P_уп. Отношение же yI_упx означает, что (y, x)P_уп и (x, y)P_уп. То есть, xI_упy и yI_упx абсолютно эквивалентны. Значит, I_уп симметрично.

Рефлексивность. Так как P_уп антирефлексивно, то (x, x)P_уп и по определению (x, x)I_уп . Значит, I_уп рефлексивно.

Можно дать другое определение отношения I_уп, как симметричного, рефлексивного отношения.

На базе введенных отношений строгого упорядочения и безразличия можно построить новое отношение

R_уп = P_уп  I_уп, (3)

которое называется нестрогим упорядочением.

Докажем, что R_уп полно.

ДОКАЗАТЕЛЬСТВО. Возьмем любую пару (x, y). Для нее возможны три случая:

а) (x, y)P_уп; б) (y, x)P_уп;

в) (x, y)P_уп и (y, x)P_уп, т.е. (x, y)I_уп.

Если имеют место случаи а) или в), то, по свойству объединения, (x, y)R_уп. Если выполняется б) или в), то (y, х)R_уп. Иными словами, в любом случае либо пара (x, y), либо (y, x) принадлежит R_уп. Значит, R_уп полно.

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

Рассмотрим основные свойства отношений P_уп и R_уп.

1. а) P_уп  P^d_уп = P^d_уп ;

б) P_уп  P^d_уп = P_уп ; в) I =P_уп  P^d_уп ._.

ДОКАЗАТЕЛЬСТВО.

Докажем свойства а) и б). Пусть (x, y)P_уп. Тогда, в силу ас-симметричности, (y, x)P_уп, а значит, (x, y)P^d_уп по определению двойственного отношения. Таким образом, из (x, y)P_уп следует (x, y)P^d_уп, а это означает, что P_уп  P^d_уп. Тогда, по свойствам объединения и пересечения множеств, P_уп  P^d_уп = P^d_уп , a P_уп = = P^d_уп  P_уп, что и требовалось доказать.

Докажем свойство в). Пусть (x, y)I_уп. Тогда, по определению I_уп, будем иметь

(x, y) P_уп и (y, x) P_уп.

Второе соотношение эквивалентно тому, что (x, y)P^d_уп. Следова-

тельно, из (x, y)I_уп вытекает, что (x, y)P^d_уп и (x,y) P_уп , т.е. (x, y) P_уп  P^d_уп и I_уп P  P^d_уп.

Докажем обратное включение. Ход рассуждений представим в виде схемы:

,

Что и требовалось доказать.

2. R_уп = P^d_уп; P_уп = R^d_уп , т.е. P_уп и R_уп образуют двойственную пару.

ДОКАЗАТЕЛЬСТВО. По определению R_уп = P_уп  I_уп. Воспользуемся представлением (2) отношения безразличия I_уп. Тогда

R_уп = P_уп  (P_уп  P^d_уп ) = (P_уп P_уп)  ( P_уп  P^d_уп).

Так как (P_уп P_уп) = АА, то R_уп = P_уп  P^d_уп, а по свойству 1а)

R_уп = P^d_уп.

Второе равенство непосредственно вытекает из свойства 8в п.2 для произвольного отношения R. При R = P_уп получим R^d_уп = = ( P^d_уп)^d = P_уп.