Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 69
Текст из файла (страница 69)
3) 1(х") шефферова при и = 2 и и > 3. 4) 1"(х") шофферова при и = 41+ 1. 5) 7'(хч) шефферова при и = 29 и Д(хч) б Б при п = 21+ 1. 6.11. Имеем 0 й Тг 0 Б, 1" ф То 0 М 0 Ь. 6.12. У к аз анно. Среци трех функций, существенно зависящих от хг, хг, нет самодвойственных и есть хотя бы одна нелинейная. 6.13. Ясно, что 1" К Тс 0 Тг 0 Б. адыгее см.
зэдачу 6.15. 6.14. В силу задачи 5.16 имеем 1" ф Б. Ясно также, что 7' ф То 0 Ты адыгее см. задачу 6.15. 6.15. Из 7' ф То 0 Тг следует, что 7" б М. Если бы 1 б Ь, то из 7 ф То 0 0Тг следовало бы, что 7' б Б, а это противоречит условию. 6.16. Пусть Б(п) число шефферовых функций 7(х"). В силу задан 6.15 Б(п) = ~Р('ЦТ 0Т 0 Б)~ = 2« г — 2« 6.1Т. См, задачи 2.7 и 6.15.
6.18. Поскольку 7' ф К найдутся наборы Н = (г«г0 ..., аы) и гу = (ог1... ..., й„) такие, что 7(Н) = 1((7). Ясно, что Н ф (О, Ц, ибо ДО) = 1, 7"(1) = = О. Заменим в 7"(хг, ..., х„) х, на х, если оо = 1, и на у, если си = О. Полученная таким образом функция д(х, у) шефферова. 6.19. 2) а) 1 б А; б) х 9 А.
6.21. Ц А Ь То, ибо (А! > ~То(. Аналогично А Я Ты А Б Б, А Ь Л. 6.22. В силу задачи 3.24 из нелинейной функции 1 с помощью отождествления переменных можно получить функцию Р(х, у, «) вида ху 91г (х, у) ипи вида ти(х, у, «) 91«(х, у, «), где 1г, 1з линейны. Поскольку 1 б о, то осуществима лишь вторая возможность. Ясно, что Р б Б((То 0 Тг). Тогда с точностью до перестановки переменных либо Р = т(х, у, «), либо 342 Ответы, указания, решенно Р = т(х, у, г). В обоих случаях в силу задачи 2.18 функция К, а значит, и 1(* ')~ образует базис в о. 6.23. Неверно. Например, ху Е То\з(Тз О Ь О М 0 о), но в [(ху)] не входит ни одна функция 7(х") такая, что ~зН1~ > 2", наззример, хз Н хг. 6.24.
Ц Неверно, рассмотреть 7" = х Н у. 2) Верно. 6.26. Ла, например, 7 = хз Ю хг Ю хгхз Ю хзхз удовлетворяет условию задачи и при этом 7 ф о' 0 М 0 Ь. 6.26. Ц., 2) ОЦ~) = (х). 3) ЯФ = (х Ю у., 0). 4) 0((~) = (х, хН у). 627.Ц1,х,х,хр,хбзу. 2)1,х. 3)х,х,ху,хну,х у,хоу. 4) х'*ув, х" Нуо, а, ДЕ(0, Ц, о(Д, т(хз,у,г)96, 7, 66 (О., Ц. 5) 0,1,ху,хНу,ху,хНу, 6.28. Ц, 2), 4) Ла. 3) 5) Нет. 6.29. Ц Ла. 2) Нет, поскольку (ху Ю у, Ц также базис в Рг 3) Ла. 4) Нот, ибо (х Н у, ху) С 07(ху Н гв) и (О, 1, ху, хН у) базис в М.
5) Ла. 6.30. Ксли (Я вЂ” простой базис, то функция 7" шефферова и не может зависеть существенно более чем от двух переменных, так как в противном случае в силу задачи 6.18 имели бы (07(1)) = Рз. Глава 111 1.1. 1) Рассмотреть два случал: х = й — 1 и х ф й — 1. 2) — 7) Рассмотреть два случая: х > у и х < у. 12) Рассмотреть два случая: х = й — 2 и х Р й — 2. 13) Рассмотреть два случал; х = й — 1 и х Ф й — 1. 14) Рассмотреть пять случаев: а) х=у=й — 1; 6)з=й — 1, у~й — 1; в)хай — 1, у=й — 1; г)хай — 1, у~й — 1, х<у; д)хай — 1, у~й — 1, х>у. 15) Рассмотреть четыре случая: а) х=у=й — 1; 6)х=й — 1, зу~й — 1; в)хай — 1, у=й — 1; г)х~й — 1, у~й — 1.
16), 17) Рассмотреть три случая; а) х=й — 1; 6)хай — 1, х)у; в)х~й — 1, х<у. 20) Рассмотреть три случая: х = О, х = 1 и х > 2. 23) Рассмотреть три случая: х = й — 1, х = й — 2 и х ) й — 3. 1.2. 2) х = шах(Уо(х), ппп(х, зз(х))). 3) уз(х) = шах (1, о'з(хз)), ~з(х) = Уз(~з(х)), (г(х) = )о(х) и х = шах (уо(х), зз(х)). 5) Пусть х у 4-х — у 4-1 = оз(х, у). Имеем оз(х, х) = х, Зз(х, т) = О. Далее получаем все константы и а) при й = 3 зз(2, х) = уз (х); 6) при 1з = 5 Р(0, х) = 1 — х, а значит, можно построить функции — х', хз, х -О 4(= х — Ц и уз (х) = 1 — (х — Цз. 8) - * = шах( 7о(х) 4(х 4- 2) 21~(~)).
9) 14 (х) = (((Х ((х — ' 1) — ' Ц вЂ” ' 1) — ' 1) — ' 1) — ' 1. 343 Гхь ПЙ й-званные лоепни 12) дь г(х) = (... ((х — '( х)) — '( х)) — ' ... — '(:с)) — '( х) ( х вычитается й — 2 раз). 15) х = ( (( х) — ' Ц) — 'оь г(х), а,7г г(х) можно представить формулой над множеством ( х, х — 'у) (см. 12)). 1А.
Ц Взять у = гп — 1. 2) Рассмотреть функцию 1 — '2х. 1.5. Полезно воспользоваться соотношением х Э у = шш (й — 1, у— — х+ й — Ц, где в выражении у — х + й — 1 сгнгжение и вычитание обычные, а не по модулю й. Индукцией по г можно доказать, что 6,(х) = = ш1п (й — 1, г(й — 1 — х)), г = 1, 2,, й — 1. 1.6. й ~ 3, 4, 6, 12. 1.7. При й = 4, б, 8, 9, 10 число различных функций указанного вгша равно соответственно 3, 2, 4, 7, 4. 1 8 гг — г(х) = оь г(х) -г , + ол — г(х) (й — 1 слагаемых); 11(х) = = уя г(х — г — Ц, 0 < э < й — 2.
Если д(х) б Р, ,то д(х) = д(0)уо(х) + ... ... ф д(1)1,(х) ф... т д(й — Цуь г(х). Остается учесть, что Ц,(х) = = 1, (х) -~-... -~- г, (х) (1 слагаемых). 1.10. аз произвольное и (Ц, если аг = О, то ао произвольное, (2), если аг Р О, то либо ао = аг, либо ао = 2аг (т.е, если аг Р О, то ао Р 0). 1.11. Ц х = шах (шгп (1, оо(х)), Зг(х)) =ус(х) ф 21г(х). 5) Лг(хг 4-х) = шах(ог(х), оз(х)) = 4уг(х) + 41з(х). 10):о — 'у = шах(ппп(1, гг(х), оо(у)), ппп(1, дг(х), гг(у)): пцп(1, о' (х)., ог(у)), пйп(Лг(х), го(у))) = = уг (х)уо(У) + уз(х)уг(У) + уз(х)уг(У) + 21г(х)уо(У) ~2 2.1. Ц Положим Т((0, 2)) = Т и 'М((0, Ц, (2)) = г11; а) хбТи ф'11: в) Хг(х) бТГ1о(1; д) х+удТи ф'И.
2) ПоложимТ((1, 3)) = Т, о)Х((0, Ц (2) (3)) = оИг о11((0, 3) (1 2)) = ='опг; в) уо(х) ф Т, с оуг и ~ ~уз; д) шах(х, у) с ТО'Мг и ф %г,' е) х уеТ, ф'Иг и Рог)йг. 22.3) 8=(Ц, Йг=ЦО), (1,2)). 4) К = (2),подходяшее разбиение подобрать нельзя. 8) К = (0), Йг = ((О, 1, 4), (2, 3)). П) Е = (О, Ц, гСг = ((О, Ц, (2, ..., й — 1Ц. 12) Е=(0, й — Ц; Р=((0,2), (Ц) при й=З и Р=((О,й — Ц, (1, 2, ..., й — 2)) при й ) 4. 2.3.
2) 2ь — 1. 3) Если Е = И, то )(Т(Е))~"~! = йь . Если 1 < гп = )Е( < й — 1, то ((Т(е))1"г) = гп"' й~ 2.4. 2) В Рг сушествуот 4 различных класса типа ог)1(В), если считать и все множество Рз. В ЕЙ их 14, а в Рз их 51. 3) Пусть (1г, гг,, г ) набор чисел из множества (1., 2....., з).
Всего таких наборов о". Упорядочим их в доксикографическом порядке и пере- нумеруем, приписав номера от 1 до з". Набор (1, 1,..., 1, Ц будет иметь номер 1, набор (1, 1,..., 1, 2) номер 2, набор (1, 1,..., 1, 2, Ц номер з ф 1 и т.д. Если набор (гг, гг, ..., г,) имеет номер ш, то 344 Ответы, указания, дешевев число )Е„) (Е, ) °... ° )Еы! обозначим через 4 . Число функций в множестве Рь(Хо), сохраняюгцих разбиение В = (Еы Ез, ..., Ев), равно )Рл( ' )8„) '.... )Е„( ', где т = в" и суммирование ведется Оом и) по всем наборам длины в", составленным из чисел, принадлежащих множеству (1, 2, ..., в). 2.5.
Ц Пусть 4,„обозначает число (Е„( .... )Е,„), где щ -. номер набора (и, ..., Ьв) в лексикографическом упорядочении множества всех наборов длины и, состоящих из чисел 1 и 2 (как в задаче 2.4, 3), если в = 2). Число функций из Рь(Х"), входящих в Т(К)~%(В), при и ) 1 равно 1~ с й — ~ )еоо( ' ...ЦЕ,„) ", где Е~ = Е, Ез = Ее'18, 1=)Е), 02* ° о ) т = 2" и сумма берется по всем наборам длины 2' — 1, составленным из чисел 1 и 2.
Если п = О, то таких функций нет. 2) ((%(В)1Т(Е))Ю~! = ~Еь'1Й~ = й — 1, где 1 = (Е). Если и ) 1, то )(11(В)1Т(е))" ! = (й — 1) ~ )Е„) ' -... ~Е,,) ' (1, т, 11 и е( такие Оз "оО же, как в задаче Ц). 3) й,если п=О,и 1' йь ' ф(й — 1)" ~ ~Е,о~'.. ~Ко,/",если и)1. 02». о ) 2.0. 2) (2!)(й — 3)5 3) х —',, хз х4 б) хауз 7) хуз 4- ту+ ь — г 9) (й — Ц(1 — (х-~-2)ь ') = ~) ( . )2'х~ *=о ь — 3 10) 1 — (х — хз — 2) ' = ~( — Ц'~ ( )2'х~ '~ '(1 — х)~ =а 2.8. Ц достаточно реализовать полиномом функцию 21о(х), ибо 21 (х) = 2 1о (х — 1) (1 = 1, 2, 3), 21а (х) = 2 -~- х -~ хе = 2 -т Зх -~- Зхз = 2 -~ х -т +2х'+ Зхз = 2+ Зх+ 2хз+ хз.
2) Если ((х) б Рв и 1'(Е4) С (О, 2), то 1(х) можно представить в з виде 1 Ь, ° 21,(х), где 6, б (О, Ц (1 = О, 1, 2, 3). Если 1" (Ее) С (1, 3), то =о рассмотреть функцию д(х) = Йх) 2.9. Функции 1(х) — уз(х) и 1" (х) — 1~(х) принимают значения только из множества (О, 2). 2.10. б4. ВРе справедливысоотношения2хз = 2х = 2х иЗх = 2х+ х .
2.11. Ц Сравнить друг с другом функции х, хз и х из Ра. 2) В Рв выполняется соотнозпение Зх' = Зх. 3) Либо 6=2 и о=2,5,либо 6=4 и а=1,4. 2.12. Ц, 2), 4) Не представима. 3), 5) Представима. 2.13. 2) Т((1, 2)). 3) аМ((0, Ц, (2, ..., й — Ц). 5) Т((0, й — Ц). 9) Т((1, й — Ц). 13) а)4((0), (1, 2, ..., й — Ц). 15) Т((1, й — 2)). Гас Пй й-заочные яогвви 345 2.14. Ц Такой подсистемой является множество (уо(х), х + у).
2) (О, х "; у, х у) С Т((0)), (уо(х), уг(х), , уа г(х)) С Т((0, Ц), (1, 2...., й — Ц С Т((1, 2...., й — Ц). 2.15. Ц АгЗ,(г) С Т(Жу„.г,(г)), г = 1, ..., й — 2. 2) АгЗ(0, й — 1, 7о(х), Уа г(х)). 2.16. Ц Полна. 2)-4) Не полна. 2.17. Ц Полноту в Яа данной системы можно доказать так: индук- цией по г (г > Ц установить, что любая функция у из оя, удовлетворяю- щая условию д(х) = х при х > г, порождается функциями из множест- ва (6ог (х), ..., 6о, (х)); затем положить г = й — 1.
2) Так как йо (6, аг(йы(х))) = йо, . г(х) (г = 1, 2, ..., й — 2), то дан- ная система порождает каждую функцию из задачи Ц, 3) Принять во внимание, что йь,рг(х -> (й — Ц) -~- 1 = 6 зид ег(х) (г = =0,1,2,...,й — 3). 2.18. Ланная система порождает множестно оа. Используя функ- цию х -~ус(х), можно построить любую функцию, выпускающую ровно одно значение (из Еа).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
