Тема 3. Отношения на множествах

Отношения. Функции. Взаимно однозначные соответствия

Часто при решении задач необходимо выбирать элементы, связанные некоторым соотношением. Примерами таких связей между элементами могут служить функциональные: зависимости или отношение «меньше либо равно».

n -местным отношением или n -местным предикатом Р на множествах A 1, А 2, ..., Апназывается любое подмножество прямого произведения A А 2× ... × Ап. Другими словами, элементы x 1, x 2, ..., x п(где x 1∈ A 1,..., xnАп) связаны соотношением Р (обозначается P ( x 1, x 2, ..., x п)) тогда и только тогда, когда ( x 1, x 2, ..., x п) ∈ Р .

При п = 1 отношение Р является подмножеством множества A 1и называется унарным отношением или свойством .

Наиболее часто встречаются двухместные отношения (п = 2). В этом случае они называются бинарными отношениями или соответствиями . Таким образом, соответствием Р между множествами А и В является подмножество множества А × В . Если РА × В и (х , у ) ∈ Р , то пишут также хРу .

Отношение РАпназывается п-местным отношением (предикатом ) на множестве А .

Пример 2.1.Если А = {2, 3, 4, 5, 6, 7, 8}, то бинарное отношение Р = {( x , y ) | x , уА , х делит y и x ≤ 3} можно записать виде Р = {(2, 2), (2, 4), (2, 6), (2, 8), (3, 3), (3, 6)}.

Пример 2.2.Рассмотрим отношение Р = {{х , у ) | х , у ∈ ℝ , ху } на множестве ℝ . Тогда запись хРу означает, что ху , и в качестве имени (обозначения) этого отношения можно взять сам символ ≤.

Бинарные отношения РА × В иногда удобно изображать графически. Рассмотрим два таких представления. Начертим пар y взаимно перпендикулярных осей (Ох горизонтальная ось, Оу — вертикальная. ось), на каждой оси отметим точки, представляющие элементы множеств А и B соответственно. Отметив на плоскости точки с координатами (х , у ) такие, что (х , у ) ∈ Р , получаем множество, соответствующее отношению Р . На рис. 1.3 показано множество точек, соответствующих отношению из примера 2.1.

Рис. 1.3.

Другой способ состоит в том, что элементы хА и y B , связанные отношением Р , соединяются стрелками.

Пример 2.4.На рис. 1.4 графически показаны отношение Р 1= {(а , 2), ( b , 1), ( c , 2)} между множествами А = {а , b , с } и В = {1, 2, 3}, а также отношение Р 2= {(а , b ), ( b , b ), (с , а )} на множестве А .

Рис. 1.4.

Для любого множества A определим тождественное отношение idA⇌ {( x , x ) | x А } и универсальное отношение UAA 2. Отношение idAназывается также диагональю , а UAполным отношением .

Пусть P — некоторое бинарное отношение. Областью определения отношения Р называется множество

δ p⇌ {x | ( x , y ) ∈ P для некоторого y },

областью значений отношения Р — множество

ρ p⇌ {y | ( x , y ) ∈ P для некоторого x },

06ратным к Р отношением называется множество

Р –1⇌ {( y , x ) | ( x , y ) ∈ P },

Образом множества X относительно предиката Р называется множество

Р (Х ) ⇌ {у | (х , у ) ∈ Р для некоторого хX },

прообразом множества X относительно Р — множество Р –1(Х ) или, другими словами, образ множества X относительно предиката Р –1.

Пример 2.5.Для отношения Р из примера 2.1 и множества X = {3} имеем δ p= {2, 3}, ρ p= {2, 3, 4, 6, 8}, Р –1= {(2, 2), (4, 2), (6, 2), (8, 2), (3, 3), (6, 3)}, P ( X ) = {3, 6}, P –1( X ) = {3}.

Произведением бинарных отношений Р 1⊆ А × В и P 2⊆ В × С или композицией РР 2называется множество P 1 ○ P 2= {( x , у ) | x А , уС , и найдется элемент z В такой, что ( x , z ) ∈ P 1и ( z , y ) ∈ Р 2} (рис. 1.5). В дальнейшем произведение P 1 ○ P 2будем также обозначать через P 1P 2.








Дата добавления: 2016-02-24; просмотров: 1396;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.004 сек.