Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 15
Текст из файла (страница 15)
ложных высказываний приведите контрпример. а) Если отношения В и Я антисимметричны, то отношение ВО Я антисимметрично. б) Если отношения В и Я антисимметричны, то отношение ВО Я антисимметрично, в) Если отношения В и Я антисимметричны, то отношение В о Я антисимметрично. г) Если отношения В и 5 антисимметричны, то отношение  — Я антисимметрично. д) Если отношения В и Я антисимметричны, то отношение ВЬ Я антиснмметрично.
17. Установите истинность или ложность приведенных ниже высказываний. Для каждого ложного высказывания приведите контрпример. а) Если отношения В и Я транзитивны, то отношение В О 5 транзитивно. б) Если отношения В и Я транзитивны, то отношение ВО Я транзитивно, в) Если отношения В и Я транзитивны, то отношение В о Я транзитивно. г) Если отношения В и Я транзитивны, то отношение  — 5 транзитивно. д) Если отношения В и Я транзитивны, то отношение В Ь Я транзитивно. 16. Установите истинность или ложность приведенных ниже высказываний.
Для 100 ГЛАВА 2. Теороя мноягеотв 18. Постройте граф для каждого из приведенных ниже отношений на А. а) А = (а, Ь,с,сМ,е); В = ((а, Ь), (Ь, а), (Ь, с), (с, Ь), (с, а), (а, с), (гЕ, е), (е, а) ); б) А = (а,Ь,с,д,е); тг = ((а, Ь), (Ь, а), (Ь, с), (с, Ь), (с, а), (сУ, с), (с, а),(а, с)); в) А = (а,Ь,с,й,е); В = ((а,Ь),(Ь,а),(Ь,с),(с,6),(с,д),(д,с),(д,е),(е,д), (Ь, е), (е, 6), (Ь, Н), (Ы, 6) ); г) А=(а,Ь,с,г~); В = ((а, 6), (6, а), (Ь, с), (с, Ь), (с, г~), (д, с), (г~, а), (а, И), (Ь, гМ), (сХ, Ь), (а, с), (с, а) ) .
19. Постройте граф для каждого из приведенных ниже отношений на А. а) А = (а, Ь,с,г1,е); Л = ((а, 6), (Ь,а),(6, с), (с, Ь), (с, й), (И, с), (д,а), (а, Н)); б) А= (а,Ь,с,й,е,г); В = т(а, 6), (Ь, а), (Ь, с), (с, 6), (с, а), (а, с), (Н, е), (е, Ы) ); в) А = (а, Ь,с,д,е); В = ((а, 6), (Ь,а),(Ь, с),(с, Ь), (с, г(),(сК, с), (Н, е), (е, Н), (а, с1), (д, а) ); г) А = (а,Ь,с,с~,е,г"); В = ((а, Ь), (6, а), (6, с), (с, Ь), (с, а), (а, с), (а, е), (е, а), (6, е),(е, Ь),(6,г"),(г", 6),(с, И),(И, с),(с,г'),(г", с), (а, (), ((, а), (е, 1), (1, е)). 20.
Найдите множество вершин, ребер и соответствующее симметричное отношение для графов, изображенных на нижеследующих рисунках. а) б) с г) РАЗДЕЛ 2.5. Отношвния 101 21. Найдите множество вершин, ребер и соответствующее симметричное отношение для графов, изображенных на нижеследующих рисунках. а) б) Е, в) г) 22. Постройте орграфы со следующими свойствами: а) Множество вершин (а,Ь,с,а,е,г") и отношение В для ребер имеет вид В = ((а, 6), (Ь, с), (а, с), (Ь, е), (с, )), (с, д), (а, г), (г, е) ) . б) Множество вершин (а, Ь, с, Н) и отношение Л для ребер имеет вид В = ((6, с), (а, й), (Ь,а), (И, с), (Ь, д),(с, а)).
в) Множество вершин (а, Ь,с,а) и отношение Л для ребер имеет вид В = ((Ь, а), (а, а), (Ь, с), (с, а), (а, с), (Ы, Ь), (г~, а)). г) Множество вершин (а, Ь,с,г),е) и отношение В для ребер имеет вид В = ((а, 6), (а, с), (а, г)), (с, а), (г), е), (е, Н) ). 23.
Постройте орграф со следующими свойствами: а) Множество вершин (а, Ь,с,а,е, г) и отношение В для ребер имеет вид В = ((а, 6), (Ь, с),(г~, с),(д, е),(г, е),(г,а),(6, е)). б) Множество вершин (а,Ь,с,д) и отношение Л для ребер имеет вид В = ((а, с), (а, Ь), (г~, с), (г), Ь), (а, а), (Ь, с), (а, а), (с, с) ) . в) Множество вершин (а, Ь,с) и отношение В для ребер имеет вид В = ((а, 6), (а,а), (6, с), (Ь, 6),(с, с), (с, а)г. г) Множество вершин (а, Ь,с,д,е) и отношение В для ребер имеет вид В = ((а,Ь),(а,с),(а,й),(с,й),(а,е),(6,е)). 24. Найдите вершины и ориентированные ребра приведенных ниже орграфов. 102 ГПАВА 2.
Теория множеств б) а) в) г) 25. Найдите вершины и ориентированные ребра приведенных ниже орграфов. а) 6) М г) в) 26. Приведенное ниже доказательство предположительно показывает, что если отношение В симметрично и транзитивно, то оно и рефлексивно. Является ли это доказательство правильным? Если нет, то почему? РдздеЛ 2.6. частично упорядоченные множвогпев 103 ДОКАЗАТЕЛЬСТВО. Пусть Л вЂ” симметричное и транзитивное отношение на множестве А.
Пусть а Е А и (а,Ь) е В. Поскольку (а, Ь) е В и Л симметрично, (Ь,а) е В. Поэтому, в силу транзитивности В, имеем (а,а) е В, откуда следует, что В рефлексивно. 27. Докажите теорему 2.31. 28. Докажите теорему 2.37. 2.0. ЧАСТИЧНО УПОРЯДОЧЕННЫЕ МНОЖЕСТВА При изложении оставшейся части этой главы будем предполагать известными элементарные свойства целых чисел, действительных чисел и заданных на них функций, хотя формально до настоящего времени они не обсуждались.
ОПРЕДЕЛЕНИЕ 2.44. Отношение В на А есть отношение частичного порядка, если оно рефлексивно, симметрично и транзитивно. Если отношение В на А является отношением частичного порядка, то (А, Л) называют частично упорядоченным множеством, или ЧУ-множеством с порядком В. Если отношение порядка В предполагается по умолчанию, то (А, В) можно обозначать просто через А. В примере 2.35 было показано, что если А — множество положительных целых чисел и отношение В определено условием (х,у) е В, если х делит у нацело, то Л есть отношение частичного порядка, а (А, Л) — ЧУ-множество. ПРИМЕР 2.45. Пусть С = (1,2,3), а Х вЂ” множество всех подмножеств множе- ства С: Х = Р(С) = (а, (Ц, (2), (3), (1,2), (1,3), (2,3), (1,2,3)).
Определим отношение В на Х посредством (Т, У) е В, еали Т с У. Таким образом, И2),(1,2)) Е В, поскольку (2) С (1,2) и ((2,3),(3)) ф Л, поскольку (2,3) Я (3). Можно легко проверить, что Л вЂ” отношение частичного порядка, а (А, В) — ЧУ-множество. П ПРИМЕР 2.46.
Пусть 5 — множество действительных чисел, а Л~ — отношение, определенное условием (к,у) Е Лы если х < у. Легко показать, что Вг— отношение частичного порядка, а (5, Лг) — ЧУ-множество. П Частичное упорядочение принято обозначать через <, а частично упорядоченное множество — через (о', <), где < — частичный порядок на множестве о'. Если (а, Ь) Е<, то, согласно введенным ранее обозначениям для отношений, а < Ь.
104 ГЛАВА 2. Теория множвспи ОПРЕДЕЛЕНИЕ 2.47. Два элемента а и Ь частично упорядоченного множества (Я, <) сравнимы, если а < Ь или 6 < а. Если каждые два элемента частично упорядоченного множества (Я, <) сравнимы, то (Я, <) называется вполне упорядоченным множеством, или цепью. ПРИМЕР 2.48. Пусть Т вЂ” множество положительных делителей числа ЗО и <, есть отношение т <г и, если тп делит п нацело. Целые числа 5 и 15 сравнимы, поскольку 5 делит 15 нацело, а 5 и 6 — нет.
П ПРИМЕР 2.49. Пусть А — множество целых чисел и В =«а — отношение х <з у, если х меньше или равно у. Упорядоченное множество (А, <з) является цепью. П ПРИМЕР 2.50. Пусть Я вЂ” множество всех подмножеств множества (а, Ь,с), а <з есть отношение частичного порядка, определенное в примере 2.45. Множества (а,6), 9 и (а,Ь,с) сравнимы, но (а,Ь) и (Ь,с) таковыми не являются.
Таким образом, (Я, <з) — ЧУ-множество, однако цепью не является. П Для изображения частично упорядоченных множеств имеется графический аппарат, известный как диаграммы Гессе. Для заданного ЧУ-множества (А, <з) диаграмма Гессе состоит из совокупности точек и линий, в которой точки представляют элементы А, и если а < с для элементов а и с множества А, тогда а помещено ниже с, и они соединены линией, если не существует такое Ь Ф а,с, что а < Ь < с. Если рассмотрение отношений ограничено отношениями частичного порядка, для них диаграммы Гессе представляют собой просто ориентированный граф, в котором петли не указаны; и если а < Ь < с, тогда линия от а к с не указана.
Например, диаграмма Гессе, соответствующая множеству (Т, <,), описанному выше, показана на рис. 2.23. Диаграмма Гессе, представляющая (Я, <з), показана на рис. 2.24. А на рис. 2.25 представлена диаграмма Гессе для цепи с четырьмя элементами. 15 10 Рис. 2.23 РЯЗК2ЕЛ 2.б. Частично упорядоченные множества 105 (Ь,с) (с) (а) Рис. 2.25 Рис. 2.24 ° УПРАЖНЕНИЯ 1.
Какое из приведенных ниже отношений В является отношением частичного порядка на А = (а, Ь,с,аК)? а) В = ((а, а), (Ь, Ь), (с, с), (д, сК), (а, с), (Ь, с), (с, сК), (а, сК), (Ь, сК) ); б) В = ((а, а), (6, 6), (с, с), (сК, сК), (а, Ь), (Ь, с), (с, Н), (Ы, а) ); в) В = ((Ь, 6), (с, с), (Н, Н), (а, с), (Ь, с), (с, с~), (а, сК), (Ь, гК) ); г) В = К,(а,а), (Ь, Ь)„ (с, с),(сК, Н), (а, 6).
(Ь, с), (а, с),(а, Н), (6, д), (с, Н)). 2. Какое из приведенных ниже отношений В является отношением частичного порядка на А = (а, 6, с, К)? а) А — множество всех людей, а отношение В определено условием: хВу, если х старше у. б) А — множество всех граждан Соединенных Штатов, и В определено условием: хВу, если х имеет больший номер карточки социального страхования, чем у. в) А — множество целых чисел, В определено условием: хВу, если х > 2у.
г) А — множество всех людей, и В определено условием: хВу, если х и у являются братом и сестрой. д) А — множество всех упорядоченных пар положительных целых чисел, и (а, 6)В(с, д), если а < с, и если а = с, то 6 < гК. 3. Постройте диаграммы Гессе для следующих ЧУ-множеств (А, <), где а) А = (а, Ь,с,с() и < = ((а, а), (6, 6), (с, с), (й, сК), (а, с), (Ь, с), (с, Н), (а, Ы), (Ь, Н) ); б) А = (а,Ь, с, д) и < = ((а, а), (Ь 6), (с, с), (сК, й), (а, с), (Ь,с)); в) А = (а, Ь, с, И) и < = ( (а, а), (6, 6), (с, с), (ак, сК) ); г) А = (а,Ь,с,й) и < = ((а, а), (Ь, 6), (с, с), (Н, И), (а, 6), (Ь, с), (а, с), (с, с~), (а, гК), (6, И) ) .
4. Постройте диаграммы Гессе для следующих ЧУ-множеств (А, <), где а) А = (1,2,3,4,5,6,7,8,9,10,1Ц и х < у, если х делит у нацело. 106 ГПАВА 2. теория множеств б) А = В х В, где В = 11, 2, 3, б, ). Определим а <, Ь, если а делит Ь нацело, и (а, 6) < (с, д), если а <1 с, и если а = с, то 6 <г Ы. в) А — множество положительных целых чисел, которые делят 27 нацело, и к < у, если к делит у нацело. г) А — множество положительных целых чисел, которые делят 64 нацело, и к < у, если к делит у нацело. б. Перечислите элементы множества А и выразите < как множество упорядоченных пар для каждой из приведенных ниже диаграмм Гессе: а) ,М 'Ф в) г) а Ь с д) Рс~ б.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
