Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 156
Текст из файла (страница 156)
Мы хотим доказать, что 2"+' > (й+ Цз. Но по индуктивному предположению 2" > йз и согласно результату предыдущей задачи 2 > 2й+ 1. Поэтому, складывая, получаем 2" + 2" > йз + 2й+ 1 или 2~е' > (й+ цз. 13. Для и = 8 имеем 8 = 3(ц + 5(ц. Предположим истинность утверждения для и = 1с, поэтому й = 3г+ 5з. Если г > 3, то й + 1 = 3(г — 3) + 5(з + 2). Если г < 3, то з > 1, поэтому й+1 = 3(с+ 2) + 5(з — ц. Так или иначе, мы выразили й+ 1 в надлежащем виде. 15. Для и = 1 имеем а = а, поэтому равенство истинно для г! = 1.
Предположим истинность для и = й, поэтому а " = (а )". Используя затем индуктивное предположение, имеем гй.!.!) й!. й ° .й ° )й.!-! а =а =а .а =(а ) а =(а 17. Для и = 2 имеем 1 — —,' = зз! или -, '= з, поэтому утверждение истинно. Предположим истинность для и = й, поэтому 1 1 1 / 11 й+1 (1 Н1 Н1 ).. ~1 )= 4 9 16 1, йз) 2й Мы хотим показать, что 1 1 1 1 / 1 ! й+2 (1 — -Н1 — -)(1 — — )" (1 — — ) ~1— 4 9 16 йз (, (й+ Цз) 2й+ 2' Умножая на (1 — — „'-,г) обе части равенства, записанного для г! = й, имеем 1 1 1 1 / 1 ! й+1/ 1 (1 Н1- И1- — )" (1- — )~1- 4 9 16 йз 1, (й+ Цз) 2й 'Х (й+ Цз / — 1— Но й+1 1 ) й+1 /(й+Цз 1 йз+2й й+2 2й ( (й+Ц ! 2й ( (й+Ц ! 2(й+Ц 2й+2' (Й А)ПА= !=1 (() ') А,) ПАйе!) ПА = =1 (() ) А,)ПАйе!) ПАПА = =! «Й А,) ПА) ПА„„ПА = =! (( )(А, ПА)) П(Айе! ПА) = =! й+1 () ) (А,ПА)) *=! определение из предыдущей задачи поскольку А и А = А закон коммутативности индуктивное предположение определение из предыдущей задачи; и утверждение истинно для и = й+ 1.
19. Некорректный переход от й = 1 к й+ 1 = 2. 21. а) для и = 1 имеем А! ПА = А! ПА. Предположим истинность утверждения для и = й, так что (П", ! А,)ПА = П,".,(А,ПА). Мы хотим показать, что ((),"+!' А,)ПА = П,"+,'(А!ПА). Но 874 Ответы к упражнениям г) НОД(12, 16) = 4, НОК(12, 16) = 48 НОД(12, 16) НОК(12, 16) = 192; Раздел 3.5. 1 а) 7 2з 13 6) 1599 = 1600 — 1 = (40 — 1)(40 Ч- 1) = 3 13 41; в) 3 23.
71; г) 131; д) 523. 3. 5и7,11и13,17и19. 5. Если одно из простых чисел не равно 2, то сумма аз+Ьз никогда не будет простым числом, поскольку она делится на 2 7. 479001603 = 12! Ч- 3 и 479001603 = 12!-1- 7. 9. Пусть р, р + 2 и р + 4 — три последовательных нечетных числа. Число р может быть записано как Зт, Зт+ 1 или Зги+ 2. Если оно имеет вид Зт, то оно делится на 3. Если оно имеет вид Зт+ 1, то р+ 2 делится на 3.
Если оно имеет вид Зт+ 2, то р-Ь 4 делится на 3. Поскольку одно из трех чисел должно делиться на 3, эти числа не могут быть все простыми. 11. Если 0 < Ь(1) < а(1), то р1Гч(р',01 для всех Е поэтому 6(а. Если 6)а, то рь01(а. Учитывая единственность разложения целого числа на простые множители, можем утверждать, что ьГО р, * является частью единственного разложения числа а, поэтому р,0~~р, и. 6) для и = 1 имеем А', = А',, поэтому равенство справедливо. Предположим истинность утверждения для и = )с, поэтому имеем (((,", А,) = Ц",, Аи Мы хотим доказать, Р Ф что ((),".1,'А;) = (),"'",'А';. По закону де Моргана (П,"'1,' А;) = (П,, А,ОАь+1) = ("- П,"., А;) ОАь.ы. Воспользовавшись индуктивным предположением, имеем (П,, А,) О А'„+, — — Ц,, АиОАьэ, = Ц+, А',.
Следовательно, утверждение истинно для и = (с+1. 23. Предположим, что Т удовлетворяет условиям (а) и (б) второго принципа индукции. Пусть Т' — множество всех целых чисел, для которых утверждение Т не является истинным. Если Т' не пусто, тогда, согласно принципу полного упорядочения, Т' содержит наименьшее положительное целое число, например, и. Но поскольку и — наименьший элемент в Т' для всех т таких, что т < и, утверждение Т истинно. Это противоречит (б), поэтому Т' пусто и Т истинно для всех и.
25. Предположим, что Т не пусто, Тогда, согласно принципу вполне упорядочения, это множество имеет наименьший элемент, например, и. Но по условию 2 существует т < и, которое принадлежит Т. Это является противоречием, поэтому Т пусто. Раздел 3.4. 1. а) 54,27,18,9,6,3,2,1, б) 63,21,9,7, 3, 1; в) 72,36, 18,9, 24, 12,6,3,8,4,2, 1; г) 73,1; д) 74,37,2, 1. 3. а) НОД(54,27) = 27, НОК(54,27) = 54; б) НОД и НОК не определены; НОД(54, 27) НОК(54, 27) = 1458; в) НОД(6, 15) = 3, НОК(6, 15) = 30; НОД(6, 15) НОК(6, 15) = 90; д) НОД(ЗЗ,Н =1, НОК(ЗЗ,Ц = ЗЗ; НОД(33,1) . НОК(33,1) = 33. 5. В качестве НОК(а, 0) можно было бы взять О. Число 0 является кратным для а и для О.
Если некоторое число делит а и О, то оно делит О. 7. НОД(а, Ь) делит а и 6, поэтому он делит а — Ь. Следовательно, НОД(а, Ь)(НОД(а — Ь, Ь). Обратно, если любое целое число делит а — Ь и 6, то оно делит а. Поэтому НОД(а— Ь, Ь)( НОД(а,6).
Следовательно, НОД(а — Ь,Ь) = НОД(а, Ь). Ответы к упражнениям 875 Раздел 3.6. 1. а) 1; 6) 3', в) 2; г) 14. 3. а) 0; 6) 1; в) 1; г) 1. 5. Если а — нечетное целое число, тогда а = 2Ь + 1 для некоторого )с. Следовательно, а = (2)с + 1) = 4Ь + 4)с + 1 = 4(Ь + ))с) + 1, так что а — 1 = 4()с~+ )с) = 4)с(Ь+ 1), и поскольку либо )с, либо )с+ 1 — четно, то аз — 1 делится на 8, и а еа 1 (арпад 3). в) (Ц; г) (3(; д) (0(, (2), 11. а) (3]; 6) (2(; 13. Если а ге Ь (тод ти), то а — Ь равно )сти для некоторого )с.
Учитывая, что а — Ь равно ()си)т, имеем а ке Ь ()пос) т). Аналогично, а ж Ь ()пос$ и). 15. Уже известно, что существует одно и только одно т, где 0 < и < и такое, что а = т (пюд и). Мы должны показать, что г является также взаимно простым с и. Поскольку а = ид+ т для некоторого д, и если г не является взаимно простым с и, то существует целое число ис такое, что и = ссп и г = Ит для целык чисел с и с(. Следовательно, а = стд + ат = (сд + с() т, так что т также является множителем а, что противоречит предположению о том, что а и и — взаимно простые числа. Раздел 4.В 1.
а) область определения у — множество В; область значений у — (у: у > 4); б) область определения 1 — (х;х > 2); область значений г — (у: у > 0); в) область определения 1 — (х:х > 2); область значений 1 — (у: у > О); г) область определения 1 — множество В; область значений 1 — (у: 0 < 1); д) область определения у — множество  — (2, — 2); область значений 1 — (у: у < --„') ь) (у: у > о); е) область определения г — множество В; область значений 1 — (у: у > 0). 3.
в) У(д(х)) = (х+3) + 1, д(Дх)) = хэ+ 1+ 3 = хз+ 4; 6) х) )*)) - ст '~т )) ~ 2. )л*)) = * + 5; 876 Ответы к упражнениям в) /(9(з)) =, 9(/(з)) = — + 3. 1 2 $. а) не удовлетворяет ни одному из условий; б) не удовлетворяет ни одному из условий; в) инъективна, сюръективна, имеет обратную функцию; г) не удовлетворяет ни одному из условий; д) сюръективна ' / ' = / '1 = /-'(/9) = (/- /)д = /и д = д. 9.
а) предположим, что / не инъективна, тогда существуют а,а' 6 А такие, что /(а) = /(а') = Ь для некоторого Ь 6 В. Следовательно, / '(/(а)) = / '(Ь) = (а,а'), поэтому неверно, что / '(/(И') = И' для всех Иг С А. Предположим, что существует И' С А такое, что / '(/(И') ~ Иг. Пусть а 6 / '(/(Иг) и а ф И'. Но /(о) 6 /(И') по определению / ', например, /(а) = Ь. Поскольку Ь 6 /(И'), то существует а' 6 Ру' такое, что /(о') = Ь, и / не является инъекцией.
6) если / не является сюръекцией, то существует Ь 6 В такое, что оно не принадлежит /(А). Следовательно, // '(Ас1(Ь)) ф Аы(Ь). С другой стороны, предположим, что /— сюръекция. По определению функции / ' соотношение // '(И') С И' выполняется всегда. Пусть ш 6 Иг.
Поскольку / — сюръекция, то существует а 6 А такое, что /(а) = ш, и при этом а 6 / '(И'). Следовательно, /(а) 6 // '(И'), поэтому ш 6 // '(Иг) и И' С // '(Иг). Таким образом, И' = // '(И'). 11. Пусть а 6 А и /(а) = о'. /(/(а)) = /(а') = а' = /(а) = /(1(о)). Если / имеет обратную функцию, то / '/(а) = / '(о') = а = 1(а). Пусть а 6 А и а" = / '(а), тогда // '(а) = /(ап) = а = /(а). Раздел 4.3 2 3)' 2 3 ) 2 3 4 ) 2 3 4 ) 3. а) 14; д) -2; 5. а) 6,11,18,2738; в) -4,— 2,— 1,— 1,0; 7. а) А(п) = 2п', в) А( ) = ( — 1)"+' (азад ); в) — 9; ж) 5. 6) 2,3,2,ез г) 1,-1-', зз б) А(п) = г) А(п) = 6) 630630; е) -3; г) -2; 1( 1) -и па+ 2. 1. а) /од= ( до/= ( /-'= (,' .— = (,' в) /ад = /1 до/= ( '=(' 9 = ( 6) /од= ( / 1 до/= ( /-' = (,' "=(' г) /од=( /1 до/= ( ( 3 "=(' Ответы к упражнениям 877 Раздел 4.8 -4 — 3 12 5 21 8 5 0 -20 -3 5 15~ б) 11 23 41 7 13 67 1 39 — 10 3 -5 0 9 -15 0 12 -20 0 15 -25 0 г) [-13]; в) [ — 12 за) [,8 [-26 60] э) [ [ 15 [35 ] ТогдаАВ=АС= [ ] но Пусть А = В ф С.
Предположим, что А и  — матрицы, и их произведение АВ определено, Пусть С = АВ, так что См — — 2" А,ьВь . При этом, в матрице 1АВ)' элемент С', = 2 АгаВьз или С,'з = 2 А,ьВь,. Пусть С = В'А', тогда С, = 2 Ва.Азь = ') А,кВы. Следовательно, В'А' = (АВ)'. Пусть Н и Я вЂ” отношения с матричными представлениями М и йг, соответственно. Пусть А = м л х, если (о„а11 6 йй Я, то (а„аш 6 В и (а„а н 6 Я.
поэтому м„= 11гы, = 1, так что А; = Мн д дг„= 1. Следовательно, если Аы = Мн д дгы = 1, то М„= дгы = 1, так что (а„ау> 6 й и (амагп 6 Я. Следовательно, (апаш, 6 ВО Я. Поэтому МО л дгы является матричным представлением для Н П Я. 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 г- [ 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 О 0 0 0 0 0 0 а)В '= б) Вой= о о ] 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 1 в) ВОЯ-! = 0 0 0 0 г) Я 'оЯ= -г] 42]' ) [69 42 ] ' ) [ 15 25 ]' [ — 25 0],В= [" е) [ в) [ )[ -4 ] 0]иС вЂ” 25 — 29 ] 66 — 1 — 10 24] 33 31 9 д) 77 'оЯ О О О О О О О О О О О)О О О е) То(ЯоВ) = О 1 О О О 1 О О О О 1 1 О О О О ж) То Я = э) (ТоЯ)ой= 13.
Я = и= 6) У )и г) Я. 15. а) ((1, а), (1, с), (2, Ь), (3, с), (4, а), (4, Ь) ]; 6) ( (1, Ь), (1, с), (2, а),(2, Ь), (3, а), (3, с), (4, а), (4, с)); в) ((1,а),( 1, с),(2, Ь),(З,а),(3, с),(4, Ь) ). в) в~~ос О О О О О О 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 6) 19. а) в) 6) 11; в) счетно бесконечное. 4 5 ) -4 — 5 12 1 4 5 ... 11 ( -7 — 6 ... О 878 Ответы к упражнениям 1 1 О О О О О 1 1 О 1 О О О 1 О О О О О О О О 1 О 1 1 1 О О 1 1 1 О О 1 1 1 О О О О О 1 О О О О О 1 17.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
