Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 69
Текст из файла (страница 69)
2) Если Е б Вл, то число возрастающих цепей длины п, содержащих ее, равно произведению числа возрастающих цепей длины !с, соединяющих О с о, и числа возрастающих цепей длины п — к» соединяющих В с 1. В силу задачи Ц это число равно М (п — )с)!. 5.19. Ц Пусть А множество попарно несравнимых наборов из В" и А, = А О В;, а л!и) множество цепей длины и, содержащих вершину о. Имеем п! > ( ) 2(о) = ~ )лео)! = ~ ~)А,!»!1п — »)! > Бел аел о« > Н )() — ()! ~ ~)А,! = (А! Я !(1 — ()!. о« Отсюда )А) < (, )~ »). 2) Указанию При» < lс < и»»2 справедливо неравенство»!1и — »)! > > !с)!гс — !с)!.
5.21. Ц О. 2) 2. 3) п..Е 2. 4) и. 5) 2" — 2. 5.22. Ц Если ~ б 3 О М", то ~ = х„Д' Ч х„(Д')* и Д' б М' '. Отсюда вытекает оценка. 2) Если ~ б М", то У = х У»" »У1о, где 1о б М, о б )О, 1). Функция У полностью опРоделЯетск паРой (1»", уо ). 5.25. При п = 4 в силу задачи 5.23 имеем !М'! = 168, а !З~! = 25б. Палее утверждение вытекает из того, что !М"! < !М (» а (о"! = !о" ) 5.26.
Лля определенности пусть л > !. 1!ля произвольного »3 б А имеется ровно ( !) наборов и из С таких,что »3 < Е. Зля всякого о б С сушествует не более (!) наборов )» из А таких, что Д < о. Отсюда !А~( ) < )С!( ). С учетом тождества ( ) © = (") (, ) получаем требуемое неравенство. 5.27. Вытекает из задачи 5.2б. 340 Ответы, указания, решенно 5.28. С использованием задачи Ц имеем дг(1з) = ( ) ~ (с-~ ) ае)(Н)) = дев„" уезе" = с4- ~ ведя(1) > с-'г ~е игдя е(1) = до .з(1з). Гею" гем 5.29.
Ц Привости индукцию по числу переменных. 2) Провести индукцию по в с использованием задачи Ц. 5.30. Вообще говоря, неверно. Рассмотреть 7(хйз) = хз и наборы (ПО) и (ООЦ. 2) Предположим противное. Пусть условия выполнены, но 1 1е М. Тогда существуют соседние наборы Й, Г1 такие, что Н < Г1 и 1(о) > Щ). Пусть наборы о, 71 различаются в (и — й)-м разряде. Тогда и(Г1) = и(Н) 4- -Ь 2я и по условию 7(Н) < 1()3). Пришли к противоречию. 5.31.
Заметим, что Е(оо, оы ..., а е) = 1 тогда и только тогда, когда выполнены условия задачи 5.30, 2), т. о. если вектор (ао, ..., ая — з) является вектором значений некоторой монотонной функции. 5.32. Ц Нельзя,так как 1" б То, а х Х То 2), 3) Нельзя, так как 1 6 о, а х» ф о. 4) Можно, 1" (х, О, 1, О) = х. 5) Можно, У(х, О, я, 0) = хю 6) Можно, Ях, у, я, я) = з. 5.33. Если 7 гн 1, то 7 б Т~ П Ь. Если ~ ги О, то ~ б То Гз Ь. Если ,Г ф (О, 1), то 1 6 То Г1 Ть 5.34. 1 6 М~,То, 0 6 М~,Ты ху 6 М~Я, ху 6 М'~й. 5.35.
Нельзя, так как (ху, ху у, 1) С Тм а 0 ф Ть 5.36. Полнота системы (О, 1, ху, х У у) вытекает из задачи 5.12. 5.37. (О, 1, ту, х Ч у), (О, 1, худ я), (О, 1, ху Ч уз 'о' ях). 5.40. Ц (О, ху, х 'о' у). 2) (1, ху, х 'о'у). 3) (О, 1, х). 5.41. Следует из задачи 5.36 и того, что 1* = О, 0" = 1, (ху)" = х Ч у, (х Ч у)* = гу. 5.42. Нельзя, так как З' 6 Я, д Х Я.
5.46. 2) Функции из М" Г1 о для и < 3 получаются из ги(хз) отождествлением переменных. Функции из М" П о при п > 3 можно получать из функпий, зависящих от н — 1 переменных, с помощью разложения из задачи 2.17. 5.47. Покажем, например, что То П М является предполным в М. Заметим, что М'~То = (1) и (О, ху, хм у) С То Гз М.
Теперь )(1) ЕЗ (М Г1 То)) = = М вытекает из задачи 5.36. 6.1. Ц Нет, А С То. 2) Да. 3) Нот, А С Ь. 4) Да. 5)Нет, АСо, 6)Да. 6.2. Ц Нет, А С Ь. 2) Нет, А С То. 3), 5) Да. 4) Нет, А С о. 6)Нет, АСМ. 6.3. Ц, 4), 6) Да. 2) Нет, А С Я. 3) Нет, А С 7'ы 5) Нет, А С Ь. 6.4. Ц Нет, так как подсистема (х о у, х Ю у) полна. 2) Да. 3) Нет, А С Ть 4) Нет, можно удалить ту о' я. Гл. П.
Замкнуигые классы и полнота 341 6.5. Ц Бг = (1, х, 7), Бг = (х, ху(х9 у), 1), где 7 = х 9 уфху9 9 у«9 «х. 2) Бг = (О, х э у), Бг = (х 9 у,. х л у), Бз = (О, ху х«), Бл = = (х9 у, ху х«). 6.6. Ц Рг. 2) МСТг. 3) (МП0)'зБ. 4) ТСБ. 5) Б. 6) ЬПБ. 6.Т. Ц а) (х ~ у), (х 3 у); б) (х 9 у, х э у), (х у, ху), (ху, х -+ у) и оше четыре базиса, получающиеся из них перестановхой переменных в функциях ху, х Л у; в) (хг9«г хг хг хУ) (х9У х У хУУ). 2) Указание. С использованием критериапьной таблицы убедиться, что нет базисов, отличных от перечисленных в задаче Ц.
6.8. Ц Ла, А 0 (0) " базис. 2) Нет,. функция х входит во все предполные классы. 3) Па, А 0 (1) — — базис. 4) Нетг функции ху и х зг' у принадлежат одним и тем же предпопным классам. 6.9. Ц Вообще говоря, нет. Рассмот1ють уг = х 9 у 9 «, 7г = хг Ч хг у хз. 2) Ла, имеем (г — = 1 К Б, 7г и М 0 Ь 0 То 0 Тг. Система полна. 3) Вообще говоря, нет. Рассмотреть уг = х — э у, 7г = 1. 4) Вообще говоря, нет. Например, Тг =:«, уг = 1. 6.10. Ц 1"(х") не является шеффоровой ни при каких и.
Если и четно, то ) б Тм Если п нечетно,то 7 б Б. 2) При четных п функция шефферова, при нечетных 7 б Т,. 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; д) х+удТи ф'И.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
