І. Чи існують на множині {1,2,3,4} такі два різні відношення R та S, що: 1) Rr=Sr; 2) Rs=Ss; 3) Rt=St? Відповіді обгрунтувати.
ІІ. Побудувати декартів добуток множин
1) {1,2,Æ} та {2,4}, 2) {а,с,е}, {с,а},
3) {1},{2,3} та {1,2}, 4) {а,{х},х} та {і,с},
5) {х,Î,с} та {Х,Í,М}, 6) {3,+,5} та {2,´,4},
7) {12,34} та {ас,іе}, 8) {Ç,È} та {{Х},{А}},
9) {a,b,c}, Æ та {1,2}, 10) {2,3},{3,4} та {2,3},
11) {1,2}, {Æ} та {{Æ}}, 12) {x,{x}}, {¹} та {{}}.
IІІ. Чи існують такі множини А, В, С, що А´(В´С)≠(А´В)´С?
ІV. Довести, що коли множини А, В, С, D непорожні, то:
1) АÍВ й СÍD Û А´СÍВ´D, 2) А=В й С=D Û А´С=В´D.
V. Довести, що:
1) (АÇВ)´(СÇD)=(А´С)Ç(В´D),
2) (А´В)È(С´D)Í(АÈС)´(ВÈD),
3) А´(ВÈС)=(А´В)È(А´С),
4) (АÈВ)´(СÈD)=(А´С)È(В´С)È(А´D)È(В´D),
5) (АВ)´С=(А´С)(В´С),
6) А´(ВС)=(А´В)(А´С),
7) А´В=(А´D)Ç(С´В), де АÍС, ВÍD,
8) U2(А´В)=[(UA)´U]È[U´(UB)],
9) A≠Æ, B≠Æ, (A´B)È(B´A)=C´D Þ A=B=C=D.
VI. Навести приклад таких множин A, B, C, D, для яких (AÈB)´(CÈD)¹ ¹(A´C)È(B´D).
VII. Чи існують такі множини А, В, С, що А´В=А´В´С?
VIIІ. Побудувати приклади унарних, бінарних та тернарних відношень, заданих на множині {1,2,3,4,5,6}.
IX. Побудувати приклади унарних, бінарних та тернарних відношень, заданих на множині:
1) N, 2) Z, 3) Q,
4) R, 5) людей, 6) тварин,
7) птахів, 8) квітів, 9) країн світу,
10) учнів школи, 11) днів тижня, 12) видів спорту.
X. Нехай А={1,2,3,4,5,6,7,8,9,10}, RÍА2. Записати відношення R у явному вигляді:
1) R={<x,y>| x,yÎA, x – дільник y, х£5},
2) R={<x,y>| x,yÎA, x<y, х£2},
3) R={<x,y>| x,yÎA, x£y+1, y>7},
4) R={<x,y>| x,yÎA, x–y ділитьcя на 3},
5) R={<x,y>| x,yÎA, x+y ділитьcя на 5},
6) R={<x,y>| x,yÎA, x>y, x+y<6},
7) R={<x,y>| x,yÎA, x парне, y непарне},
8) R={<x,y>| x,yÎA, x просте, y складене},
9) R={<x,y>| x,yÎA, x кратне 5, y<5},
10) R={<x,y>| x,yÎA, x,y не мають спільних дільників, відмінних від 1}.
XI. Нехай Х=P({а,б,в}). Знайти усі елементи відношень Í, Ì, Ê, É, Ë на Х.
XIІ. Нехай R,Q,ТÍA2, 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) (TQ¢)*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¢.
XIII. Нехай на множині N задані бінарні відношення:
R1={<x,y>| x,y – парні числа},
R2={<x,y>| x парне, y непарне},
R3={<x,y>| x,y – непарні числа},
R4={<x,y>| x непарне, y парне}.
Обчислити: Ri-1, Ri*Rj, Ri¢, RiÇRj (i,jÎ{1,2,3,4}).
XIV. Знайти R-1, R*R, R*R-1, R-1*R для відношень:
1) RÍN2, R={<x,y>| x ділить y};
2) RÍN2, R={<x,y>| y ділить x};
3) RÍR2, R={<x,y>| x+y£0};
4) RÍR2, R={<x,y>| 2x³3y};
5) RÍ[0,p]2, R={<x,y>| y³cosx}.
XV. Нехай на множині людей задані відношення R={<x,y>| x – брат y}, Q={<x,y>| x – помічник y}. Опишіть відношення RÈQ, RÇQ, RQ.
XVI. Нехай відношення <, >, £, ³ визначені на множині N звичайним чином. Чи правильні рівності:
1) <*< = <, 2) £*£ = £, 3) £*< = <, 4) £*³ = N2,
5) ³*£ = <, 6) ³*< = Æ, 7) <*> = N2, 8) >*£ = >?
XVII. Довести рівності 1-3, 5-9 теореми 5.
XVIII. Нехай R1, R2, Q – бінарні відношення, задані на множині А, R1ÍR2. Довести, що:
1) Q*R1 Í Q*R2, 2) R1*Q Í R2*Q, 3) R1-1 Í R2-1.
XIX. Нехай R, R1, R2, R3 – бінарні відношення на множині А. Довести, що:
1) R1*(R2ÇR3)Í(R1*R2)Ç(R1*R3), 2) (R1ÇR2)*R3Í(R1*R3)Ç(R2*R3).
XX. Нехай RÍA2. Довести, що R=iA Û R*R1=R1*R=R для довільного бінарного відношення R1 на множині А.
XXI. Для яких бінарних відношень R виконується R-1=R¢?
XXIІ. Класифікувати відношення, задані на множині людей, тобто для кожного відношення визначити, є воно симетричним (антисиметричним, асиметрич-ним, рефлексивним, антирефлексивним, транзитивним) чи ні.
1) R={<x,y>: x,y – підлітки, які мають спільні захоплення},
2) R={<x,y>: x – сестра y},
3) R={<x,y>: x,y – люди, які мають спільних знайомих},
4) R={<x,y>: x,y – учні різних шкіл},
5) R={<x,y>: x,y – уболівальники різних спортивних команд},
6) R={<x,y>: x,y – діти, що мешкають в одному домі},
7) R={<x,y>: x,y – люди, які працюють на одному підприємстві},
8) R={<x,y>: x,y – люди, яким подобаються одні й ті ж страви},
9) R={<x,y>: x – мати y},
10) R={<x,y>: x,y – двоюрідні брати},
11) R={<x,y>: x,y – клієнти одного банку}.
XXIІІ. Класифікувати відношення, задані на числових множинах.
1) R={<x,y>: x-y – непарне число}, RÍZ2,
2) R={<x,y>: x+y£5}, RÍZ2,
3) R={<x,y>: x2+y2=1}, RÍR2,
4) R={<x,y>: x-y>2}, RÍN2,
5) R={<x,y>: x,y – невід’ємні цілі числа, x-y>2}, RÍZ2,
6) R={<x,y>: x-y кратне 3}, RÍN2,
7) R={<x,y>: x,y – числа, які не мають спільних дільників (крім 1)}, RÍ(N+)2,
8) R={<x,y>: x´y>3}, RÍN2,
9) R={<x,y>: x=3y}, RÍ(N+)2,
10) R={<x,y>: x=y2}, RÍR2,
11) R={<x,y>: x,y – числа з однаковими чисельниками й різними знаменни-ками}, RÍQ2,
12) R={<x,y>: ½x½+y=0}, RÍR2,
13) R={<x,y>: 5x+y ділиться на 3}, RÍ(N+)2,
14) R={<x,y>: ½x-y½<1}, RÍR2,
15) R={<x,y>: ½x½+y¹0}, RÍR2,
16) R={<x,y>: ½x½>½y½}, RÍR2,
17) R={<x,y>: x,y – цілі числа, 2x+y – парне число}, RÍR2,
18) R={<x,y>: x,y – числа з однаковими цифрами у старшому розряді}, RÍ(N+)2,
19) R={<x,y>: x=y2-1}, RÍR2,
20) R={<x,y>: x+y+1 – парне число}, RÍ(N+)2,
21) R={<x,y>: x,y – числа, які мають хоча б одну спільну цифру}, RÍ(N+)2,
22) R={<x,y>: x/y³3}, RÍ(N+)2,
23) R={<x,y>: x,y – числа різної парності}, RÍ(N+)2,
24) R={<x,y>: |х+y|>1}, RÍR2.
XXІV. Класифікувати відношення.
1) R={<1,a>,<b,2>,<1,b>,<1,1>,<a,2>}, R задано на множині {1,a,b,2},
2) R={<1,3>, <4,2>, <1,1>, <3,2>, <3,1>, <4,4>, <2,4>, <2,2>, <2,3>, <3,3>}, R задано на множині {1,2,3,4,5},
3) R={<a,a>,<b,b>,<a,b>,<a,c>,<b,a>,<c,a>}, R задано на множині {a,b,c},
4) R={<x,y>: x,y – книги, видані в одному році}, R задано на множині книг,
5) R={<1,2>,<1,3>,<2,4>,<3,2>,<3,1>,<3,3>}, R задано на множині {1,2,3, 4}. Чи виконується для нього умова R=R-1?
6) R={<1,2>,<2,5>,<3,3>,<4,1>,<5,3>,<3,2>}, R задано на множині {1,2,3,4,5}. Чи виконується для нього співвідношення R2=R?
7) R={<a,d>, <b,b>, <b,c>, <d,a>, <c,b>, <a,c>, <d,d>, <c,a>}, R задано на множині {a,b,c,d},
8) R={<x,y>: x,y – книги різних авторів}, R задано на множині книг,
9) R={<x,y>: x,y – трикутники на площині, які мають рівні периметри}, R задано на множині геометричних фігур,
10) R={<x,y>: x,y – країни, розташовані на різних континентах}, R задано на множині країн світу,
11) R={<x,y>: x,y – картини одного жанру}, R задано на множині картин,
12) R={<x,y>: x,y – міста, між якими немає прямого автомобільного сполучення}, R задано на множині міст України,
13) R={<x,y>: x,y – трамваї, що обслуговують один маршрут}, R задано на множині одиниць міського електротранспорту,
14) R={<x,y>: слово x зустрічається в орфографічному словнику раніше слова y}, R задано на множині слів орфографічного словника,
15) R={<x,y>: x,y – тварини одного виду}, R задано на множині тварин,
16) R={<x,y>: x,y – слова в орфографічному словнику, між якими є принаймні два слова}, R задано на множині слів орфографічного словника,
17) R={<x,y>: x,y – слова в орфографічному словнику, які знаходяться поруч}, R задано на множині слів орфографічного словника,
18) R={<x,y>: x,y – слова у словнику, які починаються з однієї літери}, R задано на множині слів орфографічного словника,
19) R={<x,y>: x,y – слова в орфографічному словнику, між якими є більше п’яти слів}, R задано на множині слів орфографічного словника,
20) R={<x,y>: x,y – слова у словнику, що починаються різними літерами}, R задано на множині слів орфографічного словника,
21) R={<x,y>: x,y – костюми різного кольору}, R заданo на множині костюмів, що належать одній особі,
22) R={<x,y>: x,y – депутати від різних округів}, R задано на множині депутатів одного скликання,
23) R={<x,y>: x,y – страви, що містять цукор}, R задано на множині страв,
24) R={<x,y>: x,y – музичні твори одного композитора}, R задано на множині музичних творів,
25) R={<A,B>: AÇB=Æ}, R задано на булеані деякої множини Х,
26) R={<x,y>: x,y – множини, що мають принаймні два спільних елемента}, R задано на булеані деякої множини Х,
27) R={<A,B>: A та B мають один спільний елемент}, R задано на булеані деякої множини Х,
28) R={<x,y>: x,y – учні, які навчаються в одному класі, але вивчають різні іноземні мови}, R задано на множині учнів однієї школи,
29) R={<x,y>: x,y – міста України, у яких є промислові підприємства одного й того ж профілю}, R задано на множині міст України,
30) R={<x,y>: x,y – книги, видані одним видавництвом у різні роки}, R заданo на множині книг, надрукованих в Україні,
31) R={<x,y>: x,yÎ{1,3,4,6}, x+y<12}, R задано на множині {1,2,3,4,5,6,7},
32) R={<x,y>: x-y£90°}, R задано на множині кутів,
33) R={<x,y>: x+y>180°}, R задано на множині кутів,
34) R={<x,y>: x+y=90°}, R задано на множині кутів,
35) R={<x,y>: x,y – олівці різних кольорів}, R задано на множині олівців,
36) R={<x,y>: x,y – маршрути транспорту, які мають спільну частину}, R задано на множині маршрутів міського громадського транспорту,
37) R={<x,y>: x,y – чотирикутники на площині, які мають хоча б одну пару рівних сторін}, R задано на множині чотирикутників на площині,
38) R={<x,y>: x,y – матриці одного порядку}, R задано на множині квадратних матриць над множиною чисел Х,
39) R={<x,y>: x,y – столиці різних країн світу}, R задано на множині міст Землі,
40) R={<x,y>: x,y – зірки одного сузір’я}, R задано на множині зірок Всесвіту,
41) R={<x,y>: x,y – чоловічі імена}, R задано на множині імен людей,
42) R={<x,y>: x,y – множини різної потужності}, R задане на булеані деякої множини,
43) R={<x,y>: x не є власною підмножиною y}, R задане на булеані деякої множини.
XXV. Побудувати на деякій множині А бінарне відношення, яке є:
1) рефлексивним, симетричним, не транзитивним;
2) рефлексивним, антисиметричним, не транзитивним;
3) рефлексивним, транзитивним, не симетричним;
4) антисиметричним, транзитивним, не рефлексивним;
5) симетричним, транзитивним, не рефлексивним;
6) не рефлексивним, не антирефлексивним, транзитивним;
7) антирефлексивним, асиметричним, не транзитивним;
8) антирефлексивним, симетричним, не транзитивним,
9) симетричним, не рефлексивним, не антирефлексивним,
10) симетричним, не рефлексивним, не транзитивним,
11) рефлексивним, не антисиметричним, транзитивним,
12) антирефлексивним, не симетричним, транзитивним,
13) симетричним, транзитивним, антисиметричним,
14) симетричним, рефлексивним, антисиметричним,
15) не рефлексивним , симетричним, антисиметричним.
XXVI. Нехай R1, R2 – рефлексивні відношення на множині А. Довести, що: 1) рефлексивними на А є відношення R1ÈR2, R1ÇR2, R1-1, R1*R2,
2) R1ÈR2 Í R1*R2.
XXVII. Нехай R1, R2 – антирефлексивні відношення на множині А. Довести, що антирефлексивними на А є відношення R1ÈR2, R1ÇR2, R1-1. Чи є антирефлексивним на А відношення R1*R2?
XXVІIІ. Нехай R1, R2 – симетричні відношення на множині А. Довести: 1) симетричними на А є відношення R1ÈR2, R1ÇR2, R1-1, R1*R1-1;
2) відношення R1*R2 симетричне на А Û R1*R2=R2*R1.
XXIX. Нехай R1, R2 – антисиметричні відношення на множині А. Довести:
1) антисиметричними на А є відношення R1ÇR2 та R1-1;
2) відношення R1ÈR2 антисиметричне на А Û R1ÇR2-1 Í iA.
XXX. Нехай R1, R2 – асиметричні відношення на множині А. Чи є асиметричними на А відношення: R1ÈR2, R1ÇR2, R1-1, R1*R2?
XXXI. Нехай R1, R2 – транзитивні відношення на множині А. Чи є транзитивними на А відношення: R1ÈR2, R1ÇR2, R1-1, R1*R2?
ХXXIІ. Нехай R – бінарне відношення на А. Довести, що:
1) якщо R асиметричне, то R антирефлексивне,
2) якщо R асиметричне, то R антисиметричне,
3) якщо R антирефлексивне та транзитивне, то R асиметричне,
4) якщо R симетричне, транзитивне й для кожного елемента х з А існує елемент у з А такий, що <x,y>ÎR, то R рефлексивне,
5) якщо R симетричне та антисиметричне, то R транзитивне,
6) якщо R рефлексивне та антисиметричне, то RÇR-1=іА.
XXXIIІ. Які з відношень завдань XXVIІ-XXІX є відношеннями еквівалентності? Для кожного відношення еквівалентності визначити, яке розбиття воно породжує.
XXXІV. Чи є відношеннями еквівалентності відношення:
1) RmÍN2, m>1, Rm={<a,b>| (a-b) ділиться на m},
2) ТÍ(N´N)2, <a,b>Т<c,d> Û a+d=b+c,
3) SÍ(N´N)2, <a,b>S<c,d> Û (ad=bc, b¹0, d¹0) або (a=c, b=d=0),
4) WÍR2, aWb Û (a-b) – раціональне число.
XXXV. Побудувати відношення еквівалентності на множині:
1) {Æ,a,s,r,t},
2) книг університетської бібліотеки,
3) слів, що знаходяться на одній сторінці деякої книги,
4) мешканців одного будинку,
5) раціональних чисел,
6) житлових будинків Києва,
7) слів орфографічного словника,
8) вищих навчальних закладів Києва,
9) читачів однієї бібліотеки,
10) квадратних матриць порядку n над деякою множиною Р,
11) точок площини,
12) N2,
13) паралелограмів на плошині,
14) парних цілих чисел,
15) непарних натуральних чисел,
16) літер українського алфавіту.
XXXVI. Нехай R1, R2 – відношення еквівалентності на А. Довести, що:
1) R1ÇR2 – відношення еквівалентності на А,
2) R1-1 – відношення еквівалентності на А,
3) R1*R2 є відношенням еквівалентності на А Û R1*R2=R2*R1,
4) R1ÈR2 є відношенням еквівалентності на А Û R1ÈR2=R1*R2,
5) (R1)¢ не є відношенням еквівалентності.
XXXVII Нехай R1, R2 – відношення еквівалентності на А. Довести, що
1) R1*R1=A2 Û R1=A2, 2) R1*R2=A2 Û R2*R1=A2.
XXXVIII. Довести, що R є відношенням еквівалентності на А Û (R*R-1)ÈiA=R.
XXXIX. Нехай R є транзитивне та симетричне відношення на деякій множині А й D(R)ÈR(R)=А. Довести, що R – відношення еквівалентності на А.
XL. Нехай R – рефлексивне та транзитивне відношення на деякій множині А. Довести, що RÇR-1 є відношення еквівалентності.
XLІ. На даній множині А задати принаймні два відношення еквівалентності й побудувати відповідні фактор-множини.
1) А={a,b,c,d}, 2) A={!,~,$,%,*,&}, 3) A={1,2,3,a,b,c,d},
4) A=N, 5) A=Z, 6) A=Q,
7) A=R, 8) A =({1,2,3})2, 9) A=N2,
10) A=NÈN2, 11) A={3k| kÎZ}, 12) A={<x,y>|xÎN,yÎZ},
13) A – множина людей.
XLІІІ. Скільки можна побудувати двоелементних фактор-множин для множини, що має n елементів?
XLIV. Описати фактор-множини, що визначаються відношеннями еквівалентності із завдань XXXІX та XL.
XLV. Для заданого на множині A={a,b,c,d,e} відношення R побудувати рефлексивне, симетричне, транзитивне замикання, а також Rrst та A/Rrst.
1) R={<a,b>,<c,c>,<d,a>,<d,d>}, 2) R={<b,c>,<c,b>,<a,a>,<b,b>},
3) R={<d,c>,<a,a>,<c,c>,<d,d>}, 4) R={<a,c>,<b,a>,<b,b>,<a,b>},
5) R={<c,b>,<c,d>,<c,a>,<c,c>}, 6) R={<a,d>,<a,a>,<d,b>,<d,c>},
7) R={<c,d>,<c,b>,<b,a>,<d,b>}, 8) R={<a,c>,<b,d>,<d,a>,<c,b>},
9) R={<d,d>,<a,d>,<d,c>,<b,a>}, 10) R={<b,c>,<d,c>,<c,c>,<c,a>}.
XLVI. Довести, що відношення RÈR2È…ÈRn симетричне для будь-якого n³1, якщо R симетричне.
XLVІІ. Нехай R – бінарне відношення на множині А. Довести, що:
1) якщо R рефлексивне, то R=Rr;
2) якщо R симетричне, то R=Rs;
3) якщо R транзитивне, то R=Rt.