XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 7
Текст из файла (страница 7)
ЬЗ. Соответетввв в овварвые отвошеввв 45 Пример 1.3. Рассмотрим множество программистов А = = «И,П,С) и множество программ В= «пмпз,пз, пе,пз). Зададим соответствие т нз А в В, связывающее программистов и разрабатываемые ими программы: т = «(И, п1), (И, пз), (И, пз) (П, пз), (П, пе), (С, пз), (С, па)) С А х В. ф Областпь определения соотпеетпстпеия р С А х В из множества А в множество  — это множество всех первых компонент упорядоченных пар из р: Р(р) = «х: (Зу Е В)(х, у) Е р) .
Областпь значения соотпеетпстпеия р — это множество всех вторых компонент упорядоченных пар из р: Щр) = «у: (Зх Е А)(х, у) Е р). Из определения вытекает, что Р(р) С А, В(р) С В. Соответствие из А в В называют всюду определенным, если его область определения совпадает с множеством А: Р(р) = А. Сечением соотпеетпстпеия р С А х В для фиксированного элемента х Е А будем называть множество р(х) = «у: (х, у) Е р). Можно сказать, что сечение соответствия р(х) есть множество всех „образов" элемента х при данном соответствии. Сечением соотпеетпстпеия р по множестпеу С С А будем называть множество р(С) = «у: (х, у) е р, х Е С). Пример 1.4.
Область определения соответствия т ю примера 1.3есть все множество А, а область значения — все множество В. Сечением соответствия т по элементу П будет множество т(П) = «пз, п4) У Соответствие р С А х А ю множества А в себя, т.е.
подмножество множества Аз, называют бинарным отпноиеением на мношсестпее А. 46 1. МНОЖЕСТВА И ОТНОШЕНИЯ Пример 1,5. Простейшим примером бинарного отношения является отношение нестрогого неравенства на множестве действительных чисел й. Здесь каждому х Н Й поставлены в соответствие такие р Е )к, для которых справедливо х ( у. ф Для произвольного бинарного отношения на некотором множестве часто используют запись х р у вместо (х, у) Е р, говоря при этом об элементпах, связанных бинарным огпношекием р.
Это согласуется с традиционной формой записи некоторых часто используемых бинарных отношений. Так, пишут х < р, а не (х, у) Е <. Для таких бинарных отношений употребляют устоявшиеся словосочетания. Например, запись х ( у читается так: вх не больше д". Бинарное отношение на множестве А, состоящее из всех пар (х,х), т.е. пар с совпадающими компонентами, называют диагональю множества' А и обозначают ЫА. Нетрудно понять, что диагональ А есть тпождсстпеенное отоБражение А на себя.
Для наглядного изображения соответствий из А в В (бинарных отношений, в частности) будем использовать два способа. Первый из этих способов состоит в интерпретации соответствия как подмножества декартова произведения, которое можно изображать примерно так же, как на плоскости можно изображать подмножества декартова квадрата числовых множеств.
Второй способ, применяемый для конечных множеств А и В, — построение так называемого граЯа соопаветпсгпвив. В этом случае элементы множеств А и В изображаются на плоскости кружочками. Если и только если пара (и, о) принадлежит соответствию р, то в графе соответствия из кружочка, обозначающего элемент и Е А, проводим стрелку к кружочку, обозначающему элемент е Е В. Для бинарного отношения на конечном множестве А часто удобнее использовать граф другого вида. Элементы множества А изображаются кружочками только один раз, а стрелки проводятся по тем же правилам, 'Иногда говорят о диагонали в множестве А, котя правильнее было бы называть зто отношение диагональю декартова квадрата множества А.
47 1.3. Соответствии и бииариые отиошеииа что и в графе соответствия. Заметим, что при таком построении возможно соединение кружочка стрелкой с самим собой (петля). Пример 1.6. а. На рис. 1.1, а изображены график и граф бинарного соответствия из примера 1.3. 1 2 3 4 4 Рис. 1.1 б.
Пусть А = 11, 2, 3, 4). Бинарное отношение р на А определим как множество всех упорядоченных пар (х, у), таких, что я > р. Тогда Р = ((1з 1)з(2~ 1)э(2з 2)э (Зз 1)~ (Зэ 2)> (З~ 3)) (4, 1), (4, 2),(4, 3),(4, 4Ц. Область определения отношения В(Р) = (1, 2, 3, 41, область значений В(р) = 11, 2, 3, 41. График и два варианта графа отноше ния Р изображены на рис. 1.1, б. 48 1. МНОЖЕСТВА И ОТНОШЕНИЯ в.
Множество точек окружности эз+уз =1 есть график бинарного отношения на множестве действительных чисел, состоящего из всех таких упорядоченных пар (э, р), что о=~Мг- 'ч,, ~,~ ~ р л влетворяют уравнению хз+ уз = 1. Область определения бинарного отношения есть отрезок [ — 1, 1), область значения — также отрезок [-1, 1]. ф Соответствие р С А х В называют фуннционалъным но второй (первой) номионенше, если для любых двух упорядоченных пар (э, у) Н р и (х', р') Е р из равенства х = х' следует р = р' (и из у = у' следует э = э').
Функциональность соответствия по второй компоненте означает, что, фиксируя в любой упорядоченной паре, принадлежащей данному соответствию, первую компоненту, мы однозначно определяем и вторую компоненту. Таким образом, мы можем сказать, что соответствие, функциональное по второй компоненте, есть отображение (возможно, частичное). Поэтому соответствие у С А х В является отображением из А в В, если и только если оно всюду определено (т.е. Ю(у) = А) и функционально по второй компоненте.
Отметим также, что отображение из А в В является инъекцией тогда и только тогда, когда оно функционально по первой компоненте. В заключение обобщим понятие соответствия, определив отношения произвольной арности. Определение 1.4. Произвольное подмножество р декартова произведения А~ х ... х А„называют (н-арным или н-месшиым) ошношением на множествах Ам ..., Ае. В случае если все множества Ам ..., А совпадают, т.е. А~ —— ...
= А„= А, говорят об н-ариом ошиошеннн иа множесшве А. Если р — н-арное отношение на множествах А~, ..., А„и (а~, ..., а„) Е р, то говорят об элемеишаэ а~, ..., а„, св.яэаиныэ ошиозиеиием р. 49 1.3. Соответствия н бкиариые отношения к-ариое отношение на множествах А„..., А„ А,=...=А,=А Бинарное отношение на множествах Ао А~ (или соответствие ив А, в А ) и-ар нос отношение на множестве А А — А А ФУнкциональность по 2-и компоненте Бинарное отношение на множестве А Частичное отображение иаА, вА Функциональность по 2-й компоненте Полная А! Ас=А определекност Частичное отображек не множества А в себя Отображение ивА вАя Полная определенность А=А А 1 Отображение множества А в себя Рис.
1.2 Замечание 1.3. При н = 2 получаем бинарное оьпношение на множествах А1, Аз. Это не что иное, как соответствие из А1 в Аз, где множества А1 и Аз, вообще говоря, различны. При А1 = Аз = А получаем введенное ранее бинарное отношение на множестве, т.е. подмножество декартова квадрата А.
Таким образом, в общем случае (при произвольном а > 2) следует, строго говоря, различать термины еп-арное отношениее и „и-арное отношение на множестве". 50 Е МНОЖЕСТВА И ОТНОШЕНИЯ Связь между введенными понятиями отношения, соответствия и отображения проиллюстрирована на рис.
1.2. ф Пусть и-арное отношение р С А1 х ... х А„удовлетворяет условию: для любых двух кортежей (хм ..., х,, ..., х„) Е р и (ум ..., у;, ..., у„) Е р из выполнения равенств хь = уь для любого й ~ 1 (О ( й < и) следует, что и х; = у;. Тогда отношение р называют функциона.аъным ио 1-й комионенпъе (1 <1 ( и). Другими словами, функционапьность и-местного отношения по 1-й (1 ( (и) компоненте равносильна условию, что, фиксируя все компоненты, кроме 1-й, мы однозначно определяем и 1-ю компоненту. Пример 1.Т. а. Представим строку учебного расписания как кортеж вида (преподаватель, группа, дисциплина, аудитория, день, час). Тогда расписание можно рассматривать как секстарное (шестиместное) отношение на соответствующих множествах. Оно будет функционально по первой компоненте, если, конечно, предположить, что два преподавателя или более не проводят одно и то же занятие одновременно в одном и том же месте (хотя, например, на лабораторных работах это возможно).
Оно также функционально по третьей компоненте (один преподаватель не может вести одновременно занятия по разным дисциплинам), по четвертой (преподаватель со своей группой не могут находиться в разных аудиториях) и не будет, вообще говоря, функционально по второй, пятой и шестой компонентам. б. Рассмотрим на множестве 1'з геометрических векторов в пространстве тернарное (трехместное) отношение р, состоящее вз всех упорядоченных троек (х, у, х) компланарных векторов. Это отношение не является функциональным ни по одной компоненте, так как любым двум векторам соответствует бесконечно много векторов, образующих с ними компланарную тройку. 1.4.
Операции пад соответствиями 1.4. Операции иад соответствиями Поскольку соотивентсптвия можно считать множествами, то все операции над множествами (пересечение, объединение, разносить, дополнение и т.д.) можно применить и к соответствиям. Заметим, что, говоря о дополнении соответствия из А в В, мы имеем в виду дополнение до унивсрсаяьного соотпввнтствия из А в В, т.е. до декарнтова произведения А х В. Естественно, что и равенство соответствий можно трактовать как равенставо множестве. В то же время на соответствия можно распространить операции, определяемые для отображений.
Мы рассмотрим здесь две такие операции. Композиция соответствий. Следуя аналогии с композицией отображнений, композитлиеб (произведением) соотввепзстпвиб р С А х В и о С В х С называют соответствие реп = ((х, у): (3» Е В)((х, «) т р) Л ((», у) Е о)) . (13) Поясним построение композиции двух соответствий. Обратимся сначала к отображениям (как частньпя случаям соответствий). Пусть заданы отображения (возможно, частичные): у из А в В и д из В в С. Композиция' у од определяется как отображение из А в С, задаваемое формулой у = д®х)). Тем самым задается график отпображения у" е д, т.е.
множество упорядоченных нар (х, у), таких, что у = д(у(х)). При этом упорядоченная пара (х, у) будет принадлежать графику отображения у од, если и только если найдется элемент» Е В, Необходимо заметить, что в (1] запись доДа) означает д(1(х)), т.е. отображения в композиции пишутся в порядке, обратном тому, в каком опи применяются. Мы же будем везде испольэовать запись 1 е д, полагая, что 1 од(я) = д(1(я)) и порядок записи отображений в композиции совпадает с порядком их применения. Это обуситвлено тем, что композиция отображений определяетсл нами как частный случай композиции соответствий, при записи которой естественным оказывается именно такой порядок.
52 Ь МНОЖЕСТВА И ОТНОШЕНИЯ такой, что я = ~(х) и у = д(х). Таким образом, график ком- позиции отображений у и д есть у 0д= ((х, у): (Зя)(я =У(х) н у =д(з))) = = ((х, у): у = д®х))1. (1.4) Легко видеть, что (1.4) есть частный случай (1.3). Отметим, что при построении композиции отображений обычно предполагают, что пересечение области значений отображения у и области определения отображения д не пусто (В(у ) О Р(д) ~ И), поскольку в противном случае композиция была бы пуста. Для отображений, не являющихся частичными, В(~) С Р(д), так как Р(д) = В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
