Лекция № 6 Тема 1 Элементы теории бинарных отношений

1. Кафедра системы сбора и обработки информации

ВОЕННО-КОСМИЧЕСКАЯ АКАДЕМИЯ ИМЕНИ А.Ф. МОЖАЙСКОГО
Кафедра системы сбора и обработки информации
Дискретная математика
Лекция № 6
Тема 1 Элементы теории бинарных отношений
Андрушкевич С.С..

2.

2
Лекция № 6. Элементы теории бинарных отношений
Цель: ознакомиться с понятием бинарного отношения и
формами их представления, научиться выполнять основные
бинарные и унарны операции над отношениями
Учебные вопросы:
1. Определение и представление отношений
2. Формы представления отношений
3. Операции над отношениями

3.

3
Говорить об отношениях можно тогда, когда
имеется множество А
элементов, на которых эти отношения определены. Само множество А называют
множеством-носителем отношений.
Отношение R – подмножество конечного множества декартовой степени
Аk = Аn1×А n2×А n3× …×Аnk заданного множества А = { а1, а2,…,аn }
Подмножество R называется k-арным отношением в множестве А или над
множеством А. Число k называется рангом или местностью отношения R.
Подмножество R ⸦ Аk называется также k-местным или k-арным предикатом на
множестве А. Запись R(а1,а2,…,аn) означает, что (а1,а2,…,аn ) ϵ R.
Множество U = Аk и пустое множество в Аk называются соответственно
универсальным отношением и нуль-отношением ранга k в множестве А.
Диагональ множества, т.е. множество
Е = {(а1,а2,…,аn )| аi ϵАik , i = 1(1)n},
называется отношением равенства в множестве А. Множество всех n-арных
отношений в множестве А относительно операций ∪,∩ является булевой
алгеброй.

4. Учебный вопрос №1

4
Если R и S суть n-местные отношения в множестве А, то n-местными
отношениями в А будут также следующие подмножества в Аn: R ∪ S, R ∩ S,
R ∆ S, R \ S, R’= Аn\R.
Функциональным отношением называется (n+1)-местное отношение F в
А, если для любых элементов а1, а2,…,аn , а, b из А из того, что (а1,а2,…,аn , a)
ϵ F и (а1,а2,…,аn , b) ϵ F, следует, что а = b.
Бинарное
отношение
–
подмножество
множества
упорядоченных пар {(аi , аj)} элементов заданного множества
А= {(а1,а2,…аi ,…, аj …, а|A )| аi ϵАi , i = 1(1) |А},
А×А=A2

5. Учебный вопрос №1

5
О п р ед е л е н ие . Каждый элемент булеана называется бинарным
отношением.
Наряду
с
теоретико-множественными
операциями
объединения,
пересечения, разности (\), симметрической разности (∆), дополнения (R’) для
бинарных
отношений
рассматривают
также
специальные
операции:
обращения отношений , умножение отношений и др.
Отношением называется пара [Ω,R], где Ω – множество-носитель, a R –
подмножество декартова произведения Ω×Ω, т.е.R ⊆[Ω×Ω]. Содержательный
смысл такого определения состоит в том, что задание подмножества R в
множестве Ω×Ω определяет, какие пары находятся в отношении R.
Пусть (x,y) ϵ Ω тогда если пара (х, у) входит в R, т.е. (x,y) ϵ R , то будем
записывать xRy, что читается «пара (х,у) находится в отношении R».
Необходимо отметить, что порядок в паре важен и в дальнейшем будем
называть пару (х, у) упорядоченной парой.

6. Учебный вопрос №1

Наиболее важными типами бинарных отношений являются отношения
эквивалентности, порядка (строгие, нестрогие, линейные, частичные и др.) и
функциональные отношения.
Наиболее известным типом отношения является эквивалентность, ее
отношение удовлетворяет следующим условиям: аi Rаi , аi Rаj => аj Rаi , аi RаjΛ
аj Rаk => аi Rаk . Если f отображает множество Х во множество Y, то бинарное
отношение R = {(х1, х2 )| (f(x1) = f(x2))} является эквивалентностью. Для
произвольного аiϵ
А подмножество Аr ⊆A, состоящее из всех аi эквивалентных аj , называется
классом эквивалентности аi . Любые два класса эквивалентности либо не
пересекаются, либо совпадают, т.е. любая эквивалентность определяет
разбиение множества А = ∩ Аr и обратно – любое разбиение множества
порождает эквивалентность.
6

7. Учебный вопрос №2

7
1. Представление перечислением элементов отношения. Для того чтобы
задать отношение [Ω,R] на множестве Ω необходимо перечислить все пары
(x,y)∈Ω× Ω , которые содержатся в R.
Примером задания отношения на множестве Ω={x1,x2,x3,x4}, в форме
перечисления
может
быть
R={(x1,x2),(x2,x3),(x2,x4),(x4,x2)}.
Кроме
непосредственного перечисления всех пар, содержащихся в R, существуют
другие способы представления отношения: матричное представление,
векторное представление, представление графом, и др.

8. Учебный вопрос №1

2. Матричное представление. Пусть множество