Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 160
Текст из файла (страница 160)
Имеется только и — 1 различных целых чисел и и ящиков, поэтому два ящика должны содержать целые числа, которые не будут различными. Эти ящики содержат одинаковое количество шаров. Раздел 8.9. 1 1. —. 4 6 3. —. 18 1 1 5.— 2' 2' 1 7.
7 15 9. 19 19 11. 6 483 13. — . 56 252 15. — . 36 ' 17. -13 центов. 19. 3456. Ответы к упрвлгнениям 895 7 35 23. ('о) (.1)2(.9) .1937. 25 (2)(э) — 3 э2) 27. —. 36 38 36 29. 38 31. 3, 2.1. Раздел 9.10. 7. 125. Раздел В.11. 1. а) .25; 3. а) .26; 5. а) .365ь 7. а) .181632; б) .232', б) .28; 6) .6365.
б) 1000 .67032 670; в) .4989. в) .585. в) 1000 .797704 798. Раздел 9.1. 1. /!' (1,2) (1,3) (2,3) Ь~ ~~ (1) (г) Щ ~1г (1) (2) (3) 5. а) наибольший элемент 1; б) наименьший элемента; в) максимальный элемент 1, минимальный элемента; г) и то, и другое. 7. а) наибольший элемент д; 6) наименьший элемент не существует; в) максимальный элемент д, минимальные элементы а, 5, с, д; 896 Ответы к упражнениям г) верхней. 9. а) наибольший элемент г; 6) наименьший элемента; в) максимальный элемент й минимальный элемента; г) и то, и другое. 11. а) докажем а ч (6чс) = (а ч 6) чс Ь < (ач6) < (ачЬ) чс с<(ач6)чс (Ьчс) < (аж 6) чс а<(ачЬ) <(ачЬ)чс ач (Ьч с) < (а чЬ)ч с определение нвг определение нвг определение нвг определение нвг определение нвг Точно так же, (а ч 6) ч с < а ч (6 ч с) и (а ч 6)ч с = а ч (Ьч с).
Докажем а = а ч а. а < а ч а по определению верхней грани. Поскольку а < а по определению наименьшей верхней грани, то а ч а < а. Таким образом, а = а ч а. Докажем а ч Ь = Ь ч а. а < а ч Ь по определению наименьшей верхней грани. Точно так же, Ь < Ьч а. Следовательно, по определению наименьшей верхней грани, ач Ь < Ьча. Точно так же, 6 ч а < а ч Ь, и а ч Ь = Ь ч а; 6) докажем а л (Ь л с) = (а л Ь) л с. Ь > (алЬ) > (алЬ) лс с > (а Л Ь) Л с ,,(Ь л с) > (а л Ь) л с а > (аЛЬ) > (аЛЬ) Лс аЛ(ЬЛс) > (аЛЬ) Лс определение ннг определение ннг определение ннг определение ннг определение ннг Точно так же, (а л 6) л с > а л (6 л с) и (а л 6) л с = а л (ь л с).
Докажем а = а л а. а > а л а по определению наибольшей нижней грани. Поскольку а > а по определению наибольшей нижней грани, то ала > а. Таким образом, а = ала. Докажем алЬ = Ьла. а > а лЬ по определению наибольшей нижней грани. Точно так же, Ь > Ь л а. Таким образом, по определению наибольшей нижней грани, а л Ь > Ь л а. Точно так же, Ь л а > а л Ь, и а л Ь = Ь л а. 13. Доказательство проведем индукцией по числу элементов в полурешетке, имеюшей наименьшую верхнюю грань. Вполне очевидно, что единственный элемент имеет наименьшую верхнюю грань. По определению полурешетки, зто утверждение истинно для любых двух элементов. Предположим, что любые )с элементов имеют наименьшую верхнюю грань.
Если полурешетка содержит только )с элементов, доказательство завершено. В противном случае, пусть ам аз, аз,... аь, аь„1 и вь — наименьшая верхняя грань для а„аз, аз,... аь. Тогда вь ч аьзз — наименьшая верхняя грань для ам аз,аз,...аь,аьэи Вполне очевидно, а; < аь ч аз+1 для 1 < з < lс Ч- 1, Предположим, что а; < Ь для 1 < 1 < Ь+ 1. Поскольку а, < Ь для 1 < з < Ь, то вь < Ь. Поэтому, учитывая, что аь+, < Ь и аь < Ь, имеем вь ч аь+, < Ь. Следовательно, аь ч аьз, — наименьшая верхняя грань для аыаз,аз,...аь,аьзз. 15. а) если А < В и В < С, то А„ < В„ для всех 1 < 1,У < и и В;, < С„ для всех 1 < г,у < и.
Следовательно, А„ < С„ для всех 1 < 1,у < и и А < С; 6) посколькУ А„, В,з < А„ч Вч дла всех 1 < й У < и, то А < А Ч В и В < А ч В. Следовательно, А ч  — верхняя грань для А и В. Предположим, что Р— верхняя Ответы к упражнениям 897 грань для А и В. Тогда Ао, ВО < РО для всех 1 < Су < п. Если Аыч В„= 1, то АО = 1 или В„= 1, и Р„= 1.
Следовательно, Ач'Ч В„< Р„для всех 1 < ОУ < и, иАтгВ<Р; в) поскольку АО л ВО < АО, В„для всех 1 < з, у < п, то Ад  — нижняя грань для А и В. ПРедположим, что Р— нижнЯЯ гРань длЯ А и В, Если Ан д ВО = 1, то А„= О или ВО = О, и РО = О. Следовательно, Р„< А.,л В„для всех 1 < 1,1 < п, и Р < А д В; г) поскольку любые два элемента имеют как наименьшую верхнюю границу, так и наибольшую нижнюю границу, то Я является как верхней, так и нижней полурешеткой; д) наибольший элемент — матрица У, где ЬО = 1 для всех 1 < т,у < и.
наименьший элемент — матрица Т., где В„= О для всех 1 < г,у < и. Раздел У.З. 1. ((а), (а,Ь,с)), (9,(а),(а,Ь),(а,Ь,с)); ((а),(Ь),(а,Ь),(а,Ь,с)). 3. Требуется только показать, что произведение двух целых чисел вида 46 + 1 имеет такую же форму. Пусть а = 4т + 1 и Ь = 4и + 1 — целые числа такого вида. Произведение аЬ = (4п1+ 1)(4и+ 1) = = 16тп+ 4т + 4+ 1 = = 4(4тп + т + п) + 1 также имеет вид 46+ 1, где /с = 4тп+ т + и. Б. Поскольку [а] В [Ь) = [а+ 6) и [а] О )Ь] = [а+ 6] для всех положительных целых чисел а и Ь, то имеет место замыкание.
Поскольку ([а) Щ (Ь)) Щ [с) = (а + Ь) Щ (с] = = )(а + Ь) + с) = )а+ (Ь+ с)) = = [а] ~ (Ь+ с) = = ()а] ье ([Ь)) В [с]), то сложение ассоциативно. Поскольку ((а) О [Ь]) О [с) = )аЬ! О )с) = = [(а6)с) = = [а(Ьс)) = = (а] О )Ьс] = = ()а! О ([Ь)) О Ю (с)), то умножение ассоциативно.
7. Пусть а и 6 — конечные произведения элементов из (а,, аз, аз,..., аь). Тогда аЬ несомненно является конечным произведением элементов из (аыаз,аз,...,аь). Поскольку А*— подмножество множества Я, то имеет место ассоциативность. Следовательно, А' — подполугруппа полугруппы 5. Любая подгруппа А, содержащая все конечные произведения элементов из А, следовательно, должна содержать А'. 9. а) в главе 2 было показано, что композиция ассоциативна, поэтому требуется только показать, что если У и д биективны, то У од также является биекцией.
Если (У од)(х) = 898 с1шеешы к упражнениям (У о д)(у), то !(д(х)) = !(д(у)) и д(х) = д(у), поскольку ! биективна. Но тогда х = у, так как д биективна. Следовательно, ! о д — инъективна. Пусть з б 5. Поскольку !в сюръекция, то сушествует у 6 Я такой, что !(у) = з. Поскольку д — сюръекция, то существует х 6 Я такой, что д(х) = у. Таким образом, (У о д)(х) = У(д(х)) = У(у) = з н 1 о д сюръективна; 6) пусть а и Ь принадлежат образу ретракционного отображения ! на эа Ь. Следовательно, а = !(с) и Ь = !(д) для с,д б А. 1(а) = У(!(с)) = !(с) = а так что 1 не только задает взаимно однозначное соответствие, но и является тождественным отображением; в) поскольку ф положительно, то его абсолютное значение опять равно ~х), и ! — ретракционное отображение.
Ретракт — множество неотрицительных действительных чисел. Поскольку (х) — целое число, то д((х() = (х), и д — ретракция. Ретракт — множество целых чисел. Поскольку (х) — целое число, то Ь(1х1) = (х(, и Ь вЂ” ретракция. Ретракт — множество целых чисел; г) нет; д) нет. !1. Пусть А и  — (и х и)-матрицы с ненулевым детерминантам. Поскольку дес(АВ) = дес(А) дет(В), то дес(АВ) не равен нулю. Множество (ахи)-матриц с ненулевым детерминантам замкнуто относительно умножения. Поэтому они образуют полугруппу на множестве (и х п)- матриц.
Поскольку дес(1) = 1, где 1 — единица относительно умножения, то множество (и х п)-матриц с ненулевым детерминантам образует моноид. Если дес(А) = О и дес(В) = О, то дес(АВ) = О. Следовательно, множество (а х а)-матриц с нулевым детерминантам замкнуто относительно умножения и также образует полугруппу. 13.
Предположим, что 1 * а = а = а *1 для всех а б Я и е е а = а = а * е для всех а 6 Я. Следовательно, е = 1 е е = поскольку 1 — единица =1 поскольку е — единица. Раздел У.З. 1. (6); (г). 3. Подрешетка, полученная удалением е, изоморфна первой решетке в упражнении 2. Б. (а); (б); (г); (д). 7. а) (а);(Ь);(с); 6) элементарными конъюнкциями являются рЛдЛт, рЛдЛ т, рЛ дЛт, рЛ ЧЛт, р Л д Л т, р Л дЛ т, рЛ д Л т, рл дЛ т. Пересечение любых двух из них порождает противоречие и, следовательно, равно Р, нулевому элементу; в) (б),(в); г) (б),(в),(г). Ответы я упрвжнвниям 899 Раздел 9.4. 1. е [о] [ц (2] [з] [0] [О] (Ц [2] [3! [ц (ц [2! (з] [о) (2! [2! [з] (о] (Ц [з! [з] [о! (Ц [2] 3.
(2]. 6. (3]. 7. Да. 9. Пусть а = Зт и О [О! [Ц [2! (3! (о) (о] [о] [о) [о] (ц (о! [» (2] (з! [2) (0] [2! [О) [2) [3] (О] [3! [2) [Ц Ь = За. Тогда а+ Ь = ЗЛ+ За = 3(/с+ тс), поэтому сумма а и Ь кратна 3. Несомненно, 0 = 3 0 принадлежит множеству. Обратным элементом для ЗЬ будет ( — 3)Л. Следовательно, это подгруппа. 11.
Согласно задаче 5 раздела 9.2, это полугруппа. Поскольку (0] + (а] = (О + а] = (а], то (0] является единицей. Поскольку [а) + (6 — а] = (6] = (0], то каждый элемент имеет обратный элемент. Следовательно, Ле — группа относительно сложения. Это множество не является группой относительно умножения, так как элементы [0], (2], [3] и (4] не имеют обратных элементов.
13. Элемент дэ — единица, принадлежит множеству и лучше обозначить ее через до. Согласно этим обозначениям д' . д' = д*, где 0 < з < р и з и д + г (тоб р). Обратным элементом для дс является дэ с. Раздел У.б. 1. имеем 7'(1) = /(1 1) = г'(1) 7'(1), поэтому 7'(1) — идемпотент. Вполне очевидно, это единица группы Н, поскольку в группе Н только идемпотент является единицей. 3. Если 7"(Ь) = 7(Ь'), то аЬ = аЬ'. Следовательно, а 'аЬ = а 'аЬ' и Ь = Ь'. Таким образом, функция 7" — инъекция. Пусть Ь 6 Н. Тогда 7"(а 'Л) = аа 'Ь = Ь. Следовательно, 7— сюръекция. б. Определим У: Яз — лс соотношениями У(0) = 1, У(1) = 3, 1(2) = 4 и У(3) = 2. Соотношение легко угадать, поскольку мы отображаем 1, что порождает Уз~ на 3, а это, в свою очередь, порохсдает Яс. В изоморфности также легко убедиться, проанализировав следуюшие таблицы 7.
Пусть = (1,6с). рг(1,6с) = (рыфс) и (1,6г)рс = (рыфз), поэтому группа Н не является нормальной. 9. Было уже показано, что ф(1) — единица группы Н и, следовательно, группы ф(К). Пусть Ь,Ь' 6 ф(К). Тогда Ь = ф(д) и Ь' = ф(д') для некоторых д,д' 6 Н. Л. Ь' = ф(д)ф(д') = ф(д д'), поэтому Ь. Ь' 6 ф(К). Далее, ф(д ') . ф(д) = ф(д . д ') = ф(1), поэтому если Ь 6 ф(К), то Л ' 6 ф(К). Следовательно, ф(К) — подгруппа группы Н. 900 Ответы к упражнениям Раздел 10.1.
1. а) х= — 20 у=6; в) х=180у= — 87; д) х = 12 у = — 4. 3. а) х= — 28у=36; в) решение не существует; д) решение не существует. 5. Процедура Целочисленное решение(пз, и,с): //Решение уравнения х гп Ч- у и = с// Положить 1 = т, и = и, х = О, х' = 1, у = О, у' = 1; Условный цикл: до тех пор, пока и ~ О, д = (1+ и), 1 = и, и = 1 — ди, х = х', х' = х — дх', у = у', у' = у — ду'; Конец условного цикла; Положить д = и, е = с + с); Если е ~ (е), то решения не существует; Иначе х = ех; у = еу Конец процедуры. б) х=-64у=36 г) х= — 2у=б; Раздел 10.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
