XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 8
Текст из файла (страница 8)
Поэтому в данном случае пересечение В(~) П ПР(д) всегда не пусто. Полезно отметить также, что если )' и д — биекции, то и композиция их тоже будет биекцией. Вернемся к рассмотрению композиции соответствий рос~. Полагая, что область определения Р(р) соответствия р не пуста, возьмем проювольный элемент х Е Р(р). Пусть сечение р(х) С В соответствия р не пусто и найдется такой элемент е Е р(х), что сечение н(я) С С также не пусто. Тогда непустое множество ((х, Ф): Ф Е о(е)) будет подмножеством сечения соответствия р0 н в точке х. Сечением соответствия р о н в точке х будет непустое в силу сделанных предположений множество всех таких упорядоченных пар (х, $) Е А х С, что х Е Р(р), а Ф Е о(е) для некоторого я Е р(х).
Говоря неформально, нужно перебрать все элементы я из сечения р(х). Таким образом, различие в построении композиции соответствий и композиции отображений заключается в том, что „промежуточный" элемент е в общем случае не единственный и каждому такому элементу также ставится в соответствие не единственный элемент у Е С. Пример 1.8.
Соответствие р возьмем ю примера 1.3. Соответствие н зададим как соответствие из множества про- 53 1.4. Операции иад соответствиями грамм (пм ггз, газ, п4, ггь) в множество заказчиков программного обеспечения (31, Зз, Зз, 34). Пусть и = ((пд, Зз), (гз1, 34), (гзз 31), (пз, Зз), (п4, 34), (пь, Зз)). Рассмотрим процесс построения композиции соответствий р и о. Начнем с элемента И. Имеем р(т1 ) = (пм пз, ггь), гг(г11) = = (Зз, 34), гг(газ) = (Зз) и о(гзь) = (Зз). Отсюда получаем о(пд) О гг(газ) 11гг(пь) = (Зг, Зз, 34) сечение композиции по элементу Н.
Рассуждая аналогично, получим (реп)(П) = (31, 34) и (ре гг)(С) = (31, Зз). Построение графа композиции ре гг проиллюстрировано на рис. 1.3. ф рва Р 1 3, з, н зе П з 3 з с Рис. 1.3 Отметим, что область оггреоелеиил композиции соощввгпсгввий содержится в области определения первого соответствия, а область значений композиции соответствий — в области значений второго соответствия. Из приведенных рассуждений следует, что для того, чтобы композиция соответствий была отлична от пустого соответствия, необходимо и достаточно, чтобы пересечение области значений первого соответствия и области определения второго соответствия было не пусто.
К определению композиции соответствий можно подойти с более общих позиций. Пусть р С А х В и о С С х Р. При этом Ь МНОЖЕСТВА И ОТНОШЕНИЯ на множества А, В, С и Р априори не накладывается никаких органичений. Композиция р о о соответствий р и о в этом случае также определяется соотношением (1.3). Чтобы такая композиция была отлична от пустого соответствия, необходимо и достаточно выполнение условия Н(р) й Р(о) ~ И. В частности, рост= Я всякий раз, когда ВПС= Я.
Пример 1.9. Рассмотрим соответствие т = ((1, а), (2, а), (3, Н)) из множества А = (1, 2, 3) в множество В = (а, Ь, И) и соответствие ср = ((Ь, е), (Ь, Д, (с, у)) иэ множества С = (Ь,с, И) в множество Р = (е, Д. В данном случае В П С ф З, но т о <р = Я, поскольку Я(т) = (а, И), Р(~р) = =(Ь,с) и Щт)ПР(р)=а. У Заметим, что композиция соответствий р С А х В и о С С х х Р не коммутативна, т.е. в общем случае ро а ф о о р, поскольку росгСАхР, аоорССхВ. Бинарное ошношение на множестве является частным случаем соответствия.
Для двух бинарных отношений р и о, заданных на множестве А, их композиция р о о (1.3) как соответствий является бинарным отношением на том же множестве А. В этом случае говорят о ко.ннозииии бинарных онэношений на нножесгнве А. Композицию ро р бинарного отношения р на некотором множестве с самим собой называют квадраоэо.н бинарного онэношенил р и обозначают рэ. Рассмотрим пример построения композиции бинарных отношений на множестве и покажем, что в общем случае для двух бинарных отношений т и ~р также имеет место неравенство т~~р ф уо т, хотя обе композиции, в отличие от аналогичных композиций двух произвольных соответствий, заданы на одном и том же множестве. 1.4. Операции иад соответствиаии Пример 1.10. а.
Зададим на множестве А = (1, 2,3,4) бинарныеотношеният=((х, У): х+1<У) У=((х У): ~х У! =2) и найдем композицию то р. Имеем т(1) = (3, 4), ср(3) = (1) и ~р(4) = (2). Следовательно, (т о у) (1) = 1о(3) 0 ср(4) = (1, 2). Далее т(2) = (4), <р(4) = (2) и (тор)(2) = (2). Так как т(3) = т(4) = И, то в итоге получим то р = ((1, 1), (1, 2), (2, 2)). Построение композиции проиллюстрировано на рис. 1.4, а. оз Зо 4О 04 и т иот 1 1о 01 Рис. 1.4 Найдем композицию рот. Поскольку у(1) = (3), а т(3) = = И, то (1о о т)(1) = О.
Аналогично <р(2) = (4), а т(4) = о, поэтому (<рот)(2) = о. Далее у(3) = (Ц, т(1) = (3,4), поэтому (1оо т)(3) = (3,4), а 1о(4) = (2), т(2) = (4) и (ее от)(4) = (4). Построение композиции проиллюстрировано на рис. 1.4, и. Легко видеть, что торф рот. 56 1. МНОЖЕСТВА И ОТНОШЕНИЯ б. Пусть отношение р на множестве действительных чисел определено как функция у =ах+Ь.
Найдем квадрат этого отношения (линейной функции от одного переменного). Согласно (1.4), зто будет функция И, такая, что Цх) = =а(ах+Ь)+с, т.е. а(х) =а~х+(аЬ+с). Это тоже линейная функция, но с другими коэффициентами. Приведем некоторые свойства композиции соответствий: 1) ро (о о т) = (ро о) от„ 2) для любого соответствия р имеет место розг = кгор= Ег; 3) р (о0т) = (р о) 0(р т); 4) для любого бинарного отношения на множестве А имеет место равенство роЫА = ЫАор= р. Эти свойства нетрудно доказать методом двух вк иочений. Рассмотрим в качестве примера доказательство свойства 3. Пусть некоторая упорядоченная пара (х, у) принадлежит композиции р а (о 0т). Тогда, согласно (1.3), найдется такой элемент «, что (х, «) Е р и («, у) Е о 0 т.
Последнее означает, что («, у) Е о или (», у) Е т. Таким образом, для элемента « имеем (х, «) Е р и («, у) Е о или (х, «) Е р и («, у) Е т. Первая альтернатива имеет место при (х, у) Е роо, а вторая— при (х, у) Е ро т, что означает (х, у) Е р о о 0 рот. Тем самым включение ро(о0т) С роо0рот доказано. Доказательство включения рост 0рот С ро (сг0т) запишем коротко, используя логическую символику: (х, у) Е ро о 0 р о т ~ (ха)(((х, и) Е р) Л ((и, у) Е о))Ч У (Во) И(х, Е) Е р) Л ((о, у) Е т)) =Ь =ь (3«) (((х, «) Е р) Л (((«, у) Е о ) У ((«, у) Е т))) =ь =« (3«)(((х, «) Е р) Л((«, у) Ео 0т)) =ь =ь (х, у) Е ро (о0т).
В данном случае доказательства двух включений не совсем симметричны: элементы и и е во второй части доказательства не обязаны совпадать. 57 1.4. Операцви ввд соотввтствиюав Замечание 1.4. В тождестве, выражающем свойство 3, нельзя вместо объединения поставить пересечение, так как в этом случае тождество нарушится. Можно доказать, что сохранится лишь включение ро(айт) С роайрот, а обратное включение в общем случае не имеет места.
Анализ свойств 2 и 4 показывает, что роль пустого соотиввтсшвия аналогична роли нуля при умножении чисел, а диагональ мноэсвсшва А играет роль, аналогичную роли единицы, на множестве всех бинарных отношений на А. Обратное соответствие. Соответствие, обратное к соответствию р С А х В, есть соответствие из В в А, обозначаемое р 1 и равное, по определению, р = ((у, я): (х, у) Е р). Для соответствия т иэ примера 1.3 т 1 =1(пм И), (по, П), (по, С), (пэ~ И)з (п4~ П)1 (пз~ И)~ (пв~ С)).
Обратное соответствие обладает следующими легко проверяемыми свойствами: 1) ( ') '=р; 2) (рос) 1 =о 1ор Для бинарного отношения р на множестве А обратное соответствие есть бинарное отношение на том же множестве. В этом случае говорят о бинарном отношении р 1 на мнонсестее А, обратном к р. Заметим, что соответствия ро р 1 и р 1 о р в общем случае не совпадают.
Даже для бинарного отношения р на множестве А рор ~ ф р 1ор, а также рор ~ ф Ыл и р ~орф Ыл. Например, для бинарного отношения р = 1(3,1), (4,1), (4,2)) на множестве А = (1, 2, 3, 41 графы самого отношения, обратного отношения р 1, композиций рор 1 и р 1 о р представлены на рис. 1.5. 58 1. МНОЖЕСТВА И ОТНОШЕНИЯ Р Р 10 О1 1 1 2о о2 2 2 3 3 Зо оЗ 4 4 4о о4 1 1 2 2 3 3 Рис. 1.5 1 оу =!ДА, Отображение 1 1 в этом случае называют отображением, обратным к у. Ограничение соответствия. Пусть р С А х  — соответствие иэ А в В и С С А, Р С В.
Оераничением соотпветпстпвил р на подмножестпва С и Р (или (С, Р)-оераничением соответствия р) называется соответствие из С в Р, обозначаемое р~С,р, такое, что (х, у) Е р~с р 4Ф ((х, у) Е р) Л (х Е С) Л (у Е Р). Таким образом, (С, Р)-ограничение соответствия р есть „то же самое" соответствие р, но из последнего берутся только Если 1: А -~  — отображение, то оно является соответствием. Обратное к 1 соответствие из В в А в общем случае не является отображением. Действительно, соответствие 1 1, обратное к у, состоит нз всех упорядоченных пар вида (1(х), х), х Е А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
