Задачі та вправи. І. Визначити, які з відображень є: а) частковими, б) сюр’єктивними,

І. Визначити, які з відображень є: а) частковими, б) сюр’єктивними,

в) ін’єктивними, г) взаємно однозначними. А ={ a, b, c, d }, B ={ b, c, d, f }.

1) F: A ® B, F ={< a, b >,< c, f >,< d, d >};

2) F: B ® A, F ={< c, b >,< f, a >,< d, a >,< b, c >};

3) F: B ® A, F ={< c, c >,< f, d >,< d, b >,< b, a >};

4) F: A ²® B, F ={<< a, a >, d >,<< a, b >, c >,<< c, c >, f >,<< c, b >, b >,<< c, d >, f >, << d, d >, d >, << d, a >, b >,<< b, a >, c >,<< d, c >, b >,<< c, a >, d >};

5) F: A ® B ², F ={< a,< b, c >>,< b,< c, d >>,< c,< d, d >>,< d,< c, d >>}.

II. Нехай А ={ a, b, c, d }, B ={1,2,3}. Побудувати:

1) 2-арну функцію з А у В, 2) 3-арну функцію з В у А,

3) тернарну операцію на В, 4) бінарний предикат на А,

5) матрицю розмірності 3´4 над А, 6) матрицю порядку 5 над В.

ІІІ. Побудувати:

1) функцію з N у Z, 2) 4-арну функцію з Q у R,

3) тернарну операцію на Z, 4) унарну операцію на Q,

5) бінарний предикат на R, 6) унарний предикат на N.

IV. Визначити, за яких умов:

1) n -арна функція з А у В є n -арною операцією на А,

2) n -арна функція з А у В є n -арним предикатом на А,

3) n -арна операція на А є n -арним предикатом на А,

4) бінарна операція на А є матрицею над А,

5) матриця порядку n над А є n -арною операцією на А,

6) матриця порядку n над А є n -арним предикатом на А.

V. Нехай f, g – функції. За яких умов:

1) f ^-1 є функцією, 2) f * g є взаємно однозначною функцією.

VI. Нехай існує взаємно однозначна відповідність між множинами А та В й між множинами С та D. Показати, що існує взаємно однозначна відповідність між множинами:

1) А ´ C та B ´ D, 2) А^C та B^D, 3) А È C та B È D, якщо А Ç C =Æ й B Ç D =Æ.

VII. Нехай A, B, C – множини. Побудувати взаємно однозначну відповідність між множинами:

1) A ´ B та B ´ A, 2) A ´(B ´ C) та (A ´ B)´ C,

3) (A ´ B)^C та A^C ´ B^C, 4) (A^B) ^C та A^{B ´ C},

5) A^{B È C} та A^B ´ A^C, якщо B Ç C =Æ.

VIII. Довести, що для того, щоб відношення R, задане на множинах А та В, було взаємно однозначною відповідністю між А та В, необхідно й достатньо, щоб R * R ^-1= i_А й R ^-1* R = i_В.

ІХ. Нехай F – взаємно однозначне відображення множини А на множину В, G – взаємно однозначне відображення множини В на множину С. Довести, що H = F * G є взаємно однозначне відображення А на С.

X. Побудувати приклади відображень та часткових відображень:

1) { a, b, c, d } у { g, h }, 2) {1,2,3} у { x, y, z, v, w }, 3) {1,2,3} у N,

4) N у Q, 5) Q у N, 6) Q у R,

7) R у N, 8) R у Q, 9) N ´ N у R,

10) A ={ a, b, c } у P(A).

XІ. На множинах A ={1,2,3,4,5} та B ={ a, b, c } задані відношення. Які з них є: а) функціональними, б) відображеннями А у В?

R ₁={<1, c >,<1, b >,<3, a >,<3, c >,<2, b >}, R ₂={<2, b >,<3, c >,<1, b >},

R ₃={<4, a >,<3, a >,<1, c >,<5, c >,<2, a >}, R ₄={<1, a >,<3, a >,<4, a >},

R ₅={<2, a >,<5, b >,<4, c >,<1, a >,<2, b >}, R ₆={<2, a >,<2, b >,<2, c >},

R ₇={<3, b >,<4, a >,<5, c >,<4, b >}, R ₈={<1, c >,<5, a >,<2, b },

R ₉= R ₅\ R ₈, R ₁₀={<2, a >}.

Скільки відношень існує на множинах: а) А та В? б) В та А?

Скільки існує відображень: а) А у В? б) В у А?

XII. Знайти область значень та область визначення відношення 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 =5};

4) R Í R ², R ={< x, y >| x + y £0};

5) R Í Q ², R ={< x, y >| x >0, x ´ y <3};

6) R Í R ², R ={< x, y >| x + y £0};

7) R Í R ², R ={< x, y >| 2 x ³3 y };

8) R Í[0,p]², R ={< x, y >| y ³cos x }.

XIIІ. Довести, що:

1) B ¹Æ Þ D(А ´ В)= А, 2) А ¹Æ Þ R(А ´ В)= В,

3) В ¹Æ Þ В^А ¹Æ, 4) В^А Í В (А ´ В).

XIV. Довести твердження 2-10 теoреми 11.

XV. Нехай A ÍD(F), B ÍR(F) для деякого відображення F. Довести, що:

1) A Í F ^-1(F (A)), 2) F (F ^-1(B))= B, 3) F (A)Ç B = F (A Ç F ^-1(B)),

4) F (A)Ç B =Æ Û A Ç F ^-1(B)=Æ, 5) F (A)Í B Û A Í F ^-1(B).

XVI. Нехай f: A ® B, g: B ®C – відображення, x Î A. Визначити (f * g)(x).

XVII. Довести, що для будь-якого бінарного відношення R:

1) D(R)=Æ Û R =Æ Û R(R)=Æ, 2) D(R ^-1)=R(R), 3) R(R ^-1)=D(R).

XVIIІ. Нехай F, G – (часткові) відображення A у B. Довести, що F = G Û D(F)=D(G), R(F)=R(G), для кожного елемента x з області визначення F та G F (x)= G (x).

ХІХ. Нехай задано відображення f: A * A ® A таке, що для будь-яких елементів x, y, z множини A f (x, y)= f (y, x), f (x, f (y, z))= f (f (x, y), z), f (x, x)= x. Визначимо xRy Û f (x, y)= x. Довести, що R – частковий порядок на А.

ХХ. Нехай R – бінарне відношення на n -елементній множині А. Сформулювати правила перетворення матриці відношення R на матрицю відношення: 1) R_r; 2) R_s.

ХХІ. Нехай R – перетворення множини А. Чи будуть перетвореннями множини А відношення R_r, R_s, R_t?

XХІI. Для заданого відображення множини А ={ a, b, c, d } у множину В ={1,2,3,4,5} побудувати канонічний розклад.

1) F ={< a,1>,< b,2>,< c,2>,< d,1>}, 2) F ={< a,2>,< b,2>,< c,2>,< d,2>},

3) F={<a,3>,<b,5>,<c,4>,<d,1>}, 4) F={<a,1>,<b,2>,<c,3>,<d,4>},

5) F ={< a,1>,< b,1>,< c,2>,< d,3>}, 6) F ={< a,3>,< b,5>,< c,5>,< d,5>}.