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

 

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

в) ін’єктивними, г) взаємно однозначними. А={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>| 2x³3y};

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

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>}.