Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 68
Текст из файла (страница 68)
Палее см. задачу 4.5, 5). 2) А не является базисом в То, так хак А С То С Ть 3) А не является базисом в Ты так как [(ху, х уЯ = Ть 4) А не является базисом в То О Ты так как А С сО 5) Нет, так как [(ху, х Ю у 63 хН = То С Ть 6) А . базис в То С Тз, см. задачу 4.5, 5) и задачу 1.2, 12). 4.7. Ц ау = (0110), ~ = х~ ~Э хз. Решение. 1(хо) 6 Ь существенно зависит от хз и хз и 3(00) = О. Отсюда 3 = хо СО хз.
Утверждение о том, что [(хз Ю хз)) = То СЗ Ь, доказано в задаче 4.5, 7). 2) ау = (10010110). 3) ау = (01100110). 4) Йу = (100Ц. 6) ау = (0110 0110 0110 100Ц, 7) 3' = 1 Ю хд 61 хз Ю хо 8) Еу = (0010101Ц. 22 Г. П. Гаврилов, А. А. Сапоженко 338 Ответы, указания, решения 4.8. Пусть 7»р Т». Тогда либо а) у'(х, ..., х) = О, либо б) 1(х, ..., х) = = х. В случае а) имеем Рг = [(О, 1, ху Ю я)] С [(0) Ез Т»] С [(1] О Т»]. В случае б) Рг = [(х, ху]] С [(З') О 7»]. 4.9.
1) Пусть 1 Е Ь»»А. Тогда 1" существенно зависит более чем от одной переменой. Подстановкой константы 0 из 1' можно получить функцию вида х Ог у ш»т, а 6 (О, 1]. Но [(х ЕО у О» еб х)] = Ь. 3) Пусть г" б 7»»А. Тогда 1(х, ..., х) О (1, х). Палее утверждение следует из полноты в Ь систем (1, х 9 у], (х,х ЕО у]. 4.10. Ц Пусть 1 6 То»»Б. Из 1 отождествлением переменных можно получить функцию у», которая имеет внц либо ху»О 1»(х, у), либо ти(х, у, я) Ю 1г(т,, у, г), где 1», Н линейныс функции (см. задачу 3.24).
В обоих случаях То = [(х О» у, »р]] С [То О 1 П (У]]. 2) А = То О о не является предполным в То, так как А С То Е1 Т». 3) Ла. 4) Нет. 5) Нет, так как, например, [(0) 1З А] ~ То. 5.1. 1), 4), 6), 7) ( ф М. 2), 3), 5), 8) У б М. 5.2. 1) Ла, 1:— О. 2) Ла, у' = 1. 3) Нет, 1(х» 0) = х. 4) Ла, 1" = х»»е'хгхг 5) Нет, 1"(1, О, я) = я. 6), 7) Ла. 8) Нет. 5.3. 1) Н = (010), [з = (110). 2) о = (ООЦ, (1 = (011). 5.4. 1), 3) Лва вектора. 2), 5) — 7) Трн вектора. 8) 18. 5.5.
1), 2), 4)-6) Один вектор. 3), 7) Лва вектора. 8) Три вектора. 5.6. 1) При и = 1 1(х") 6 М. Если же и > 2, то г'(х», 1, О, ..., 0) = х», и, следовательно, » »р М. 2) з" (хт") 6 М при п = 2, 3, ) (х в) К М при и > 4. 3) » (х") монотонна при четных»» и немонотонна при нечетных и. 4) При и = 1 и и = 3 функция монотонна, а при других и, нет.
5.7. При и = 1 такой функцией является х». ?1рн и > 1 таких функций не существует (см. задачу 5.9). 5.8. Если 1 ф. М, то существуют наборы а = (»т», ..., ой) и т = = (т», ..., т ) такие., что Е < т, но 1'(Е) > [(т). Если р(а, т) = 1, то утверждение доказано. Пусть р(й, т) = к > 1. Рассмотрим произвольную последовательность вида 7о,7»»,.,, 7я, где 7о = а, 7» = 'г, 7 -» < 7 (а значит., р(7, », 7,) = 1). Имеем 1'(7о) = 1, »'(7я) = О.
Ясно, что сущест- вует такое», 0 < г < й, что 1(7, ») > 1(7,). Остается положить Н = 7, 6=7, 5.9. Вытекает из задачи 5.8. 5.11. Покажем первое нз разложений. С использованием задачи 5.10 имеем Д(х") = х)»»»»хго = х(з» у )о)»1хзо = хг[»г )о. 5.12. Следует из задачи 5.11 по индукции. 5.13. Предположим противное. Пусть К = х»В - . простой импликант функции 1 6 М. Тогда по определению К»г' 1 = 1, Ь»11" Р 1. Из последне- го соотношения вытекает существование набора Н = (о», ог, ..., о„) тако- го, что Ь(Н) = 1, 1"(Н) = О. Заметим, что и» = 1, так как иначе К(Н) = 1, 1(Н) = О, что противоречит условию.
Положим Д = (О, иг, ..., оы). Имеем Гл. П. Замкнутые классы н полнота 339 Цо) = Ь!»3) = Ь !»3) = 1"!»3) = 1. Из»З < В и 1 б М следует, что 1!о) > > 1О3) = 1. Пришли к противоречию. 5.14. Ц е11) = п11) = 3. 2) еЩ = 2, г»Я = 1. 3) е!1) = пЦ) = 4. 4) е(Д = 2" » и® = !с. 5.16. Пусть П и !3 -- нижние единицы функции 1"(х") из М !и > 2). Тогда !!»»у! = 2!! !!+2!!и!! — 2!!""о!!. Ясно, что )!УГ) не является степенью двойки при о ь' В и 13 ь' Й, а значит, 1" 7 3. 5.17. Ц Рассмотреть В!",ь»з!.
2) Пусть М»" = ) з' б Рл: ! ) В». С !Уу, ! ) В»2 = !Уу). Показать, н>!»3! к<! 12! что М," С М" и !М»" ~ = 2~!Мз!). 5.18. В любой возрастающей цепи длины п куба В" для каждого» = = О, 1, ..., и имеется вершина а, б В,". Ясно, что всегда оо = О. Пля выбора о» имеется п возможностей, для выбора Йз при выбранной вершине с»» имеется и. — 1 возможностей и т.д.
Всего и! возможностей. 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 б Т,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
