Контрольные вопросы и задания

1. Доказать, что:

а) _R=   R=  _R = ; б) _R^–1 =_R, _R^–1=_R;

в) _RR= R₁^-1 (_R_R); г*) _RR= R₂(_R_R);

д) если B то _AB =A; е) если A то _AB=B.

2. Доказать, что R  R^d для произвольного отношения R .

3*.  Доказать тождествоR = (R^–1 \ R)  (R  R^d).

4. Доказать включение R^–1 R(R  R^–1).

5. Какими свойствами должно обладать бинарное отношение

R, чтобы выполнялось равенство R^–1 =R ?

6. Доказать, что для любых бинарных отношений:

а) Qo(R_i ) = (Q o R_i); I I i  I б) Q o (  R_i)  (Q oR_i); i I i  I

в) (R_i)oQ = (R_i oQ); i I i  I г) (R_i)oQ  ( R_ioQ). i I i  I

7. Доказать, что для того, чтобы отношение R  AB было вза-

имно однозначным соответствием между A и B, необходимо и достаточно, чтобы R o R^–1 = R^–1 o R = .

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

Задача 1(г).

Пусть y_RR, т.е. существует такой xA, что  (x,y) 

R₁oR₂. Следовательно, найдется такое z, что (x,z)R₁ и (z,y) R₂, но это по определению означает, что z  _R и  z_R. Поэтому, z_R_R. Так как (z,y) R₂, то по определению образа множества относительно отношения, получим y R₂(_R_R). R₁^d.

2) Докажем обратное. Пусть y R₂(_R_R), тогда существует элемент x_RR, что (x,y)  R₂. Следовательно, x_Rи x_R xR следует, что найдется такой z, что (z,x)  R₁, а так как (x,y) R₂, то (z,y)  R₁oR₂. Поэтому y_RR .

Задача 3.

1) Покажем, чтоR  (R^-1 \R)  (R  R^d). Пусть (x, y)R, т.е. (x, y)R. Для пары (y, x) возможны два случая: либо (y, x)R, либо (y, x)R. В первом случае получаем, что (x, y)R^–1 и (x, y)R, следовательно, (x,y) R^–1 \ R. Для второго случая спра-ведливо (x, y)R и (x, y) R^–1 = R^d, что означает (x, y)R R^d. В обоих случаях получим, что (x, y) (R^-1 \ R)  (R  R^d).

2). Докажем теперь обратное включение. Так как (x,y) ( R^–1 \ R)  (R  R^d), то (x, y) R^–1 \R или (x, y)R  R^d. В обоих случаях то, что (x, y)R следует непосредственно из определений пересечения или разности множеств.

3. Способы задания бинарных отношений

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

1. Матричное задание. Оно используется когда А – конечное или счетное множество А = {x_i}. Тогда отношение R можно задавать с помощью матрицы R = {x_ij}, элементы которой определяются соотношением:

2. Задание с помощью графа.

Для конечного или счетного множества А отношение можно задавать с помощью графа Г(R), который является геометрическим образом бинарного отношения. Граф – фигура состоящая из точек (вершин) соединенных линиями (дугами). Вершины графа соответствуют элементам множества А, то есть x_i, а наличие дуги, соединяющей вершины x_i и x_j, означает, что (x_i, x_j)R. Чтобы подчеркнуть упорядоченность пары на дуге ставится стрелка.

Основные свойства графа.

1) Г(R^–1) получается из Г(R) изменением направления стрелок на противоположные.

2) Граф Г(АА) содержит дуги, соединяющие любую пару (x_i, x_j). Такой граф назывыется полным.

3. Задание верхними и нижними срезами.

Этот способ может быть использован для любых множеств и отношений. Пусть на множестве А задано отношение R. Верхний срез G_R(x) отношения R в точке x А - это множество элементов yА таких, что (y, x)R, т.е.

G_R(x) = { yA | (y, x)R }.

Если рассматривать R как отношение предпочтения, то G_R (x) – это множество элементов, лучших чем х.

Нижний срез H_R(x) отношения R в точке xА – это множество элементов yА, таких, что (x, y)R, т.е.

H_R(x) = { yA | (x, y)R }.

Свойства нижних и верхних срезов.

Для любого хA и любого отношения R_iAA выполняя-ются соотношения.

1. а)G_RR(x)=G_R(x)G_R(x); б) H_RR(x)=H_R(x)H_R(x)

2. a) G_R(x) = A \ G_R(x); б)H_R(x) = A \ H_R(x).

3. a) G_R^–1(x) = H_R(x); б) H_R^–1(x) = H_R(x).

4. G_AA(x) = H_AA(x) = A.

КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ

1. Пусть X = {2, 3, 4, 5, 6, 7, 8, 9}. Построить матрицу и граф следующих бинарных отношений:

а) R = { (x_i ,x_j) | x_i ,x_jX, x_i делится на x_j };

б) R = { (x_i ,x_j) | x_i ,x_jX, x_i >x_j };

в) R = { (x_i ,x_j) | x_i ,x_jX, x_i и x_j имеют общий делитель};

г) R = { (x_i ,x_j) | x_i ,x_jX, x_i x_j 15};

д) R = { (x_i ,x_j) | x_i ,x_jX,  n: x_j =x_i ⁿ }.

2*. Для бинарных отношений R, определенных в задаче 15 п.1 построить множества G_R(x) и H_R(x).

3. Пусть x=(x₁,x₂) и R = { (x,y) | , x,yR, (x,y)  k}. По-

строить верхний и нижний срезы отношения R, если:

а) (x,y) = ;б) (x,y) = max | x_i  y_i |; i  i

в) (x,y) = | x_i  y_i |. i