Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


¬иды бинарных отношений




ќпределение 20. Ѕинарное отношение R на множестве ј называетс€ рефлексивным, если ∀ a ј: (а;a) R (т.е. aRa).

ѕример. Ђ=їна множестве ℝ.

ќпределение 21. Ѕинарное отношение R на множестве ј называетс€ антирефлексивным, если ∀ а ј: (a;a) R.

ѕример. Ђ<їна множестве ℝ.

ќпределение 22. Ѕинарное отношение R на множестве ј называетс€ симметричным, если a,b A, из (а,b) R (b,a) R.

ѕример. Ђ∥ї на множестве всех пр€мых в пространстве, Ђ=ї на множестве ℝ.

ќпределение 23. Ѕинарное отношение R на множестве ј называетс€ антисимметричным, если a,b A, из (а,b) R и (b,a) R a=b.

ѕример. ќтношени€ ,=,<,> на множестве ℝ.

ќпределение 24. Ѕинарное отношение R на множестве ј называетс€ транзитивным, если a,b,с A, из (а,b) R и (b,с) R (а,с) R.

ѕример. Ђ∥ї на множестве всех пр€мых в пространстве, отношени€ ,=,<,> на множестве ℝ

Cвойства отношений

ѕусть = (a,a)|a A - диагональ декартова квадрата A2=A A.

Ћемма 1. ѕусть R - бинарное отношение на множестве A. “огда

1) R рефлексивно R;

2) R антирефлексивно R = .

ƒоказательство.

1) а) Ќеобходимость. ѕусть R рефлексивно. ѕокажем, что R. ƒействительно, = (а,а) |а ј R по определению 20, т.к. ∀ a ј: (а;a) R R.

б) ƒостаточность. ѕусть R. ѕокажем, что R рефлексивно. ѕусть а ј. ѕокажем, что (а,а) R. “ак как (а,а) R, т.е. (а,а) R по определению 20 R рефлексивно.

2) а) Ќеобходимость. ѕусть R антирефлексивно. ѕокажем, что R = . ƒопустим, что R (x,y) R (x,y) R и (x,y) x=y, т.е. (x,x) R Цпротиворечие с определением 21 допущение неверно R = .

б) ƒостаточность. ѕусть R = . ѕокажем, что R антирефлексивно. ƒл€ этого достаточно показать, что R удовлетвор€ет определению 21. ѕусть а ј. ѕокажем, что (а,а) R. ќт противного, допустим, что (а,а) R (a,a) R = , противоречие (а,а) R. Ћемма доказана.

ќпределение 25. ѕусть R Ц бинарное отношение между множествами A и B.

ћножество R-1 = (m,n) | (n,m) R называетс€ бинарным отношением, обратным бинарному отношению R.

Ћемма 2. ѕусть R - бинарное отношение на множестве A. “огда

1) R симметрично R-1=R;

2) R антисимметрично R R-1 .

ƒоказательство. 1) а) Ќеобходимость. ѕусть R симметрично. ћетодом встречных включений покажем, что R-1=R.

ƒокажем, что R-1 R. ƒействительно, R-1 = (m,n) | (n,m) R . Ќо так как R симметрично, то, по определению 22, из (n,m) R следует (m,n) R
R-1 R.

ƒоказательство R R-1 проводитс€ аналогично.

б) ƒостаточность. ѕусть R-1=R. ѕокажем, что R симметрично. ѕусть (n,m) R. ѕокажем, что (m,n) R. “ак как (n,m) R= R-1 (n,m) R-1 (m,n) R R симметрично.

2) а) Ќеобходимость. ѕусть R антисимметрично. ѕокажем, что R R-1 . ѕусть (x,y) R R -1 (x,y) R -1 и (x,y) R (x,y) R и (y,x) R, и так как R антисимметрично x=y.

б) ƒостаточность. ѕусть R - бинарное отношение на ј и R R-1 . ƒокажем, что R антисимметрично. ѕредположим, что это не так. “огда найдЄтс€ хот€ бы одна пара (a,b) R така€, что (b,a) R и ab (по определению R-1) (a,b) R и (a,b) R-1. “аким образом, (a,b) R R-1 a=b, противоречие предположение неверно. Ћемма доказана.

ќпределение 26. ѕусть R, S - бинарные отношени€ на множестве ј.

ћножество R.S={(x,y) | y A: (x,y) S и (y,z) R} называетс€ произведением бинарных отношений R и S.

Ћемма 3. ѕусть R - бинарное отношение на множестве A. “огда R транзитивно R.R R.





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-05-06; ћы поможем в написании ваших работ!; просмотров: 917 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

—тремитесь не к успеху, а к ценност€м, которые он дает © јльберт Ёйнштейн
==> читать все изречени€...

497 - | 507 -


© 2015-2023 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.014 с.