Intro1l дискретная математика
.pdf
Отношения
Пусть R A B – бинарное отношение.
Область определения R:
R = fx j существует y такое, что (x; y) 2 Rg:
Область значений R:
R = fy j существует x такое, что (x; y) 2 Rg
.
|
|
1 сентября 2014 г. |
19 / 29 |
Отношения
Пусть R A B – бинарное отношение.
Область определения R:
R = fx j существует y такое, что (x; y) 2 Rg:
Область значений R:
R = fy j существует x такое, что (x; y) 2 Rg
.
Пример
Пусть A = fa; b; c; dg; B = f1; 2; 3; 7; 8; 10g и R = f(a; 1); (a; 10); (c; 2); (d; 1); (d; 7)g.
R = fa; c; dg
R = f1; 2; 7; 10g
|
|
1 сентября 2014 г. |
19 / 29 |
Отношения
Обратное отношение для бинарного отношения R X Y :
R 1 = f(y; x) j (x; y) 2 Rg
|
|
1 сентября 2014 г. |
20 / 29 |
Отношения
Обратное отношение для бинарного отношения R X Y : |
|
|||||||||||||
|
|
|
|
R 1 = f(y; x) j (x; y) 2 Rg |
|
|
|
|
||||||
Образом множества |
|
A X относительно R называется |
|
|
|
|||||||||
множество |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
R(A) = fy 2 Y j |
|
существует x 2 A такое, что |
(x; y) 2 Rg |
|
||||||||||
Прообразом |
|
B Y |
|
относительно |
R называется множество |
|
||||||||
R 1(B). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
R 1(B) = |
f |
x |
2 |
X |
j |
существует |
y |
2 |
B |
такое, что |
(x; y) |
2 |
R |
g |
|
|
|
|
|
|
|
||||||||
|
|
1 сентября 2014 г. |
20 / 29 |
Отношения
Пример
Пусть A = fa; b; c; dg; B = f1; 2; 3; 7; 8; 10g и R = f(a; 1); (a; 10); (c; 2); (d; 1); (d; 7)g. Обратное отношение для R:
R 1 = f(1; a); (10; a); (2; c); (1; d); (7; d)g:
Для X = fa; b; cg образ относительно R :
R(X ) = f1; 2; 10g:
Для Y = f1; 3; 7g прообраз относительно R :
R 1(Y ) = fa; dg:
|
|
1 сентября 2014 г. |
21 / 29 |
Отношения
Произведение отношений R A B и Q B C :
R Q =
f(x; z) j существует y 2 B такое, что (x; y) 2 R и (y; z) 2 Qg.
R Q отношение на A C .
|
|
1 сентября 2014 г. |
22 / 29 |
Отношения
Произведение отношений R A B и Q B C :
R Q =
f(x; z) j существует y 2 B такое, что (x; y) 2 R и (y; z) 2 Qg.
R Q отношение на A C .
Пример
Пусть A = fa; b; c; dg; B = f1; 2; 3; 7; 8; 10g; C = f ; ; g;
R= f(a; 1); (a; 10); (c; 2); (d; 1); (d; 8)g и Q = f(1; ); (2; ); (7; )g. Тогда
RQ = f(a; ); (c; ); (d; )g.
|
|
1 сентября 2014 г. |
22 / 29 |
Отношения эквивалентности
Бинарное отношение R на множестве A называется отношением эквивалентности, если для него выполнены следующие условия:
1) |
рефлексивность: для любого a 2 A (a; a) 2 R; |
2) |
симметричность: для любых a; b из A (a; b) 2 R , (b; a) 2 R; |
3) |
транзитивность: для любых трех элементов a; b; c из A, если |
(a; b) 2 R и (b; c) 2 R, то и (a; c) 2 R.
|
|
1 сентября 2014 г. |
23 / 29 |
Отношения эквивалентности
Бинарное отношение R на множестве A называется отношением эквивалентности, если для него выполнены следующие условия:
1) |
рефлексивность: для любого a 2 A (a; a) 2 R; |
2) |
симметричность: для любых a; b из A (a; b) 2 R , (b; a) 2 R; |
3) |
транзитивность: для любых трех элементов a; b; c из A, если |
(a; b) 2 R и (b; c) 2 R, то и (a; c) 2 R.
Классы эквивалентности для R = : для a 2 A его класс эквивалентности [a] включает все эквивалентные a элементы:
[a] = fb 2 A j R(a; b)g. Если a b, то [a] = [b] ,
а если a 6 b, то [a] \ [b] = ;:
Таким образом, разбиение A на классы эквивалентности не зависит от выбора конкретных представителей этих классов в качестве их имен.
1 сентября 2014 г. 23 / 29
Отношения эквивалентности: примеры
Свойства эквивалентности:
1) |
рефлексивность: для любого a 2 A (a; a) 2 R; |
2) |
симметричность: для любых a; b из A (a; b) 2 R , (b; a) 2 R; |
3) |
транзитивность: для любых трех элементов a; b; c из A, если |
(a; b) 2 R и (b; c) 2 R, то и (a; c) 2 R.
Пример
Отношение равенства “=” на любом множестве A:
1)a = a;
2)a = b , b = a;
3)a = b; b = c ) a = c.
Класс эквивалентности [a]= = fag.
|
|
1 сентября 2014 г. |
24 / 29 |