Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 13
Текст из файла (страница 13)
Итак, всякий раз, доказывая теорему относительно булевой алгебры, мы фактически доказываем две теоремы: саму теорему и двойственную ей (если они отличаются). Таким образом, доказывая одну теорему, вторую теорему получаем даром. Используя правила теории множеств (теорема 2.18), легко можно показать, что подмножества произвольного множества А образуют булеву алгебру, где О и о аналогичны бинарным операциям . и +, соответственно, а А — В соответствует В'. Множество А является единичным элементом 1, а пустое множество есть нулевой элемент 0 этой булевой алгебры. ° УПРАЖНЕНИЯ 1. Докажите непосредственно, что х х = х. 2.
Докажите непосредственно, что х 0 = О. 3. Докажите непосредственно, что х. (х+ у) = х. 4. Докажите непосредственно, что 0' = 1. 5. Докажите непосредственно, что 1' = О. 6. Найдите выражения, двойственные приведенным ниже: а) х у'+ х г'+ у х', б) х.у г'+х у' в) х у (х+О+ (г 1)). 7. Найдите выражения, двойственные приведенным ниже; а) (х + у') (г' + у)', б) (1+х) у+х у' г; в) (х.у+1) (О+х) г.
(х у) . (х'+ у') = ((х. у) . х') +.((х. у) . у') = ((у.х) ')+И у).у') = (у (х х')) + (х (у у')) = (у 0) (х . 0) = 0.0 = (х. у) + (х'+ у') = (х'+ у') + (х. ((х' + у') + х) (х + (х' + у') ) Их + х') + у') ((х + х') + у') (1 + у') (х' + (у'+ 1) . (х'+ 1.1= 1. закон коммутативности закон дистрибутивности закон коммутативности закон ассоциативности закон коммутативности закон дополнения закон коммутативности свойство констант 90 ГЛАВА 2.
Теория множеств 8. Докажите, что если ху = хз и х'у = х'з, то у = з. 9. Сформулируйте задачу, двойственную к предыдущей. 10. Докажите, что ху' = О тогда и только тогда, когда ху = х. 11. Сформулируйте задачу, двойственную к предыдущей. 12. Докажите, что нулевой элемент О и единичный элемент 1 определены своими свойствами единственным образом. 13.
Множество называется кононечным, если его дополнение конечно. Пусть универсальное множество Р есть множество всех конечных и всех коконечных подмножеств множества положительных целых чисел. Докажите, что подмножества У вместе с операциями объединения, пересечения и дополнения образуют булеву алгебру. 2.5. ОТНОШЕНИЯ Среди рассмотренных операций над множествами было декартово произведение множеств А и В, которое обозначается через А х В. Оно представляет собой множество ((а, Ь): а е А и Ь е В). Таким образом, множество А х В состоит из всех упорядоченных пар, имеющих в качестве первой компоненты элемент из А, а в качестве второй компоненты — элемент из В.
ОПРЕДЕЛЕНИЕ 2.25. Отношением В множеств А и В называется произвольное подмножество А х В. Если (а, 6) Е Б., это записывают как аКЬ; при этом говорят, что а и 6 находятся в отношении Б., или просто, что а относится к Ь. Если А = В, то отношение есть подмножество А х А; такое отношение называют бинарныи отношением на А. В дальнейшем на множестве будем обычно рассматривать бинарные отношения, поэтому вместо термина "бинарное отношение" будем употреблять термин "отношение".
Если А = (1,2,3), а В = (г, в), так что А х В = ((1, т), (1, з), (2, т), (2, з), (3, г), (3, в)), тогда В = ((1,г),(1,в), (3, в)) есть отношение множеств А и В. Можно также записать Зйз, поскольку (3, з) е В. Множество А х В содержит шесть элементов, поэтому существует 2в = 64 подмножества множества А х В. Следовательно, существует 64 различных отношения на А х В В примерах и упражнениях, приведенных ниже, предполагаются известными элементарные свойства действительных и целых чисел, а также заданных на этих числах функций. Вот несколько примеров отношений: 1.
Все множество А х В есть отношение множеств А и В. 2. Если А — множество действительных чисел, то ((х, у) Е А х А; ха+уз = 4) есть бинарное отношение на А. РЯЗДЕЛ 2.5. Отношеная 91 3. Пусть А — множество товаров в магазине, а  — множество действительных чисел. Тогда ((х, у) е А х В; у — цена х) — отношение множеств А и В. 4. Пусть А — множество женщин, а  — множество мужчин, тогда ((х,у): у является мужем х) есть отношение множеств А и В. 5.
Если А — множество людей, то ((х, у) е АхА: у является родственником х) есть бинарное отношение на А. ОПРЕДЕЛЕНИЕ 2.26. Область определения отношения В на А и В есть множество всех х Е А таких, что для некоторых у е В имеем (х, у) е В. Другими словами, область определения В есть множество всех первых координат упорядоченных пар из В. Множество значений отношения В на А и В есть множество всех у е В таких, что (х,у) е В для некоторого х е А.
Другими словами, множество значений В есть множество всех вторых координат упорядоченных пар из В. В примерах отношений, приведенных выше, в частности, в (1), область определения есть все множество А, а множество значений — все множество В. В (2) как область определения, так и множество значений совпадают с множеством (г: — 2 ( г ( 2). В (3) область определения есть множество А, а множество значений есть множество всех действительных чисел, каждое из которых совпадает с ценой некоторого товара в магазине. В (4) область определения есть множество всех замужних женшин, а множество значений — множество всех женатых мужчин. В (5) область определения и множество значений есть множество всех людей, имеющих родственников. С каждым отношением В на А х В связано отношение В ~ на В х А.
ОПРЕДЕЛЕНИЕ 2.27. Пусть В С А х В есть отношение на А х В. Тогда отношение В ' на В х А определяется следующим образом: В ' = ((Ь,а): (а, Ь) б В). Другими словами, (Ь,а) е В ' тогда и только тогда, когда (а, Ь) е В или, что равносильно, ЬВ 'а тогда и только тогда, когда аВЬ. Отношение В ' называется обратным отношением к данному отношению В.
Пусть В = ((1,г), (1, з), (3, з)), тогда В ' = ((г, 1), (з, 1), (з,3)). Пусть В— отношение ((х,у): у является мужем х), тогда В ' — отношение ((х,у): у— жена х). Пусть  — отношение ((х, у): у является родственником х) либо В— отношение ((х, у): ха+ уз = 4), тогда В ' = В. Имея два заданных отношения, можно образовать новые отношения указанным ниже способом. 92 ГПАВА 2. теория множеств ПРИМЕР 2.29.
Пусть А = (1,2,3), В = (х,у), а С = (П,Ь,О,*)„и пусть отношения В на А х В и 5 на В х С заданы в виде; В = ((1, х), (1, у), (3, х)); 5 = ((х,П),(х,ь),(у,О),(у,*)) Тогда 5 о В = ((1, П), (1, Ь), (1, ()), (1,*), (3, П), (3, Ь)), поскольку из (1,х) ~ В и (х, П) ~ 5 следует (1, П) ~ 5 о В; из (1,х) Е В и (х, Ь) Е 5 следует (1,Ь) Е 5 о В; из (1, у) Е В и (у, О) Е 5 следует (1, О) Е 5 о В; из (3, х) Е В и (х, сз) е 5 следует (3, Ь) е 5 о В.
ПРИМЕР 2.30. Пусть В и 5 — бинарные отношения на множестве положительных целых чисел, заданные в виде 5 = ((х,х + 2):х — положительное целое число) и В = ((х,ха): х — целое положительное число). Тогда 5оВ = ((х,ха+2): х— положительное целое число) и В о 5 = ((х, (х+ 2)з): х — положительное целое число).
П ТЕОРЕМА 2.31. Композиция отношений ассоциативна; т.е., если А, В и С— множества и если В С А х В, 5 С В х С и Т С С х Р, тогда То(5оВ) = (То 5) оВ ДОКАЗАТЕЛЬСТВО. Покажем сначала, что Т о (5 о В) С (Т о 5) о В. Пусть (а, 0) Е Т о (5 о В), тогда существует такое с Е С, что (а, с) Е 5 о В и (с, Н) е Т. Поскольку (а,с) е 5 о В, существует такое Ь е В, что (а, Ь) е В и (Ь,с) е 5. Поскольку (Ь,с) е 5 и (с,д) е Т, (Ь,И) е Т о 5. Поскольку (Ь,Н) е Т о 5 и (а, Ь) Е В, (а,й) Е (Т о 5) о В.
Таким образом, Т о (5 о В) С (То 5) о В. Вторая часть доказательства, показывающая, что (Т о 5) о В ~ Т о (5 о В), аналогична и предоставляется читателю как упражнение. Теперь рассмотрим специальные свойства отношений на А. РАЗДЕЛ 25.
Отношения 93 ОПРЕДЕЛЕНИЕ 2.32. Отношение В на А х А называется рефлексивным, если (а, а) принадлежит В для всех а из А. Отношение В называется антирефлексивныи, если из (а, Ь) Е В следует а ф Ь. Отношение В симметрично, если для всех а и Ь, принадлежаших А, из (а,0) е Л следует, что (Ь,а) е В. Отношение В транзитивно, если для всех а, 0 и с из А из того, что (а, Ь) Е Л и (Ь, с) е В, следует, что (а, с) Е В. Отношение В называется антисилгметричным, если для всех а и Ь из А, из принадлежности (а, 0) и (Ь,а) отношению В следует, что а = Ь. ПРИМЕР 2.33.
Пусть А = (1,2,3,4,5,6) и пусть отношение В| С А х А есть множество В1 = ((1, 1), (2,2), (3,3), (4,4), (5,5), (6,6), (1,2), (1,4), (2, 1), (2,4), (3,5), (5,3), (4,1), (4,2)1. Отношение Вг Рефлексивно, т.к. длЯ каждого а Е А, (а,а) Е Вг. Рассмотрев все возможные случаи и показав, что в каждом из них из (а,Ь) Е Лг следует (Ь,а) Е Вы можно показать, что отношение Вг является симметричным. Можно также показать, что Л| транзитивно, используя метод прямого перебора, как показано на примере следуюшей таблицы.
Проанализировав каждый возможный случай, когда (а, Ь) Е В, и (Ь,с) Е Вы получаем, что (а, с) Е В,. Вг не является антисимметричным, поскольку (1,2) Е Вг и (2,1) Е Вы но 1 зс 2. П ПРИМЕР 2.34. Пусть А = (П, Л,0),*1 и пусть Вз С А х А определено в виде В = (((-), П), (ьз, г-'), ((-),*), (сз, П), (*, г)), (*,*), (0,*), (0, 0)). 94 гЛА8л 2. Творил множеств Лз не является рефлексивным, т.к.
Ь Е А, но (1з,сз) ф Лз. Лз не является симметричным, поскольку ((),*) Е Лз, но (*,( )) ф Лз. Лз не является анти- симметричным, поскольку (1з, П) Е Лз и (П, Ь) Е Лз, но сз ф П. Лз не является транзитивным, т.к. (Ь, П) Е Лз и (П,*) Е Лз, но (11,*) ф Лг. П ПРИМЕР 2.35. Пусть А — множество положительных целых чисел. Определим отношение Л, задавая (х, у) Е Л условием: у кратно х. Л рефлексивно, поскольку для каждого положительного целого числа и, и = 1 и и (и, и) е Л. Л не является симметричным, т.к (2,4) Е Л, но (4,2) ф Л; однако, Л антисимметрично, т.к., если (гп, и) Е Л и (и,гп) Е Л, тогда и кратно т и т кратно и, так что гп = и.
Л транзитивно, потому что если (т, и) Е Л и (п,р) Е Л, тогда и кратно гп и р кратно п, так что р кратно гп и (тп,р) Е В. П ОПРЕДЕЛЕНИЕ 2.36. Пусть Л вЂ” бинарное отношение на множестве А. Рефлексивное замыкание В есть наименьшее рефлексивное отношение на А, содержащее Л как подмножество.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
