XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 17
Текст из файла (страница 17)
Используя ранее доказанные тождества, показать сира ведливость тождества (А ~ В) х С = (А х С) ~ (В х С). 1.7. Доказать, что для любой функции у и любых множеств А и В имеют место соотношения: а) у(А1.1В) = У(А) 0,1(В); б) у(А 11 В) С у(А) Пу(В); в) ~(А) ~ДВ) С ~(А~В). При каких условиях включения б) и в) превращаются в равен- ство? 107 Волросы и ээдачя 1.8. Доказать, что для любой функции ~ и любых множеств А и В имеет место равенство: а) у' ~(АПВ) = ~ ~(А)й~ ~(В); б) ~ ~(АОВ) =~ ~(А)ОУ '(В); в) у ~(А) = у ~(А); г) ~ ~(А~В) =У ~(А) ~У ~(В).
1.9. Построить графики и графы следующих бинарных отношений, заданных на множестве Х = 11, 2, 3, 4, 5, 61: а) х~ ухе, если х~ < хз+1; в) х~ рхз, если ]х~ — хз] > 3; б) х~ тхз, если х~ <хз, г) ((а, Ь): а+Ь вЂ” четное). 1.10. Определить, какими свойствами (рефлексивность, иррефлексивность, симметричность, антисимметричность, транзитивность) обладают следующие бинарные отношения: а) у = 1(а, а), (а, 6), (с, а), (6, И), (а, Ы), (Ь, с)) на множестве М=(а,Ь,с,Ф б) р„, такое, что тп р„й, если т — Й делится на н, где га, Й ЕЕ, а не Еи фиксировано; в) <р, такое, что хну, если х — у < 2, хай, у ЕК.
1.11. Пусть р = ((х, у): х < у и у+ х < 1,5) — бинарное отношение на множестве Х = (О, 1]. Построить графики отношений р и р~. Исследовать свойства отношений р и р~. 1.12. Найти Р(р), В(р)) р ~, рэр, р ~ ор, рор ~ для бинарных отношений: а) р=((х, у): х,уе]0,1], х+у< Ц; б) р = 1(х, у): х, у Е [О, 1], 2х > Зу1. 1.13. Доказать, что для любого бинарного отношения р С С А х А имеют место равенства: а) Р(р ~) = В(р); в) Р(р~ орз) = р~ ~(В(р~) ПР(рз)); б) В(р ~) =Р(р); г) В(разоря) =рз(В(р~)ПР(рз)).
108 1. МНОЖЕСТВА И ОТНОШЕНИЯ 1.14. Доказать, что для любых бинарных отношений р1, р2, рз Е А х А имеют место равенства: а) р1пр1=р1ор1=р,; д) (р1ирз)-'=р,'ир,-', б) р1 о(ряорэ) =(р1оря)орэ~ Е) (р) 1 =(р 1)~ В) р1 оЫА =1олор1 =р1. Ж) (р1оря) = ро ор1 -1 -1 г) (р1йрг) '=р1'Прз', 1.15. Доказать, что для бинарных отношений т и р;, 1 Е 1, справедливы равенства: а) то фр) =Ц(тор1). б) то (Пр;) Сп(тор;).
1Е1 1Е1 1Е1 1Е1 1.16. Доказать, что для бинарного отношения р на А имеет место равенство ро р 1 = р 1 о р = ЫА, если и только если р— биекция А на А. 1.1?. Найти необходимые и достаточные условия односторонней обратимости бинарного отношения р на множестве А, т.е. условия того, что ро р 1 = ЫА (или р 1 о р = ЫА). 1.18. Построить бинарное отношение, которое является: а) рефлексивным, симметричным, но нетранзитивным; б) рефлексивным, антисимметричным, но нетранзитивным; в) рефлексивным, транзитивным, но несимметричным; г) антисимметричным, транзитивным, но нерефлексивным.
1.19. Доказать, что для любых рефлексивных отношений р и <т на произвольном множестве А р1.1 сг С рост. 1.20. Пусть А и  — конечные множества, содержащие ги и и элементов. Сколько существует различных соответствий из А в В? Сколько можно задать функций из А в В, а среди последних — инъекций? При каких гп и п существуют биекции и сколько их? 1.21. Пусть в 1яз задана плоскость ах+ Ьу+ с» = О. Точки с радиус-векторами т1 и тз связаны отношением т, если 109 Вопросы и задачи ((г~ — гэ),в) = О, где ть — нормаль к плоскости, а (, ) — скалярное произведение векторов.
Показать, что г — отношение эквивалентности. На какие классы эквивалентности разбивается Жз? Указать фактор-множество множества 11з по данному отношению эквивалентности. 1.22. Пусть А — конечное множество. Какое отношение эквивалентности на нем дает наибольшее число классов эквивалентности? Сколько классов эквивалентности при этом будет? Сколькими способами можно задать отношение эквивалентности, разбивающее А на два класса? 1.23.
Доказать, что число различных отношений эквивалентности на и-элементном множестве удовлетворяет формуле р.+~ =",«,С„'р;, ре =1, где р; — число различных отношений эквивалентности на 1-эле ментном множестве. 1.24. Доказать, что композиция р~ марэ двух эквивалентностей р~ и рз является эквивалентностью тогда и только тогда, когда р~орэ =ргор~. 1.25. Описать наименьшее по включению отношение эквивалентности, содержащее данные эквивалентности р и и на А.
Каким будет это отношение, если рож = и о р? 1.20. Пусть бинарное отношение и определено на множестве положительных рациональных чисел следующим образом: (а/Ь) и (с/о), если ад ( (бс. Показать, что и является отношением линейного порядка. 1.27. Пусть А — произвольное множество и р, а — бинарные отношения на множестве 2я х 2л: (Р, Я) и (Х, У), если Р С Х и Ч С У, а (Р, (~) р (Х, У), если (РЬц) С (ХЬУ).
Являются ли р и и отношениями порядка? 110 1. МНОЖЕСТВА И ОТНОШЕНИЯ 1.28. Пусть М вЂ” множество квадратных матриц типа 2 х 2, элементами которых являются целые числа. Выяснить, является ли бинарное отношение т, заданное на множестве М, отношением порядка или отношением линейного порядка: а) А т В, если аН ( Ь,", ь', 1 = 1, 2, А, В Е М; б) А т В, если аН < Ь,", ь', 1 = 1, 2 и хотя бы для одной пары элементов неравенство строгое, АВ Е М. 1.29.
Пусть Р— множество функций, непрерывных на отрезке (а,6]. Проверить, является ли заданное отношение отношением указанного вида: Ь Ь а) ~(х) т д(х), если у(х) <Ь = д(х) сЬ; отношение эквива- лентности; б) 1(х) т д(х), если 1(х) Нх ( (д(х) Их; отношение поряд- О я ка и отношение предпорлдка. 1.30. Пусть р1 и рз — линейные порядки на множестве А. Когда р1 о рз — линейный порядок? Указание: докажите, что если р1 ф рз, то р1 о рз не является линейным порядком. 1.31.
Всегда ли транзитивна композиция транзитивных бинарных отношений? У к а з а н и е: постройте пример конечного упорядоченного множества, в котором композиция исходного и двоиственного порядка не является транзитивным отношением. 1.32. Пусть А и  — конечные множества. Используя метод математической индукции, доказать, что ~А х В~ = ~АВВ~. Пусть А1, ..., А„— конечные множества. Доказать, что ~А1 х ... х А„~ = ~АЬ~... Щ. 1.33.
Какую мощность имеет множество простых чисел? Вопросы и задачи 1.34, Пусть А — множество всех многочленов степени не выше и, имеющих коэффициенты заданного вида. Определить мощность этого множества„если: а) все коэффициенты много- членов рациональные; б) свободный член действительный, а все остальные коэффициенты рациональные. 1.35. Доказать счетность следующих множеств: а) множества всех многочленов с рациональными коэффициентами; б) множества всех попарно непересекающихся открытых шаров в 1ай; в) множество всех цифр 8, расположенных на плоскости так, что ни одна пара цифр не имеет общих точек, кроме, может быть, точек касания. 1,36.
Определить мощность множество всех точек плоскости, у которых: а) обе координаты рациональные; б) первая координата рациональная, а вторая — иррациональная. 1,3'Т, Доказать, тго следующие множества имеют мощность континуума: а) множество М" всех бесконечных последовательностей натуральных чисел; б) множество 1Чоо всех последовательностей натуральных чисел; в) множество Аоо всех (конечных или бесконечных) последовательностей элементов вэ конечного множества А. 1.38. Доказать, не используя теорему 1.20, что множество 2(е 1) имеет мощность ббльшую, чем мощность континуума. Указание: установите биекцию множества 2(с'1) на множество всех функций из [О, 1] в (О, 1) (характеристических функций подмножеств отрезка (О, 1]), а затем обобщите „диа. гонаяьную" конструкцию из доказательства теоремы 1.15. 2.
АЛГЕБРЫ: ГРУППЫ И КОЛЬЦА Предметом рассмотрения в абстрактной алгебре являются произвольные множества с заданными на них операциями. При этом природа множеств и операций может существенно отличаться от привычных числовых множеств и известных операций над числами. Мы уже сталкивались с операциями над множествами и бинаркыии ошношекилмп (см. 1), которые оказались в чем-то похожими на операции над числами, но в то же время проявились и их существенные отличия. В дискретной математике разрабатываются алгоритмы и вычислительные методы, позволяющие манипулировать сложно организованными нечисловыми структурами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
