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

І. Класифікувати відношення, задані на множині людей, тобто для кож-ного відношення визначити, є воно симетричним (антисиметричним, асиметричним, рефлексивним, антирефлексивним, транзитивним) чи ні.

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 – клієнти одного банку}.

ІІ. Класифікувати відношення, задані на числових множинах.

1) R={<x,y>: x-y – непарне число}, RZ²,

2) R={<x,y>: x+y5}, RZ²,

3) R={<x,y>: x²+y²=1}, RR²,

4) R={<x,y>: x-y>2}, RN²,

5) R={<x,y>: x,y – невід’ємні цілі числа, x-y>2}, RZ²,

6) R={<x,y>: x-y кратне 3}, RN²,

7) R={<x,y>: x,y – числа, які не мають спільних дільників (крім 1)}, R(N⁺)²,

8) R={<x,y>: xy>3}, RN²,

9) R={<x,y>: x=3y}, R(N⁺)²,

10) R={<x,y>: x=y²}, RR²,

11) R={<x,y>: x,y – числа з однаковими чисельниками й різними знаменниками}, RQ²,

12) R={<x,y>: x+y=0}, RR²,

13) R={<x,y>: 5x+y ділиться на 3}, R(N⁺)²,

14) R={<x,y>: x-y<1}, RR²,

15) R={<x,y>: x+y0}, RR²,

16) R={<x,y>: x>y}, RR²,

17) R={<x,y>: x,y – цілі числа, 2x+y – парне число}, RR²,

18) R={<x,y>: x,y – числа з однаковими цифрами у старшому розряді}, R(N⁺)²,

19) R={<x,y>: x=y²-1}, RR²,

20) R={<x,y>: x+y+1 – парне число}, R(N⁺)²,

21) R={<x,y>: x,y – числа, які мають хоча б одну спільну цифру}, R(N⁺)²,

22) R={<x,y>: x/y3}, R(N⁺)²,

23) R={<x,y>: x,y – числа різної парності}, R(N⁺)²,

24) R={<x,y>: х+y1}, RR².

ІІІ. Класифікувати відношення.

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}. Чи виконується для нього співвідношення R²=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 задане на булеані деякої множини.

IV. Побудувати на деякій множині А бінарне відношення, яке є:

1) рефлексивним, симетричним, не транзитивним;

2) рефлексивним, антисиметричним, не транзитивним;

3) рефлексивним, транзитивним, не симетричним;

4) антисиметричним, транзитивним, не рефлексивним;

5) симетричним, транзитивним, не рефлексивним;

6) не рефлексивним, не антирефлексивним, транзитивним;

7) антирефлексивним, асиметричним, не транзитивним;

8) антирефлексивним, симетричним, не транзитивним,

9) симетричним, не рефлексивним, не антирефлексивним,

10) симетричним, не рефлексивним, не транзитивним,

11) рефлексивним, не антисиметричним, транзитивним,

12) антирефлексивним, не симетричним, транзитивним,

13) симетричним, транзитивним, антисиметричним,

14) симетричним, рефлексивним, антисиметричним,

15) не рефлексивним , симетричним, антисиметричним.

V. Нехай R₁, R₂ – рефлексивні відношення на множині А. Довести, що: 1) рефлексивними на А є відношення R₁R₂, R₁R₂, R₁^-1, R₁R₂,

2) R₁R₂  R₁R₂.

VI. Нехай R₁, R₂ – антирефлексивні відношення на множині А. Довести, що антирефлексивними на А є відношення R₁R₂, R₁R₂, R₁^-1. Чи є ан-тирефлексивним на А відношення R₁R₂?

VІІ. Нехай R₁, R₂ – симетричні відношення на множині А. Довести, що: 1) симетричними на А є відношення R₁R₂, R₁R₂, R₁^-1, R₁R₁^-1;

2) відношення R₁R₂ симетричне на А  R₁R₂=R₂R₁.

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

1) антисиметричними на А є відношення R₁R₂ та R₁^-1;

2) відношення R₁R₂ антисиметричне на А  R₁R₂^-1  i_A.

IX. Нехай R₁, R₂ – асиметричні відношення на множині А. Чи є асимет-ричними на А відношення: R₁R₂, R₁R₂, R₁^-1, R₁R₂?

X. Нехай R₁, R₂ – транзитивні відношення на множині А. Чи є транзи-тивними на А відношення: R₁R₂, R₁R₂, R₁^-1, R₁R₂?

ХІ. Нехай R – бінарне відношення на А. Довести, що:

1) якщо R асиметричне, то R антирефлексивне,

2) якщо R асиметричне, то R антисиметричне,

3) якщо R антирефлексивне та транзитивне, то R асиметричне,

4) якщо R симетричне, транзитивне й для кожного елемента х з А існує елемент у з А такий, що <x,y>R, то R рефлексивне,

5) якщо R симетричне та антисиметричне, то R транзитивне,

6) якщо R рефлексивне та антисиметричне, то RR^-1=і_А.