Бинарные отношения

Бинарные отношения

План

1. Бинарное отношение. Область определения, область значения бинарного отношения. Понятие упорядоченной пары.

2. Декартово произведение множеств. Свойства декартового произведения множеств.

3. Матрица бинарного отношения, заданного на конечном множестве.

4. Свойства бинарных отношений

1. Бинарное отношение. Область определения, область значения бинарного отношения. Понятие упорядоченной пары

Термином «отношение» в математике часто пользуются для того, чтобы обозначить какую-либо связь между предметами, в частности, элементами множества.

Чаще всего используемыми являются бинарные отношения. Бинарные (двухместные) отношения используются для определения каких-то взаимосвязей, которыми характеризуются пары элементов во множестве (на множестве людей могут быть заданы, например, следующие бинарные отношения: жить в одном доме, быть старше, быть матерью). Задать отношение, определенное на конечном множестве, можно простым перечислением пар элементов, находящихся в заданном отношении.

В общем случае при установлении бинарного отношения для объектов важно, в каком они берутся порядке. Для иллюстрации рассмотрим следующий пример. Пусть множество членов одной семьи , где элементы определяются следующим образом:

- мать (35 лет);

- отец (41 год);

- сын (11 лет);

- дочь (7 лет);

- бабушка (60 лет).

Между членами семьи рассмотрим отношение «быть старше». Будем обозначать отношение . Если два члена семьи находятся в таком отношении друг к другу, как, например, и (поскольку отец старше матери), то будем писать . Заметим, что и в рассмотренном отношении не состоят, т.к. не верно то, что мать старше отца. А значит в рассмотренном бинарном отношении важен порядок объектов: какой из них взят первым, а какой вторым. Для рассмотренного множества получим, что, кроме , имеют место: , , , , , , , , , однако, если объекты в парах поменять местами, то в указанном отношении они уже состоять не будут.

Обычно бинарное отношение рассматривает пары объектов, взятых в определенном порядке: так называемые упорядоченные пары.

Упорядоченной парой элементов и , обозначаемой как , называется объект, обладающий двумя свойствами:

1. однозначно определяется элементами и ;

2. Если существует упорядоченная пара такая, что

,

то , .

Таким образом, бинарное отношение – это множество упорядоченных пар. Если есть некоторое отношение, то запись означает, что .

Таким образом, задать отношение «быть старше» на множестве из предыдущего примера можно следующим образом:

В общем случае можно рассматривать n-местные отношения, где каким-то свойством связаны между собой не пары, а n-ки элементов. Тогда n-арное отношение – это множество упорядоченных n-ок элементов. Например, для n=3 на множестве всех студентов ОНПУ можно задать трехместное отношение «жить в одной комнате общежития». Тогда множество будет состоять из всех троек студентов, каждая из которых проживает в одной комнате.

Областью определения бинарного отношения (обозначается далее ) называется множество:

.

Областью значения бинарного отношения (обозначается далее ) называется множество:

.

2.Декартово произведение множеств. Свойства декартового произведения множеств

Прямым (или декартовым) произведением множеств называется множество:

.

Некоторые свойства декартового произведения аналогичны свойствам произведения чисел:

;

;

;

;

;

.

Докажем первое свойство. Для этого надо показать: любой элемент множества является элементом множества ; любой элемент множества является элементом множества . Два условия можно объединить в одно: если элемент принадлежит множеству , то это равносильно тому, что он принадлежит множеству . Для первого свойства имеем:

что и требовалось доказать.

Любое бинарное отношение есть подмножество некоторого декартового произведения , такого, что , .

3.Матрица бинарного отношения, заданного на конечном множестве

Задать бинарное отношение на конечном множестве можно не только при помощи перечисления упорядоченных пар, которые этому бинарному отношению принадлежат, но и при помощи матриц. Так бинарному отношению , где , ставится в соответствие прямоугольная матрица с элементами . Элементы определяются в соответствии с формулой:

т.е. , если между и имеет место отношение , или , если оно отсутствует.

Для примера, рассмотренного выше, где отношение определялось как отношение «быть старше» на множестве , соответствующая матрица будет иметь вид:

4.Свойства бинарных отношений

Пусть . Это отношение называется:

1. Рефлексивным, если для : , т.е. каждый элемент множества связан отношением с самим собой. Например, отношение параллельности для прямых на плоскости является рефлексивным, поскольку каждая прямая параллельна самой себе;

2. Антирефлексивным, если не существует элемента множества , связанного отношением с самим собой. Например, отношение «быть матерью», заданное на множестве людей, является антирефлексивным, поскольку никакой человек не может быть матерью для самого себя;

3. Симметричным, если из того, что следует, что , т.е. если находятся в отношении к , то и находятся в отношении к . Например, отношение «учиться в одном университете» является симметричным;

4. Антисимметричным, если для из одновременной истинности и будет следовать, что , т.е. ни для каких различающихся элементов и не выполняются одновременно и . Например, отношение «быть выше» на множестве студентов группы;

5. Транзитивным, если из того, что и следует, что . Например, отношение «быть моложе» на множестве людей.

Для бинарного отношения, обладающего определенными свойствами, его матрица также имеет характерные признаки:

• Для рефлексивного отношения главная диагональ его матрицы будет содержать только единицы;

• Для антирефлексивного отношения главная диагональ его матрицы будет содержать только нули;

• Для симметричного отношения его матрица будет симметрична относительно главной диагонали;

• Для антисимметричного отношения в его матрице будут отсутствовать единицы, симметричные относительно главной диагонали.

Вопросы

1. Что называется бинарным отношением? Привести примеры бинарных отношений.

2. Что такое область определения, область значения бинарного отношения? Привести примеры.

3. Что такое упорядоченная пара элементов?

4. Как определяется декартово произведение множеств?

5. Свойства декартового произведения множеств. Доказать.

6. Способы задания бинарного отношения на конечном множестве.

7. Как определяется матрица бинарного отношения?

8. Какое бинарное отношение называется рефлексивным/антирефлексивным? Какими особенностями обладают матрицы таких отношений? Привести примеры.

9. Какое бинарное отношение называется симметричным/антисимметричным? Какими особенностями обладают матрицы таких отношений? Привести примеры.

10. Какое бинарное отношение называется транзитивным? Привести примеры.