бинарные отношения. Лекция. Бинарные отношения и операции над ними
![]()
|
Лекция. Бинарные отношения и операции над нимиКлючевые слова: бинарное отношение, пересечение, объединение, произведение бинарных отношений. 1 Понятие бинарного отношения В математике для обозначения связи между предметами или понятиями используют термин «отношение». Например, отношение «меньше» в множестве действительных чисел, отношение подобия треугольников, отношения родства и старшинства в множестве людей и др. Это примеры отношений между двумя элементами (понятиями) так называемых бинарных отношений. Определение. Бинарным отношением, определенным на паре множеств А и В, называется любое подмножество их декартова произведения А × В. Если ![]() ![]() ![]() ![]() ![]() Если ![]() Два бинарных отношения R1 и R2 равны тогда и только тогда, когда любая пара (а, b) из R1 принадлежит вместе с тем и R2, и обратно: любая пара (а, b) из R2 принадлежит и R1. Аналогично, ![]() Определение. Пусть ![]() ![]() ![]() ![]() ![]() ![]() ![]() Пусть А — произвольное множество. Множество А×A называют универсальным отношением, определенным на множестве А; любая пара (a1, a2), где ![]() ![]() По аналогии с понятием бинарного отношения вводится и понятие n-арного (n-местного) отношения. Определение. Пусть A1, …, An — непустые множества. Всякое подмножество R их декартового произведения А1×An называется отношением, определенным на системе множеств A1, …, An. Если A1 = … = An = А, то отношение R, определенное на системе множеств A1, …, An, называют n-арным (n-местным) отношением, определенным на множестве А. 2 Операции над бинарными отношениями Так как бинарные отношения, определенные на фиксированной паре множеств А, В, являются подмножествами А×В, то над ними можно производить операции объединения, пересечения и дополнения (в множестве А×В). Так, если R, S — два бинарных отношения, определенных па паре множеств А, В, то для любых ![]() ![]() ![]() ![]() Помимо теоретико-множественных операций над отношениями важное значение имеют еще две операции над ними: обращение и умножение отношений. Определение. Пусть ![]() ![]() ![]() ![]() Бинарное отношение, обратное к отношению R, обозначается R–1. Таким образом, ![]() Если R — бинарное отношение «х является родителем у», то R–1 — отношение «х является ребенком (сыном или дочерью) у». Определение. Пусть ![]() ![]() ![]() ![]() Произведение бинарных отношений ![]() ![]() ![]() ![]() Теорема 1. Пусть ![]() ![]() ![]() Теорема 2. Пусть ![]() ![]() 1 Свойства бинарных отношений Бинарное отношение R, определенное на множестве А, называется: - рефлексивным, если для любого ![]() - антирефлексивным, если для любого ![]() -симметричным, если для любых ![]() - антисимметричным, если аRb и bRa влекут a=b. - транзитивным, если для любых ![]() Например, отношение ≤ на множестве R действительных чисел, а также отношение включения подмножеств некоторого множества являются рефлексивными и транзитивными, но не являются симметричными. Отношение < на множестве действительных чисел транзитивно, но не рефлексивно, не симметрично. Отношение «х является матерью у» не рефлексивно, не симметрично, не транзитивно. 2 Виды бинарных отношений Определение. Бинарное отношение R, определенное на множестве А, называется отношением эквивалентности или просто эквивалентностью на множестве А, если R рефлексивно, симметрично и транзитивно. Примеры отношений эквивалентности: отношение равенства в произвольной системе множеств; отношение равночисленности, т.е. иметь одинаковое число элементов, в системе конечных множеств; отношение «учиться в одной группе» в множестве студентов лесопромышленного факультета; пусть F: A → B — отображение. Отношение σ, определяемое следующим образом: ![]() |