Примеры бинарных отношений. 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 Операции над отношениями
Так как отношения – это множества, то над ними могут выполняться все теоретико-множественные операции: объединение, пересечение, дополнение и разность.
Кроме того, определяются специфические для отношений операции: сечение, обращение (симметризация) и композиция.
Рассмотрим два отношения и , определенные на множествах и , , . В результате выполнения операций , , получаем множество упорядоченных пар, являющихся соответственно объединением, пересечением и разностью множеств и . Результаты выполнения этих операций также являются отношениями на множествах и . Дополнение отношения (обозначается ) содержит все упорядоченные пары множества , кроме тех пар, которые принадлежат , т.е. .