341_1- Сборник задач по математике для втузов. В 4-х ч. Ч.1_ (ред) Ефимов А.В, Поспелов А.С_2001 -288с (987777), страница 29
Текст из файла (страница 29)
Доказать, что о — отношение эквивалентности, а т— отношение порядка. 4.22. Доказать, что в частично упорядоченном множестве наибольший элемент является максимальным. Привести пример частично упорядоченного множества, в котором максимальный элемент не является наибольшим.
4.23. На множестве И'1 (Ц введем отношение В: аЛЬ, если Ь делится на а без остатка. Доказать, что  — частичный порядок. Есть ли в данном множестве наибольший, наименьший элемент? Есть ли в нем максимальные и минимальные элементы (относительно Л)? Графической интерпретацией па плоскости отношения о, заданного иа конечном множестве А = (аы аэ,..., а„) (кпаче графом отношения) называется диаграмма, в которой элементы аы аг, ..., а„изображаются точками, обозначаемых теми же буквами, что и элементы множества А, при этом направленная стрелка из а; в а изображается, если (аь а ) Е а. Например, отношение о = ((1, 2), (2, 3), (1, 4), (3, 3)) на множестве А = (1, 2, 3, 4, 5) изображается следующим графом (см. рис. 35). Если отношение о симметрично, то вместо двух направленных ребер (а, Ь~ и (Ь, а~ обычно рисуют одно (а, Ь) без направления.
При изображении графа отношения порядка, заданного на множестве Х, при х < у точку х располагают ниже точки у. Если имеются линии ог Гл. 4. Элемеяты общей алгебры 168 х к у и от р к г, то линию, соединяющую х и г, не рисуют. Аналогично поступают и для более длинных цепочек элементов. (а,Ь,с) (а, Ь) (Ь, с) (с) Рис. Зб Рис. 35 Пример 4. Построить граф отношения включения С на множестве всех подмножеств множества (а, Ь, с). «) Множество всех подмножеств множества (а, Ь, с) содержит восемь элементов: й~, (а), (Ь), (с), (а, Ь), (а, с), (Ь, с), (а, Ь, с). В соответствии с замечанием 2 в цепочках включений не изображаем лишние ребра.
Так, Я С (Ь) С (а, Ь) С (а, Ь, с), но линии ст И к (а, Ь) и (а, Ь, с) опускаем. Полученный граф отношения изображен на рис. Зб. (> 4.24, Пусть А = (1, 2, ..., 10), Я вЂ” отношение делимости на множестве А, введенное в задаче 4.23. Построить граф этого отношения. Найти максимальные и минимальные элементы А (относительно В).
4.25, Пусть А = (3, 4, ..., 10). Введем отношение о, считая, что для а, Ь е А ааЬ, если существует некоторое с Е А такое, что а и Ь делятся на с без остатка. Построить граф этого отношения. 4.26'. Доказать, что всякий частичный порядок т на конечном множестве может быть продолжен до линейного (т.е. существует такой линейный порядок т', что т С т'). Пусть множество А = А1 х... х А„, причем на каждом из множеств Аы ..., А„авданы отношения частичного порядка. На множестве А можно определить отношения порядка < и -С: а) (аы..., а„) < (а'„..., а'„), если Ч( а; < а';; б) (аы...,а„) -С(а~,...,а'„),еслилибоа1 =а(, ..., а; 1 =а,' ы а; < а'; для некоторого (, либо а; = а'; для всех (.
Порядок .< на множестве А называется лексикографическии (по такому приндипу упорядочены слова в словаре). 4.27. Доказать, что отношение < на множестве А = А~ х... хА„ является отношением частичного порядка. 4.28, Доказать, что отношение -С на множестве А = А1 х...хА„ является отношением частичного порядка. з 1. Бинарные отношения и алгебраические операции 169 4.29. Доказать, что если все А; линейно упорядочены, то А относительно отношения -< также линейно упорядочено.
4.30. Построить графы отношений из задач 4.27 и 4.28 для множества Ат х Аэ, где Ат = (а, Ь, с ~ а < Ь < с), Аэ = (и, о ~ и < < о). 3. Операции над бинарными отношениями. Пусть ст, т С А х А— бинарные отношения. Так как бинарные опюшения являются подмножествами множества А х А, то можно брать их пересечение и П т, объединение а О т и разность а1т.
Обратпяььи отношением к бинарному отношению о на множестве А называется отношение о ' = ((р, х)! (х, р) Е о). Противоположным отппошепаелт к бинарному отношению о на множестве А называется отношение У = (А х А) 1о. Очевидно, (а, Ь) Е о сь сФ(а, Ь) фп. Произведением бинарных отппошепиб и и т называется отношение пт = ((х, у) ( В х: (х, г) Е и, (х, р) Е т) . Обозначим через ль отношение равенства на А, т.е.
Ь = ((а, а) ! а Е Е А). 4.31. Доказать следующие свойства операций над бинарными отношениями: з) (ОРа)ст = И(Рост)~ 6) (ПРа)п С ()(Рая) ° 4.32. Выразить с помощью операций пт, о 1 и отношения С следующие свойства бинарных отношений: а) рефлексивность; б) симметричность; в) транзитивность; г) антиснмметричность. Пример 5. Выяснить, является ли транзитивным отношение, которое одновременно симметрично и антисимметрично. 0 Пусть о — симметричное и антисимметричное отношение. Симметричность отношения и равносильна условию о ' = о, а антисимметричность — условию о По ' С тл. Из этих двух условий следует, что и С Ь.
Наконец, пэ = по С Ьп = о, поэтому п транзитивно. сь Пример 6. Найти какое-нибудь транзитивное отношение о такое, что оэ С о (т.е. оэ С т и оэ ф о). < Надо найти элементы а, Ь такие, что (а, Ь) Е о, но не существует такого х, для которого (а, х), (х, Ь) е о. Примером может служить отношение < на множестве целых чисел. Оно транзитивно и для него (3, 4) Е о, но (3, 4) ф пэ. с> Обозначим через й универсальное отношение на множестве А: й = = А х А. П р и м е р 7. Пусть т3 — отношение равенства на множестве А, а о— произвольное отношение. Чему равны произведения т1о, ом, йойу < Заметим, что (а, Ь) е Ьп <=ь Вх (а, х) е Ь, (х, Ь) е и еь а = х, (х, Ь) Е о еь (а, Ь) е и.
Значит, Ьо = о. Аналогично доказывается, Гл. 4. Элементы обшей алгебры 170 что абс = о. Яетрудно видеть, что если в а есть хотя бы один элемент (а, Ь), то отношение йой содержит все пары (х, у), где х, у й А. Таннм образом, ( Й, если сг ф йг, Йсгй = С( !> с( зг, если о = а.
Пример 8. Доказать, что если о ' С о, то о ' = о. 0 Так как а ' С о, то (о ') ' С о ', т.е. о С о '. Следовательно, сг '=о.Ь 4.33. а) Будет ли пересечение отношений эквивалентности также являться отношением эквивалентности? б) Будет ли объединение отношений эквивалентности также являться отношением эквивалентности? в) Будет ли пересечение отношений порядка также являться отношением порядка? г) Будет ли объединение отношений порядка также являться отношением порядка? д) Будет лн произведение двух отношений эквивалентности также являться отношением эквивалентности? е) Будет ли произведение двух отношений порядка также являться отношением порядка? Транзитиеиьгм замыиаиием аг бинарного отношения о на множестве А называется наименьшее транзнтнзное отношение, содержащее а. 4.34.
Доказать следующие свойства транзитивного замыкания: а) ас — пересечение всех транзитивных отношений, содержащих о; б) сгс, и, г1,сгз и в) (а, Ь) Е сг <=> Зсы ..., с„е А, что (а, с1) е гт, (с„, Ь) е о и (с;,с;+1) Есг прис'=1, ...,и — 1. В задачах 4.35 — 4.37 доказать, что для любых отношений р, о, т на одном и том же множестве справедливы указанные равенства либо включения. 4.35**. (ро)т = р(сгт). 4.36.
(рсг) г = о ~р 1. 4.37'. р(опт) — — рсг0рт, р(сгПт) С ройрт. Привести пример отношений, для которых р(сг г1т) ~ рсг П рт. Пример 9. Пусть о — отношение на множестве К, определенное условием ааЬ <:~ ~а — Ь~ = 1. Что нз себя представляет транэитивное замыкание отношения о? 0 Условие (а, Ь) е о' равносильно существованию элементов хы хэ, ... ..., х„таких, что (а-хг! = ~хг — хэ~ = ... = ~х„— Ь| = 1.
Таким образом, (а, Ь) Е а' в том и только том случае, когда а — Ь Е Е. с> Э 1. Бинарные отношения и алгебраические операции 171 4.38. Доказать, что транзитивное замыкание отношения о— это наименьшее транзитивное отношение, содержащее о в качестве подмножества (или, что то же самое, пересечение всех транзитивных отношений, содержащих о). В задачах 4.39 и 4.40 найти транзитивное замыкание заданных отношений: 4.39. хо у, если х = у — 1 (на множестве Ж); 4.40. хну, если у = йх, где й — простое число илн 1 (на множестве 1Ч). 4.41.
Доказать следующие равенства для отношений параллельности и перпендикулярности, заданных на множестве всех прямых на плоскости (при этом считается, что любая прямая параллельна самой себе): Г'=!1, .1. '=~., !! !1 =.1 1=В !! 1=.1., 1!1 =.1.. Какие из этих равенств остаются справедливыми для прямых в пространстве? 4.42.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
