Свойства бинарных отношений
Определение 20. Бинарное отношение R на множестве А называется рефлексивным, если для любого a А: (а;a) R (т.е. aRa). Пример. //, =. Определение 21. Бинарное отношение R на множестве А называется антирефлексивным, если для любого а А: (a;a) R . Определение 22.Бинарное отношение R на множестве А называется симметричным, если из (а,b) R (b,a) R, a,b A. Пример. //,= Определение 23.Бинарное отношение R на множестве А называется антисимметричным, если из (а,b) R и (b,a) R a=b, a,b A. Пример. ,=,<,> . Определение 24.Бинарное отношение R на множестве А называется транзитивным, если из (а,b) R и (b,с) R (а,с) R, a,b,с A. Пример.//,<,>,=. Пусть = (a,a)|a A - диагональ декартова квадрата A2=A A. Лемма 1. Пусть R - бинарное отношение на множестве A. Тогда 1) R рефлексивно R; 2) R антирефлексивно R = . Доказательство. 1) а) Необходимость. Пусть R рефлексивно. Покажем, что R. Действительно, = (а,а) |а А R (по определению 20) 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 симметрично) R-1 R. Доказательство включения R R-1 проводится аналогично. б) Достаточность. Пусть R-1=R. Покажем, что R симметрично. Пусть (n,m) R. Покажем, что (m,n) R. Так как (n,m) R= R-1 (m,n) R R симметрично. 2) а) Необходимость. Покажем, что 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 (по определению R-1) (a,b) R-1 и (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-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (334)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |