341_1- Сборник задач по математике для втузов. В 4-х ч. Ч.1_ (ред) Ефимов А.В, Поспелов А.С_2001 -288с (987777), страница 30
Текст из файла (страница 30)
На рис. 37 изображен граф отношения о. Построить графы отношений сг ', о~, оо ~, ст ~п, о'. 4.43. Какие линии нужно добавить к графу отношения о, изображенному на рис. 37, чтобы получился: а) граф рефлексивного отношения; б) граф симметричного отношения; в) граф транзитивного отношения? а 4.44. Доказать, что для любого отношения и от- е ношения и ~о и оо ~ — симметричные.
с я' В задачах 4.45-4.47 о, т, р — отношения эквивалентности на одном и том же множестве, о 'ч' т Рнс З7 обозначает наименьшее отношение эквивалентности, содержащее о и т. Доказать приведенные равенства. 4.45. и 'ч' т = (о У т)'. 4.48. р П (о Ч т) = (р П т) Ч (р П т).
4.47. р 1l (и й т) = (р Ч т) П (р Ч т). 4.48. Для двух данных отношений эквивалентности о и т определить, что собой представляют классы отношений эквивалентности о П т, о 'ч' т из задачи 4.45. Два частично упорядоченных множества иноморфны, если между ними существует взаимно однозначное соответствие, сохраняющее отношения порядка. 4.49. Перечислить все неизоморфные частично упорядоченные множества, состоящие из 2 нли 3 элементов.
4.50. Рассмотрим конечное множество из я элементов. Сколько на этом множестве можно ввести: а) различных бинарных отношений; б) рефлексивных бинарных отношений; Гл. 4. Элементы общей алгебры 172 в) симметричных бинарных опюшений; г) антисимметричных бинарных отношений; д) отношений линейного порядка; е) отношений частичного порядка (и = 3); ж) отношений эквивалентности (и = 3)? 4.
Алгебраические операции и их свойства. Алгебраической операцией на множестве А называется отображение А х А -+ А. Если при отображении элементам а, Ь Е А ставится в соответствие элемент с й А, то с называется произведением элементов а и Ь. Используется запись с = аЬ. Термин «произведение» носит условный характер: он может означать «сумму», «разность», «реаультат последовательного выполнения» (преобразований) и т.д.
Произведение элементов а и Ь обозначают также а Ь, а*Ь, а+Ь, а оЬ, аПЬ и т.д. Множество А, на котором задана операция *, принято обозначать (А, *). Операцию на конечном множестве А = (ат, аэ, ..., а„) можно задать таблицей Кали, в которой на пересечении строки элемента а; и столбца элемента а, стоит элемент а« = а««ат: Операция коммутпатпивна, если а «Ь = Ь «а для всех а, Ь.
Операция ассоциативна, если (а*Ь) *с= а «(Ь*с) для всех а, Ь, с. Элемент и называется левой единицей если и «а = а для всех а; правой единицей, если а * и = а для всех а; левым нулем, если и * а = и для всех а; правым нулем, если а «и = и для всех а. Единица (или двуспюроннлл единица) — элемент, являющийся одновременно правой и левой единицей. Нуль (или двустпоронниб нуль) — элемент, являющийся одновременно правым и левым нулем. П риме р 10. На множестве А = (1, 3, 5, 15) задана операция а«Ь = = НОЯ(а, Ь) (наибольший общий делитель чисел а и Ь). Проверить коммутативность и ассоциативность этой операции. Составить таблицу Кали этой операции. Найти единицы и нули. о Таблица Кали имеет вид: 1.
Била лые отношения и алгеб акческие опе ации 173 Так как НОД(а, 6) = НОД(6, а), то операция * коммутатнвна. Операция * ассоциативна, поскольку НОД(НОД(а, Ь), с) =НОД(а, НОД(Ь, с)) = = НОД(а, Ь, с). Так как НОД(15, а) = а и НОД(1, а) = 1 для всех а Е А, то 15 — единица в А, а 1 — нуль в А. Других единиц и нулей нет. > 4.51. а) Сколько различных алгебраических операций можно ввести на множестве из и элементов? 5) Сколько из них будут коммутативны? 4.52. а) Доказать, что если в множестве есть правая и левая единицы, то они совпадают, и этот элемент является двусторонней единицей. б) Доказать аналогичное утверждение для нулей. В задачах 4.53 и 4.54 построить таблицы Кэли указанных множеств с заданными операциями.
Найти все левые (правые) единицы, левые (правые) нули. 453. М = (а, 6, с, а), х * у = х для всех х, у Е М. 454.М=(1,2,3,4), хяу= ' 4' 4.55. Как по таблице Кали конечного множества определить, является ли операция на атом множестве коммутативной? 4.58. Проверить ассоциативность операции, заданной следующей таблицей Кали: Операция на множестве А обратима слева, если уравнение ха = 6 разрешимо для всех а, 6 Е А; обратима справа, если уравнение ау = 6 разрешимо для всех а, 6 Е А.
Операция сократ .иа слева, если ах = ау =~ х = у для всех а, х, у е А; сократима справа, если ха = уа =~ х = у для всех а, х, у Е А. 4.57. Как по таблице Кали конечного множества определить, является ли операпия на этом множестве: а) обратимой (слева или справа); б) сократимой (слева или справа)? 4.58. Привести пример алгебраической операции: а) коммутативной,но неассоциативной; б) ассоциативной,но некоммутативной; в) ассоциативной, обратимой слева,но необратимой справа; г) ассоциативной, сократимой слева,но несократимой справа.
174 Гл. 4. Элементы общей алгебры В задачах 4.59-4.66 для заданных операций выяснить, будут ли они ассоциативны, коммутативны; найти все левые (правые) единицы, нули. 4 59. а я 6 = а — Ь (а, Ь Е К). 460.а*Ь=а (а,6ЕК; а,Ь)0). 4.61. а * 6 = НОД(а, Ь) (а, Ь Е Я). 4.62. а я 6 = НОК(а, 6) (НОК вЂ” наименьшее общее кратное чисел а и Ь (а, 6 Е 1"'))).
4.63. а я Ь = ~(а~ + 6~ (а, 6 Е К; а, Ь ) О). 4.64. (а, Ь) х (ам Ь1) = (аам аЬ1 + Ь) (на множестве К х К). 4.65. (у яд)(х) = ~(д(х)) (на множестве отображений Х -~ Х). 4.66. а я 6 = а + Ь вЂ” аЬ (а, Ь Е К). Введем на множестве Е„= (О, 1,..., и — Ц остатков от деления целых чисел на и е М операции сложения и умнолсенил ио модулю и. Для а, 6 с Е„выражения а+6 (пюд и) и а 6 (мод и) обозначают остатки от деления на и чисел а+ Ь и а Ь соответственно. Пример 11. Доказать коммутативность и ассоциативность операции а+ Ь (люди) на множестве Е„. < Чтобы различить операции обычного сложения и сложения по модулю и, будем их в этом примере обозначать + и Ю.
Очевидно, а 9 6 = а + + Ь (щод и) для всех а, Ь Е Е„. Коммутативность операции очевидна. Проверим ее ассоциативность. Пусть а, Ь, с б Е„. Тогда (а б 6) ® с ьз ж (а + 6) 9 с = (а + 6) + с = а+ (Ь+ с) = а + (Ь 9 с) = а Ю (Ь 9 с) (мод и). Так как (ае)Ь) ®с = а9(ЬЮс) (люди) н оба числа (аЮЬ) Юс, ай(ЬЮс) принадлежат Е„, то (а®6) Юс = ай(6®с). ~> В задачах 4.67 и 4.68 построить таблипы Кэли множества Ея с указанными операпиями. Найти все левые (правые) единицы, левые (правые) нули. 4.67. Операция сложения по модулю 4. 4.68.
Операция умножения по модулю 4. 4.69. Доказать коммутативность и ассоциативность операции а Ь (пюди) на множестве Е„. Пусть а — элемент множества А с операцией я. Тогда по определению а" = а" ' *а, где и б М. Элемент а — идениогиенга, если аэ = а. Пусть множество (А, *) имеет нуль д. Тогда а — нияьиогленглныб элемент, если а" = д прн некотором и б И. 4.70. Найти все идемпотенты и нильпотентные элементы множества: а) (Ез, +)' б) (Еа ). Гомоморфиомом множества (А, я) на множество (В, о) называется отображение у: А -+ В, удовлетворяющее условию <р(х* у) = ~р(х) о~р(у) 'т'х, у б А. 1.
Бинарные отношения и алгебраические операции 175 Взаимно однозначное отображение у, являющееся гомоморфизмом, называется изоморфизмом. Множества (А, *) и (В, о) изоморфны, если существует изоморфнзм между ними. В этом случае пишут (А, «) ы ж (В, о) или А = В. Пример 12. Пусть Р(Х) — множество всех подмножеств множества Х. Доказать, что множества с операциями (Р(Х), 0) и (Р(Х), й) изоморфны.
з Проверим, что отображением, осуществляющим нзоморфизм, является взятие дополнения. А именно, пусть у(А) = А для А 6 Р(Х). Ясно, что отображение р: Р(Х) -«Р(Х) взаимно однозначно. Наконец, х(АОВ) = А и В = АиВ = р(А) и р(В), поэтому р — нзоморфизм. с. Пример 13. Изоморфны ли множества (Е, +) и (Е, *), если операция «определяется формулой а * Ь = а + Ь вЂ” 2? а Пусть е — единица в (Е, *). Тогда для всех элементов х этого множества выполняется равенство е*х = х, или е+ х — 2 = х. Таким образом, е = 2.
Это обстоятельство наводит на мысль, что изоморфнзм множеств (Е, +) и (Е, *) получится, если и каждому элементу прибавлять 2. Проверим это. Пусть ~р: (Е, +) -» (Е, *) таково, что у(х) = х + 2 для всех х. Ясно, что у взаимно однозначно. Кроме того, х(х+ у) = х + у + 2 = (х+ 2) + (у + 2) — 2 = (х+ 2) * (у + 2) = у(х)» ~р(у) . Следовательно, «з — изоморфизм. ~> 4.71. Какие множества с заданными операциями из задач 4.53, 4.54, 4.67, 4.68 изоморфны? 4.72. Пусть М = [а, Ь]. Положим х Л у = ппп(х, у), х У у = = гпах (х, у).
Изоморфны ли (М, Л) н (М, У)? 4.73. На множестве Е целых чисел введена операция а» Ь = = а + Ь+ 3. Доказать, что (Е, ») ол (Е, +). 4.74. На множестве К введем операцию х» у = ~багха + уз. Проверить, что (К, ») = (К, +). 4.75. Изоморфны ли множества (Е, +) и (Е, )? Прямым произведением множеств Ам Аз, ..., А„с операциями называется множества А1 х Аз х... х А„, в котором операция определяется пономпонентно: (аы аэ, , а„) (а~, ан ..., а'„) = (а1 а1, аг аз, ..., а„ . а'„). 4.76, Выяснить, при каких условиях на множества (А;, ) толь- но что введенная операция в А1 х Аэ х... х А„будет: а) номмутативной; б) ассоциативной. 4.77.
Какие элементы множества А1 х ... х А„ относительно введенной выше операции являются: а) (левыми, правыми) единицами; б) (левыми, правыми) нулями? Гл.4. Элементы обшей алгеб ы 176 В задачах 4.78 и 4.79 выяснить, изоморфны ли указанные множества. 4.78. (Жз х Жз, +) и (Е4, +). 4.79. (бт х Жэ, ) и Щ4, ). 4.80.
Пусть А = (2, 3, 4, 5), В = (2, 4, 5, 101. На множествах А, В операции обычного сложения и умножения являются часптичныни операциями (т. е. определенными не для любых пар элементов). Построить таблицы Кэпи сложения и умножения на множествах А и В. Показать, что (А, +) 94 (В, ). ~ 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
