Примеры бинарных отношений. 4 страница

Доказательство теоремы можно провести методом математической индукции.

Следствие теоремы 1.Мощность декартовой степени множества равна .

Пример.Пусть , , .

Мощность множества равна , где , , .

Мощность множества равна или

3.2 Понятие отношений. Бинарные и n-арные отношения

Введем формальные понятия отношений.

Говорят, что находятся в отношении ( является множеством), если .

Определение. -арное ( -местное) отношение на множествах - это подмножество декартова произведения этих множеств, т.е. .

Определение. Унарное (одноместное) отношение – это подмножество множества . Такие отношения называются признаками: обладает признаком , если и .

Свойства унарных (одноместных) отношений – это свойства подмножеств множества . Поэтому для случая термин «отношение» употребляется редко.

Пример.

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

Пропорция иллюстрирует четырехместное отношение.

Наиболее часто встречающимися и хорошо изученными являются бинарные, или двухместные, отношения. Эти отношения возникают между парами объектов.

Определение.

Бинарным отношением на паре множеств и будем называть подмножество декартового произведения .

Пример. Отношение принадлежности (определяет связь между множеством и его элементами, обозначается ); отношение включения (определяет связь между двумя множествами); отношение равенства (=); отношение неравенства ( или ).

Примеры бинарных отношений.

1. Выражения: «быть братом», «делиться на какое-либо число»; «входить в состав (чего-либо)».

2. Всё множество есть отношение множеств и .

3. Если - множество действительных чисел, то { }.

4. Пусть - множество товаров в магазине, а - множество действительных чисел. Тогда - отношение множеств и .

5. Отношение « » выполняется для пар (7,9) и (7,7), но не выполняется для пары (9,7).

6. Если - множество людей, то .

Для любого бинарного отношения можно записать соответствующее ему соотношение. В общем виде соотношение можно записать как , где - отношение, устанавливающее связь между элементом из множества и элементом из множества .

Определение. Пусть , , . На паре множеств и можно построить бинарных отношений.

Определение.На множестве , состоящем из элементов, может быть задано бинарных отношений.

В дальнейшем будем рассматривать бинарные отношения, поэтому вместо термина «бинарное отношение» будем употреблять термин «отношение».

3.3 Область определения и область значений отношений

Определение.

Область определения отношения на и (обозначим ) есть множество всех таких, что для некоторых имеем , т.е. область определения есть множество первых координат упорядоченных пар из . Область значений отношения на и (обозначим ) есть множество всех таких, что для некоторого , т.е. область значений есть множество всех вторых координат упорядоченных пар из .

Пример.

В примерах отношений, приведенных выше, в частности, в (2), область определения есть все множество , а область значений - все множество . В (3) как область определения, так и область значений совпадают с множеством . В (4) область определения есть множество , а область значений есть множество всех действительных чисел, каждое из которых совпадает с ценой некоторого товара в магазине. В (6) область определения и область значений есть множество всех людей, имеющих родственников.

Пример. и . Декартово произведение этих множеств .

Отношение «быть делителем» есть множество . Отношение «равенство (=)» есть множество . Отношение « » есть пустое множество .

Области определения и значений отношения - это соответственно множества и .

Области определения и значений отношения - это соответственно множества , и .

Определение.Если и , то и . В таких случаях есть отношение от к , называется соответствиеми обозначается . Если , то любое является подмножеством множества и называется отношением в . Если область определения отношения совпадает с некоторым множеством , то говорят, что отношение определенона .

Существует три частных случая отношений в :

- полное (универсальное отношение) , которое имеет место для каждой пары элементов из (например, отношение «работать в одном отделе» на множестве сотрудников данного отдела);

- тождественное (диагональное) отношение, равносильное (например, равенство на множестве действительных чисел);

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

3.4 Способы задания отношений

Существует несколько способов задания отношений:

- способ перечисления элементов (в виде списка);

- способ задания характеристического свойства или (порождающей процедуры), выраженного в словесной или символической форме;

- матричный способ;

- графический способ (с помощью ориентированного графа);

- с помощью фактор-множества.

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

Пример. На множествах чисел и построим отношение «делитель» ( ), которое состоит из упорядоченных пар вида , где - делитель , , :

.

Часто отношение задается при помощи характеристического свойства, выраженного в словесной или символической форме.

Пример. Пусть - множество женщин, - множество мужчин. Тогда отношение , заданное при помощи характеристического свойства, выраженного в словесной форме, будет иметь вид .

Пример. Если - множество действительных чисел, то .

Матричный способ задания отношений основан на представлении отношения соответствующей ему прямоугольной таблицей (матрицей). Её строки соответствуют первым координатам, а столбцы – вторым координатам. На пересечении -ой строки и -ого столбца ставится единица, если выполнено соотношение , и нуль, если это соотношение не выполняется (нулевые клетки можно оставлять пустыми).

Эта матрица содержит всю информацию об отношении .

Полному отношению соответствует квадратная матрица, все клетки которой заполнены единицами, тождественному – квадратная матрица, состоящая из нулей, с главной диагональю из единиц, а пустому – квадратная нулевая матрица.

Пример. Пусть заданы , . Отношение может быть представлено следующей матрицей

Отношения можно задавать (или изображать) с помощью ориентированного графа. Вершины графа соответствуют элементам множеств и (элементы изображаются точками на плоскости), а дуга, направленная из вершины к (направленная линия, соединяющая пары точек) означает, что .

Пример. Отношение из предыдущего примера представлено в виде следующего ориентированного графа (рис.3.1).

Рисунок 3.1 – Граф отношения

Отношение в отображается графом с вершинами, соответствующими элементам этого множества. При этом если имеют место соотношения и , то вершины связываются двумя противоположно направленными дугами, которые можно условно заменять одной ненаправленной дугой. Соотношению соответствует петля, выходящая из и входящая в эту же вершину.

Пример. Пусть . Отношение может быть представлено в виде графа на рис. 3.2.

Рисунок 3.2 – Граф отношения

Пример.

Граф полного отношения для представлен в следующем виде (рис. 3.3).

Рисунок 3.3 – Граф полного отношения для

Пример.

Граф тождественного отношения для представлен в следующем виде (рис. 3.4).

Рисунок 3.4 – Граф тождественного отношения для

Пример.

Граф пустого отношения для представлен в следующем виде (рис. 3.5).

Рисунок 3.5 – Граф пустого отношения для

При рассмотрении способа задания отношения с помощью фактор-множества введем понятие сечения отношения.

Определение

Пусть - отношение на множествах и . Если , то сечение отношения по элементу , обозначаемое , есть множество , состоящее из элементов таких, что , т.е. . Множество всех сечений отношения называется фактор-множеством множества по отношению и обозначают . Объединение сечений по элементам некоторого подмножества называется сечением R(Z)относительно подмножестваZ.

Фактор-множество полностью определяет отношение .

Пример. Пусть заданы множества , и отношение . Получим сечения: , , , , , . Определим фактор-множество . Рассмотрим множество . Сечение отношения по множеству выглядит следующим образом: .

3.5 Операции над отношениями

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

Кроме того, определяются специфические для отношений операции: сечение, обращение (симметризация) и композиция.

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