Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 14
Текст из файла (страница 14)
Симметричное замыкание Л есть наименьшее симметричное отношение на А, содержащее В как подмножество. Транзитивное замыкание Л есть наименьшее транзитивное отношение на А, содержащее Л как подмножество. ТЕОРЕМА 2.37. Пусть Л вЂ” отношение на множестве А и 1 = (х: х = (а, а) для некоторого а е А).
Тогда а) ЛО 1 есть рефлексивное замыкание Л; б) ЛОВ есть симметричное замыкание Л; в) если А — конечное множество, содержащее и элементов, то отношение ЛО Лз и Лз О .. и Л" есть транзитивное замыкание Л. ДОКАЗАТЕЛЬСТВО. Доказательство утверждений (а) и (б) предоставляется читателю. Обозначим транзитивное замыкание Л через Л.
Для доказательства утверждения (с) сначала покажем, что Л 0 Лз 0 Лз 0 и Л" ~ Л. Проведем индукцию по и. Для и = 1 имеем Л С Л, что достоверно истинно. Допустим, что Л О Лз О Лз и О Л" С Л. Необходимо показать, что ЛО Лз О Лз и и Л"+' С Л или, что то же самое, Л"+' с. Л. Пусть (а,с) е Л"+'. Тогда существует 6 такое, что (а,6) е Л" и (Ь,с) е Л. Но, согласно индуктивному предположению, (а, Ь) и (Ь,с) Е Л.
Поскольку Л транзитивно, (а,с) Е Л. Поэтому В О Лз и Лз и . О Ль+' с Л. для того, чтобы показать, что Л с ЛОЛ~ОЛз0 ОЛь+', просто покажем, что ЛОЛзОЛзО . ОЛь+' транзитивно. Пусть (а,Ь) е ЛУ и (Ь,с) е В". Тогда (а,с) е Ю+". Если а = с, утверждение доказано. В противном случае существуют Ьз,Ьз,64,...,Ь ч.ь г Е А такие, что (а,Ьз),(6з, Ьз), (Ьз, Ьв),,(6,+ь-з, Ьь„,,),(Ь,„ь ыс) Е Л.
Обозначим а через Ьд, а с через Ьу+ь. Если некоторые из Ь, равны, например, Ьр — — Ьв, из указанной выше последовательности упорядоченных пар, находящихся в отношении Л, можно удалить (Ьр,Ьр+,),(Ьр+,,Ьр.ьз),..., (Ьв ыЬв) и после этого получить последовательность а, Ьз, Ьз, Ьр,, Ьв,..., Ь,ьь „с, в которой каждый предыдущий элемент находится в Л-отношении к последующему. Так можно продолжать до тех пор, пока все элементы окажутся отличными, но при этом каждый из них будет нахо- РЯЗДЕЛ 2.о. Отношения 95 диться в В-отношении к последующему. Поскольку во множестве А существует только и различных элементов, получаем, что (а,с) Е В" и ЛОВз1и)сзО О)с"+' транзитивно.
Одним из наглядных способов представления конечного антирефлексивного симметричного отношения является граф. В дальнейшем мы убедимся, что легко установить связь между конечными антирефлексивными симметричными отношениями и графами. Однако, помимо этого конкретного использования, графы получили самостоятельное развитие, и в настоящее время теория графов является одной из важных областей математики. ОПРЕДЕЛЕНИЕ 2.39. Граф есть конечное множество )г, называемое множеством вершин, на котором задано симметричное антирефлексивное отношение В и выделено множество Е двухэлементных подмножеств Ъ', определяемое как (а,Ь) Е Е тогда и только тогда, когда (а, Ь) Е Л и а З~ Ь. Множество Е называется множеством ребер. Всякий элемент Е называется ребром.
Граф обозначается С(Ъ;Е). Говорят, что элементы а и Ь графа Ъ' соединены или связаны ребром (а, Ь), если (а, 6) Е Е. Конечный граф обычно изображается при помощи диаграммы, в которой вершины представлены точками, а ребра, соединяющие две вершины, — линиями между этими точками. ПРИМЕР 2.39. Граф, в котором множество вершин Ъ' = (а, Ь, с), а Е = ((а, Ь), (6, с)), может иметь вид, как на рис. 2.18 или рис. 2.19.
Рис. 2.19 Рис. 2.!8 В = ((а, Ь), (Ь, а), (Ь, с), (с, Ь)). ПРИМЕР 2.40. Граф, в котором множество вершин )с = (а, Ь,с, д,е), а Е = ((а, Ь), (а, е), (Ь, е), (6, с1), (Ь, с), (с, с1) ), имеет диаграмму, изображенную на рис. 2.20. )с = ((а, 6), (6, а), (е, а), (а, е), (е, 6), (6, е), (Ь, д), (с1, Ь), (Ь, с), (с, Ь), (с1, с), (с,с1)).
96 ГЛИНА 2. Теория множеств Мы видели, что граф описывал симметричное отношение Л на множестве Ъ', в котором никакой элемент не находился в отношении с самим собой. Для отношения Л более общего вида необходимо представление элемента (а,6) Е В, для которого возможно (Ь,а) ф В. Необходимо также иметь возможность представлять элемент (а,а) е В. Все сказанное можно осуществить с помощью ориентированного графа. ОПРЕДЕЛЕНИЕ 2.41. Ориентированный граф, или орграф С, обозначаемый С(КЕ), состоит из множества $' вершин и отношения Е на Ъ', называемого множеством ориентированных ребер, или просто ребер, если понятно, что граф ориентирован. Элемент множества Е называется ориентированным ребром. Если (а, Ь) е Е, тогда а называется начальной вершиной (а, 6), а Ь— его конечной вершиной.
Обратите внимание, что, в отличие от неориентированного графа, в случае ориентированного графа мы допускаем наличие петель. Причин этому две. Вопервых, ориентированные ребра естественным образом включаются в наше определение, поскольку петля при вершине а есть просто ребро (а,а). Этого нельзя было сделать в случае неориентированного графа, поскольку его ребра имеют вид (а, Ь), так что петля имела бы вид (а, а). Во-вторых, вообще говоря, элементы могут находиться в отношении к самим себе, что для множеств не имеет смысла, поскольку любой элемент присутствует во множестве только один раз.
Тем не менее, дальнейшее рассмотрение покажет, что петли в ориентированных графах встречаются чаще, чем в неориентированных. Ребро (а, 6) орграфа обозначается на диаграмме стрелкой от а к Ь. Заметим, что в простом графе ребро представляется двухэлементным подмножеством, чтобы подчеркнуть, что ребро как отношение симметрично, тогда как в орграфе ребро представлено упорядоченной парой, чтобы подчеркнуть то, что порядок имеет значение, и то, что (а, Ь) может быть ребром диаграммы, а (Ь,а) — нет.
ПРИМЕР 2.42. Орграф с вершинами Ъ' = (а, Ь,с) и ребрами Е = ((а, а), (а, Ь), (Ь, с), (с, Ь), (с, а)) показан на рис. 2.21. ПРИМЕР 2.43. Орграф с вершинами Ъ' = (а,Ь,с,й) РАЗДЕЛ 2.5. Отношения 97 и ребрами Е = ((а, Ь), (Ь, с),(с, с), (Ь, Н), (Н, Ь), (с, д), (д, а)) показан на рис. 2.22. Р .ггг ° УПРАЖНЕНИЯ В = ((1, 7), (4, 6), (5, 6), (2, 8) ); В = ((6, 10),(6, 11),(7, 10), (8, 13)); Т = ((11, Ь), (10, Ь), (13, в), (12, П), (13, О)) ).
Определите отношения: а) В'иВ', в) ВоВ 'иВ 'оВ; д) Т.(ВоВ); ж) (Т о В) о В. 4. Пусть А = ((Ь,а),(с,е),(а,г), (1,о)(д,и)) и В = ((и, а), (ш, е), (х, г), (у, о)(з, и)). а) Опишите отношение А '. б) Опишите отношение В в) Опишите отношение А ' о В. г) Опишите отношение В ' о А. б) В о В; ) В'~В'; е) ТоВ; 1. Найдите область определения и множество значений отношений: а) ((а, 1),(а, 2), (с, 1), (с, 2), (с, 4), (в), 5)); б) ((1,2), (2,4), (3,6), (4,8),...); в) ((х,у):х,уЕтти х=у ).
2. Найдите область определения и множество значений отношений; а) ((а, 1),(а, 2), (а, 3),(а, 4), (а, 5),(а, 6))„ б) ((х,у):х,уЕ1 их +у <16); в) ((х, у); 0 < х, у < 10 и х > 2у). 3. Пусть А = (1,2,3,4,5); В = (6,7,8,9); С = (10, 11, 12, 13); Р=(П,аО,*). Пусть В С А х В, В С В х С и Т С С х Р определены следующим образом 98 ГПАВА 2. Теория множеств Пусть отношения У, Ъ' С?? х В определены указанным ниже способом Ьг = ((х, у): у = х + 5)) и Ъ' = ((х, у): у = Зх). а) Опишите отношение Ьг с $', б) Опишите отношение Ъ' о Ьг, в) Опишите отношение У г) Опишите отношение Ъ' д) Найдите область значений бг.
Пусть А = (а, Ь, с,г1,е). Опишите наименьшее рефлексивное отношение на множестве А. Пусть А = (а,Ь,с,г1,е) и Я = ((а,а),(а,Ь),(Ь,с),(Ь,г1),(с,е),(е,г1),(с,Ь)). а) Опишите наименьшее симметричное отношение на А, содержащее Я. б) Опишите наименьшее рефлексивное и симметричное отношение на А, содержащее Я.
в) Опишите наибольшее симметричное отношение, содержащееся в 5. г) Опишите наименьшее транзитивное отношение на А, содержащее Я. 8. Пусть А = (а, Ь,с,г1,е), а Я,Т,У и Ъ' — отношения на А, где Я = ((а,а),(а, 6),(Ь,с),(Ь,И), (с,е),(е,с1),(с,а)); Т = ((а, Ь), (6, а), (6, с), (Ь, сМ), (е, е), (сХ, е), (с, Ь) ); У = ((а, 6),(а,а),(Ь,с),(Ь,Ь),(е,е),(Ь,а),(с,6),(с,с),(д,гК),(а,с),(с,а)); Ъ' = ((а, 6), (Ь, с), (6, 6), (е, е), (Ь, а), (с, Ь), (И, г?), (а, с), (с, а)).
а) Какое из отношений является симметричным? б) Какое из отношений является рефлексивным? в) Какое из отношений является транзитивным? г) Какое из отношений является антисимметричным? 9. Пусть А = (а, Ь,с,д, е), а Я, Т, У и Ъ' — отношения на А, где Я = ((а,а), (а, Ь), (Ь, с), (Ь, И), (с, е), (е, И), (с, а) ); Т = ((а, Ь), (6, а),(Ь, с),(Ь,сУ), (е, е), (Н, е), (с, Ь)); У = ((а, 6), (а, а), (Ь, с), (Ь, 6), (е, е), (Ь, а), (с, Ь), (с, с),(д, г1), (а, с), (с, а)); Ъ' = ((а, 6), (Ь, с),(Ь, Ь),(е, е),(Ь,а), (с, 6),(с?,гК), (а, с),(с, а)). а) Опишите Уй Ъ'. б) Опишите Я О Т. в) Опишите У вЂ” Т. г) Опишите У Ь Я. 10.
Докажите, что пересечение рефлексивных отношений рефлексивно 11. Докажите, что пересечение симметричных отношений симметрично. 12. Пусть А = (а, Ь, с, д, е). а) Опишите отношение на А, которое рефлексивно, но не является ни симметричным, ни транзитивным. б) Опишите отношение на А, которое симметрично, но не является ни рефлексивным, ни транзитивным. РА377ЕП 2.о. Отношения 99 в) Опишите отношение на А, которое транзитивно, но не является ни рефлексивным, ни симметричным. Пусть А = (а,б,с,д,е). а) Опишите отношение на А, которое рефлексивно и симметрично, но не является транзитивным. б) Опишите отношение на А, которое симметрично и транзитивно, но не является рефлексивным.
в) Опишите отношение на А, которое рефлексивно и транзитивно, но не является симметричным. Установите истинность или ложность каждого из приведенных ниже высказываний. Для каждого ложного высказывания приведите контрпример. а) Если отношения В и Я рефлексивны, то отношение В и 5 рефлексивно. б) Если отношения В и 5 рефлексивны, то отношение В О Я рефлексивно. в) Если отношения В и 5 рефлексивны, то отношение В о Я рефлексивно. г) Если отношения В и Я рефлексивны, то отношение  — 5 рефлексивно. д) Если отношения В и Я рефлексивны, то отношение В Ь 5 рефлексивно. 13. 14.
15. Установите истинность или ложность каждого из следующих высказываний Для ложных высказываний приведите контрпример. а) Если отношения В и Я симметричны, то отношение ВО Я симметрично. б) Если отношения В и Я симметричны, то отношение ВО Я симметрично. в) Если отношения В 5 симметричны, то отношение В о Я симметрично. г) Если отношения В и 5 симметричны, то отношение  — Я симметрично. д) Если отношения В и Я симметричны, то отношение В Ь Я симметрично.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
