Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 165
Текст из файла (страница 165)
0110 О( 7 а)С~= 0 1 1 0 1 0 о о б) 0 000000 0 0 100101 010011 001111 110110 011100 101010 111001 1 100000 0 1 000101 110011 101111 010110 111100 001010 011001 0 010000 1 1 110101 000011 001111 100110 001100 111010 101001 001000 101101 011011 000111 111110 010100 100010 110001 100001 010111 001011 110010 011000 101110 111101 000100 0 0 0 000010 1 0 100111 010001 001101 110100 011110 101010 111001 О 000001 0 1 100100 010010 001110 110111 011101 101011 1110 00 1 110000 1 О 010101 100011 111111 000110 101100 011010 001001 в) вместо 111101 должно стоять 111001; 111001 — правильно; вместо 110010 должно стоять 110110; вместо 101001 должно стоять 111001. 9.
101101, 011011, 110110; ~ 1 0 1 1 0 1 1 С = 0 1 1 0 1 1 1 1 0 1 1 0 (а -ь Ь) + с = ((ад,аг,,а„) + (Ьд,Ьг,,Ь )) + (сд,сг,,с ) = = (ад + 6д,аг + Ьг, ,а„ + Ь„) + (сд,од, , с„ ) = ((ад+Ьд)+од (аг+Ьг)+сг ''' (а +Ь )+с ) = (ад + (Ьд + сд),аг + (Ьг + сг), ° °, а„(+Ь„+ с„)) = = (ад,аг, ,а ) + (Ьд + сд, Ьд + сг, , Ь„ + с„) = = (ад,аг, ,а„) + ((Ьд, Ьд, , Ь ) + (сд, сг, , с„)) = = а + (Ь + с). Единицей является элемент (0,0,,0). Каждый элемент является своим обратным элементом.
Замкнутость следует из определения сложения. Следовательно,  — группа. П. Ассоциативность. Пусть а = (ад,аг,,а„), 6 = (Ьд,Ьг,,Ь„) и с = (сд,сг,,с„)— элементы из В„ 934 Ответы к упрвжненияи 13. Поскольку С вЂ” подмножество множества В, оно ассоциативно. Каждый элемент является своим обратным элементом, Поэтому необходимо показать только замкнутость. Пусть и,и Е С .
Тогда иос = пес =0 для всех с б С. Поэтому (и+и)ос = нос+пес =0+О=О для всех с Е С н и+ и Е С~. Следовательно, С~ — группа. Раздел 78.3 1 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 1 0 1 1 0 0 0 0 1 1 0 1 3. 6(110010101,010101111) = 5. Б. 001100110, 101100111, 100000111 ~1 0 1 1 1 0 0~) 7.а)С~~=~1 1 1 0 0 1 0 1 1 0 1 0 0 1 б) вместо 1110110 должно быть 1110010, вместо 1011001 должно быть 1010001, вместо 1101100 должно быть 1100100, и вместо 1111110 должно быть 1111111. 9. Порождающая функция в упражнении 7 меняет 1001001 на 1101001. Порождающая функция в упражнении 8 меняет 1001001 на 1011001. Обе порождающие функции "исправляют" код, генерируя ошибки.
11. а) если с = с', то нет такой позиции, в которой соответствующие биты отличались бы. Следовательно, отсутствуют позиции, в которых олин бит равен 1, а другой равен О. Таким образом, 6(с, с') = О, Обратно, если 6(с, с') = О, отсутствует позиция, в которой один бит равен 1, а соответствующий бнт равен О. Вполне очевидно, что все соответствующие биты должны совпадать, н с = с'. б) пусть 6(с, с') = и. В таком случае имеется и позиций, где соответствующие биты строк с и с' отличаются. Но тогда Во1 имеется и позиций, где соответствующие биты строк с' н с отличаются, и 6(с', с)=п.
13. 1 — 1 — 1 1 Ответы к упражнениям 935 1 1 1 -1 1 -1 1 -1 -1 — 1 — 1 1 1 1 1 -1 1 -1 1 -1 -1 -1 -1 1 — 1 -1 -1 1 -1 1 -1 1 1 1 1 — 1 — 1 -1 -1 1 — 1 1 — 1 1 1 1 1 — 1 016 = Раздел 19.1. !. Пусть ( 1 2 3 )' ! ( 2 3 1 )' (! 3 2) " (3 2 !)! (3 1 2)' (2 1 3)' В таком случае имеем следующую таблицу умножения. 1 2 3 4 5 6 7 8 ~ 1 2 3 4 5 6 7 8!' 1 2 3 4 5 6 7 8 ! 1,2 3 4 5 6 7 8 1/' !' ! 2 3 4 5 6 7 8'! '! 3 4 5 6 7 8 1 21' 1 2 3 4 5 6 7 8 ! ~4 5 6 7 8 1 2 3!' ! 2 3 4 5 6 7 8 ~ ~5 6 7 8 1 2 3 5(' /! 2 3 4 5 6 7 8~ '! 6 7 8 1 2 3 4 5!' 1 1 1 1 1 -1 1 -! 1 1 -1 — 1 1 -1 — 1 1 1 1 1 1 1 — 1 1 -1 1 1 -1 -1 1 — 1 -1 1 1 1 1 1 1 -1 1 -1 1 1 -1 — 1 1 — 1 — 1 1 1 1 1 1 1 -1 1 -1 1 1 -1 — 1 1 -1 — 1 1 1 1 1 -1 1 1 1 -1 -1 -1 -1 1 -1 -1 -1 1 1 1 1 -1 1 1 1 -1 -1 -1 -1 1 -1 -1 -1 1 1 1 1 1 — 1 1 -1 -1 1 -1 1 1 -1 -1 1 — 1 1 1 1 1 1 1 — 1 1 1 1 -1 1 -1 -1 -1 -1 — 1 -1 1 -1 — 1 -1 -1 -1 1 -1 1 1 -1 1 -1 -1 1 1 1 -1 1 1 1 -1 -1 — 1 -1 1 — 1 -1 -1 1 -1 -1 -1 1 -1 -1 — 1 1 1 1 1 -1 1 1 1 -1 1 1 1 -1 -1 -1 -1 1 -1 -1 -1 1 1 1 1 -1 -1 — 1 -1 1 1 1 1 -1 1 1 1 -1 -1 -1 -1 1 936 Ответы к упражнениям 7.
7. Раздел 19.2. 1. 8. 3. 4. 5. 18. 7. 39. 9. т4 Ч- т'Ь + 3тгьг + тЬз + Ь4. и. з + т4Ь + гтзбг + гтгбз + тЬ4 + Ь'. 13. та + ттЬ + 4теЬг + 5тзЬз + 8т4Ь4 + 5тзЬ + 4тгЬе + тьг + Ьз 15. тго+ 4тэЬ+15т Ь +42тгЬ + 72т Ь + 84тзЬз + 72т4Ь -~-42тзЬ + 154 гЬ + 4тЬ + Ьго Раздел х0.1. 1. Еслиах=Ь,тоа ах=а Ьих=а ~Ь.Еслиатп=ьиап=ь,тоат=ап,поэтому а ага=а оп итп=п. 3. Предположим, что аЬ вЂ” делитель нуля. Тогда гаь)с = О для некоторого с, Следовательно, а1ьс) = О. Если Ьс = О, то Ь вЂ” делитель нуля. Если Ьс ~ О, то а — делитель нуля. 5. О. 7. Предположим, что из аЬ = ас следует, что Ь = с для всех ненулевых а из В.
Если аН = О = аО и а ф О, то Н = О, и Н вЂ” область целостности. Обратно, если  — область целостности и аЬ = ас для а ~ О, то аГЬ вЂ” с) = О. Следовательно, Ь вЂ” с = О и Ь = с. 9. Пусть 4+1 и г'+ г' принадлежат 1+ 1. Тогда 4+1+ 4'+ г' = 4+ 4'+1+ г'. Поскольку 4+4' б 1 и 1+ г' 6 1, то 4+1+4'+1' 6 1+ 1. Также агг+1) = аз+агь Поскольку аз 6 1 и ау 6 .У, то аГ44 и 1) 6 1+ 1. 2 3 4 5 8 1 2 3 2 3 4 5 1 2 3 4 2 3 4 5 1 8 7 6 2 3 4 5 3 2 1 8 2 3 4 5 5 4 3 2 2 3 4 5 7 6 5 4 2 3 4 5 8 7 6 5 2 3 4 5 2 1 8 7 2 3 4 5 4 3 2 1 2 3 4 5 6 5 4 3 4 5 6)' 6 7 8 ) 6 7 8 ) Ответы к упражнениям 937 11.
(3). 13. ДО) = О. Поэтому О б Дй). Пусть а, Ь е Дй). Тогда а = Дс) и 6 = Дд) для некоторых с,д б В. Поэтому с — д О В и Дс — д) = 1(с) — Дд). Следовательно, Дс) — Дд) б Дй). Аналогично, если а, Ь Е Дй), а = 1(с) и Ь = Дд) для некоторых с, д б й, то сд б В и У(сд) = з'(сЩд), Таким образом, аЬ б 1(й). Следовательно, !(В) — кольцо.
15. Нет. 17. Неверное утверждение. Элементы ]2] и ]3] — нулевые делители кольца 21з. Однако, ]2] Ч]3] = ]5] не является нулевым делителем кольца Ягз. 19. Пусть  — область целостности. Если аз = а, то а а = а 1 и, согласно результату предыдушей задачи, а = 1. 21. Для всех а, Ь б й имеем ( — а)(6) + аЬ = (-а + а)Ь = О Ь = О. Поэтому ( — а)(6) = — аЬ.
Аналогично, а( — Ь) = — аЬ. Лля всех а, Ь б В ( — а)(-6) + ( — а)(6) = ( — а)( — Ь+ Ь) = ( — а) О = О. Поэтому (-а)( — Ь) + ( — а)(Ь) = аЬ+ (-а)(Ь) и ( — а)( — Ь) = аЬ. Раздел 20.2. 1. Покажем сначала, что пересечение подколец с единицей является кольцом с единицей. Поскольку мультипликативная единица принадлежит всем подкольцам, то она принадлежит их пересечению.
Пусть а,Ь принадлежит пересечению подколец, тогда а,Ь принадлежит каждому из подколец. Поэтому а — Ь принадлежит всем подкольцам и, следовательно, пересечению подколец. Аналогично, аЬ принадлежит пересечению всех подколец. Следовательно, пересечение подколец с единицей есть кольцо с единицей. Далее покажем, что пересечение областей целостности есть область целостности. Предположим, что а и 6 принадлежат пересечению всех подколец,аЬ = О и а ~ О, Но а и Ь принадлежат каждой из областей целостности.
Поэтому Ь = О. 3. Или а > О, или — а > О. Если а > О, то, согласно определению упорядочения,аз > О. Если -а > О, то (-а) > О. Но ( — а) = аз, поэтому а > О. Поскольку 1 = 1, то 1 > О. Раздел ЯО.З. 1. Пустьз'=(а),д=(Ь) ид=(с)". У+(д+6) = (о,)'+ (Ь, + с,)' = =(а,+(Ь,+с,))' = = ((а, + Ь,) ч- с,)* = = (а, + 6.)' + (с,)' = = У+д)+А, поэтому сложение ассоциативно. Аддитивной единицей является (д,), где д, = О для всех й Обратным элементом относительно сложения для (а,)' будет (-а;)'. У+ д = (а,) + (Ь;) = (а~ + Ьг)* = = (Ь, + а,) = (Ь.)*+ (а,) =д+У, 938 Ответы и упражнениям и сложение коммутативно.
Следовательно, множество многочленов — коммутативная группа относительно сложения. У(дй) = (а;) ((Ь;) (с,) ) = (а,) ( ~ Ь,сз)* = . ь|=ь ( ~ а 2 6,сз)'= т-ьь= .е,=ь ( ~" Ь,с,) = те ° ез= (~ (~ а Ь,)с,)*= .~.р=«те =в ( ~ а Ь,) (с,) ((а,)'(Ь,)')(с,)* = (Уд)6, и умножение ассоциативно. Окончательно, г'.(д+ Ь) = (а,)'(6;+ с.)* = =( ~ а,(Ь, +с,))' = *еу=ь = ( ~ (а,Ьз+а;с;))* = *ч а=а = ( ~ ~а,Ь~)'+ ( ~ ~а,су ез=ь *.~.у=ь = Хд+16 3.
Неверное утверждение. Пусть у = (1,1,1,1,0,0,".) и д = (1,1, — 1,-1,0,0, .). Тогда у + д = (1, 1, О, О, О, О, . ). дея(У) = с1ед(д) = 3, тогда как с1ея(У ч- д) = 1. 5. В Уа, 1(х) = х~ — 1 — нулевая функция, тогда как у имеет степень 4. Раздел 20.4. 1. Пусть г = а+ 61 и з = с+де — целые комплексные числа. Тогда г — з = (а — с) + (Ь-д)1 и гз = (а + Ье)(с+ де) = (ас — Ьд) + (од + Ьс)1 — также целые комплексные числа. Поэтому множество целых комплексных чисел является подкольцом. 3. з1п(пя) = 0 для любого целого числа и. Следовательно, уравнение имеет бесконеное количество нулей, и юп(х) нельзя представить в виде многочлена. Б.
Пусть А = Я и У,д Е А(х] определены соотношениями У(х) = х' + 1 и д(х) = ха — 3 соответственно, тогда / и д — простые многочлены, но ( + д простым многочленом не является, поскольку 1 + д(х) = 2ха — 2. 7. Пусть с = а + 61 — комплексное целое число. Тогда У(х) = (х — (а+ Ьг))(х — (а — 61)) = = (х — а) + 61)(х — а) — Ь1) = = (х — а) Ч- Ьа, поэтому / Е фх) и У(с) = О. Ответы к улражненоям 939 9. Подкольцо, состоящее из всех чисел вида а+ ЬЛ, где а и 6 — рациональные числа. 11. Подкольцо, состоящее из всех чисел вида а+ ЬзГ5г, где а и 6 — рациональные числа. !3.
Подкольцо, состоящее из всех чисел вида а+ ЬчГЗг, где а и Ь вЂ” рациональные числа. Раздел 21.2. 1. 1 = Х(дд ') = Х(д)Х(д ') = (а+ 6!)Х(д '). СлеДовательно, Х(д ') = —,', = эг+ьт Но поскольку а+ 6! лежит на единичной окружности, то а + Ь = 1, поэтому х(д ') = а — Ь!. 3. Если д ~ д', то дг!Од'! !дгз~ ! д'! и д' = д! !Од' ! !д' ~ ! ..д' ! 1, где для некоторого ! имеем дг! ! зе д! !*!. Тогда хе(д!) = аг!*! и хе (д!) = а', ! !. Поскольку а',!'! ~ а! О1, то х.Ь!) Ф х, Ь.) и х, Ф хеп 1, если з б Я вЂ” 1; Х(з) = О, если з Е 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
