Задачі та вправи

І. Нехай R,Q,ТA², A={1,2,3,4,5,6,7}, R={<2,1>,<2,2>,<3,5>,<6,3>}, Q={<1,3>,<1,5>,<4,3>,<5,7>,<2,4>}, T={<4,5>,<1,6>,<5,5>,<4,1>, <5,7>}. Обчислити вирази:

1) (RQ)(QR), 2) (TQ)R^-1, 3) (T\Q)Q^-1,

4) (QT)\R, 5) T^-1((QR)T), 6) (Q(R\T))T,

7) (Q\R)Q, 8) (T^-1R)Q^-1, 9) T(QR),

10) (QR)R, 11) (R\T)R, 12) (QT)^-1(T\R),

13) ((QT)^-1T)\R, 14) (TQR), 15) (TQ)R,

16) (Q^-1)(RT), 17) (T^-1)(QT), 18) (QR)T,

19) (RR)Q, 20) (Q\R)T, 21) (QR)T,

22) (R\Q)(TT), 23) (TQ^-1)\(RR^-1), 24) (QQ)(T^-1),

25) RRR, 26) TTT, 27) QQQ,

28) RQR, 29) TQT, 30) QTQ.

II. Нехай на множині N задані бінарні відношення:

R₁={<x,y>| x,y – парні числа},

R₂={<x,y>| x парне, y непарне},

R₃={<x,y>| x,y – непарні числа},

R₄={<x,y>| x непарне, y парне}.

Обчислити: R_i^-1, R_iR_j, R_i, R_iR_j (i,j{1,2,3,4}).

III. Знайти R^-1, RR, RR^-1, R^-1R для відношень:

1) RN², R={<x,y>| x ділить y};

2) RN², R={<x,y>| y ділить x};

3) RR², R={<x,y>| x+y0};

4) RR², R={<x,y>| 2x3y};

5) R[0,]², R={<x,y>| ycosx}.

IV. Нехай на множині людей задані відношення R={<x,y>| x – брат y}, Q={<x,y>| x – помічник y}. Опишіть відношення RQ, RQ, R\Q.

V. Нехай відношення <, >, ,  визначені на множині N звичайним чином. Чи правильні рівності:

1) << = <, 2)  = , 3) < = <, 4)  = N²,

5)  = <, 6) < = , 7) <> = N², 8) > = >?

VI. Довести рівності 1-3, 5-9 теореми 5.

VII. Нехай R₁, R₂, Q – бінарні відношення, задані на множині А, R₁R₂. Довести, що:

1) QR₁  QR₂, 2) R₁Q  R₂Q, 3) R₁^-1  R₂^-1.

VIII. Нехай R, R₁, R₂, R₃ – бінарні відношення на множині А. Довести, що:

1) R₁(R₂R₃)(R₁R₂)(R₁R₃), 2) (R₁R₂)R₃(R₁R₃)(R₂R₃).

IX. Нехай RA². Довести, що R=i_A  RR₁=R₁R=R для довільного бінарного відношення R₁ на множині А.

X. Для яких бінарних відношень R виконується R^-1=R?

Відображення

Відношення R, задане на множинах А та В, називається функціо-нальним, якщо для кожного елемента xА існує не більше одного еле-мента yВ такого, що <x,y>R. Іншими словами, у функціональному відношенні R, заданому на множинах А та В, кожен елемент множини А може бути (першим) компонентом не більш, як однієї пари, що належить R.

Наприклад, відношення R={<1,b>,<3,a>,<4,b>}, задане на множи-нах A={1,2,3,4} та B={a,b,c}, є функціональним, оскільки кожен з еле-ментів 1,3,4 з множини А є першим компонентом лише однієї пари відношення R, а елемент 2 з множини А не є першим компонентом жодної пари відношення R. Відношення Q={<1,a>,<1,b>,<2,c>}, задане на тих самих множинах А та В, не функціональне, тому що елемент 1 з множини А зустрічається двічі (тобто більше одного разу) на першому місці у парах, які належать Q. Не функціональними є також відношення < та  на множині N, оскільки для кожного числа n з N існує не одне число mN таке, що n<m й nm.

Нехай R – відношення, задане на множинах А та В. Назвемо областю визначення відношення R (позначається D(R)) множину {x| xA, існує yВ такий, що <x,y>R}. Областю значень відношення R (позначається R(R)) назвемо множину {y| yB, існує такий xA, що <x,y>R}.

Нехай, наприклад, RAB, A={1,2,3,4}, B={1,3,5}, R={<1,1>, <1,5>,<2,3>,<3,5>,<3,3>}. Тоді D(R)={1,2,3}, R(R)={1,3,5}.

Функціональне відношення F на множинах А та В назвемо відображенням множини А у множину В (або функцією з А у В), якщо D(F)=А. Функціональне відношення F на множинах А та В назвемо частковим відображенням множини А у множину В (або частковою функцією з А у В), якщо D(F)А. Позначатимемо (часткове) відобра-ження F множини А у множину В через F: АВ. Якщо <a,b>F, то елемент b називають образом елементу а, елемент а – прообразом елементу b при відображенні F й пишуть b=F(a). Множина усіх відображень А у В позначається В^А.

Часто відображення множини A у множину B задається у вигляді F(x)=t(x), де xA, t(x) – деякий вираз. Наприклад, відображення F:NN, F={<x,y>| x,yN, y=2x}, можна задати у вигляді F(x)=2x.

Відображення множини А у множину А називають перетворенням множини А.

Через F^-1(b) позначимо множину {a| aA, F(a)=b}; F^-1(b) назива-ється повним прообразом елементу b при відображенні F. Нехай F:АВ й ХА. Образом множини Х при відображенні F (позначається F(Х)) назвемо множину {y| yB, y=F(x) для деякого x з X}.

Наведемо приклади відображень. Відношення F={<1,a>,<2,a>, <3,c>,<4,d>,<5,d>}, задане на множинах А={1,2,3,4,5} та В={a,b,c,d,e}, є відображенням А у В, тому що F функціональне й D(F)={1,2,3,4,5}=А. F^-1(a)={1,2}, F^-1(b)=, F^-1(c)={3}, F^-1(d)={4,5}, F^-1(e)=, F(A)={a,c,d}, F({1,2,3})={a,c}. Відношення Q={<2,c>,<3,d>,<5,b>}, задане на тих самих множинах, є частковим відображенням А у В, тому що Q функціональне й D(Q)={2,3,5}А.

Зауважимо, що коли F (F:AB) – відображення, то відношення F^-1 може не бути відображенням. Розглянемо, наприклад, множини A={1,2}, B={a,b} та відображення F={<1,a>,<2,a>} А у В. F^-1={<a,1>,<a,2>}. F^-1 – не функціональне відношення на множинах В та А, отже, F^-1 не є відображенням В у А.

Якщо А=А₁…А_n, то (часткове) відображення F: АВ назива-ють (частковим) відображенням множини А₁…А_n у множину В (або (частковою) функцією з А₁…А_n у В).

Нехай, наприклад, A₁={1,2,3}, A₂={2,4}, A₃={a,b}, B={d,f,g}. Від-ношення F={<1,4,a,f>,<2,2,a,d>,<1,2,b,f>,<3,2,a,d>}, задане на множинах А₁, А₂, А₃, В, є частковим відображенням А₁А₂А₃ у В. Відношення R={<1,2,a,d>,<1,2,a,f>,<2,4,b,g>}, задане на тих самих множинах, не функціональне на множинах А₁А₂А₃ та В, оскільки для елементу <1,2,a> множини А₁А₂А₃ існує два (тобто більше одного) елемента у з множини В (це елементи d та f) таких, що <1,2,a,у>В, отже, R не є відображенням А₁А₂А₃ у В.

Теорема 6. Довести, що для будь-якої функції F виконується:

1) F(AB)=F(A)F(B), 2) F(AB)  F(A)F(B),

3) F(A)\F(B)=F(A\B), 4) AB  F(A)F(B),

5) F(A)=  AD(F)=, 6) F^-1(AB)=F^-1(A)F^-1(B),

7) F^-1(AB)=F^-1(A)F^-1(B), 8) F^-1(A\B)=F^-1(A)\F^-1(B),

9) AB  F^-1(A)F^-1(B), 10) F^-1(A)=  AR(F)=.

Доведемо перше твердження. Нехай xF(AB). Тоді у множині AB існує такий елемент у, що х=F(y); yA або уВ. Розглянемо перший з цих випадків: yA  xF(A)  xF(A)F(B). У випадку yB маємо: yВ  xF(B)  xF(A)F(B). Отже, F(AB)F(A)F(B). Нехай тепер хF(A)F(B). Тоді xF(A) або xF(B). У випадку xF(A) у множині А існує такий елемент у, що х=F(y), але уАВ й тоді хF(AB). Якщо xF(B), то у множині В існує такий елемент z, що х=F(z). Оскільки zB  zAB, то хF(AB). Таким чином, F(A)F(B)F(AB). Отже, F(AB)=F(A)F(B).