Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 68
Текст из файла (страница 68)
Таким образом, 6 = 1,что и требовалось доказать. 3) Указание; Значение Д(0) и условия однозначно определяют ее значения на В". При этом на наборах четного веса значение функции совпадает с Д(0), а на наборах нечетного веса противоположно ему. Такова функция хз ф, .. Ю х„бЗ Д(0). Представление единственно.
3.7. Ц, 2) Вытекает из задачи 3.6), Ц. 3.10. 2('6). 3.11. 2" 3.12. Функция хз -в хг нелинейна. Если 1 6 Ь, то хз — > х = з (хы хз, О....., 0) 6 Ь. Пришли к противоречию. 3.13. Предположим, что у 6 Ь. Тогда 1" = хз Ж... Озх Ющ л 6 (О, Ц. Из условия ((хы О, ..., 0) ф 1(хы 1,..., Ц следует, что и четно. Пришли к противоречию с условием.
3.14. В силу нелинейности функции 1 существуют такие з и у, что 1 = х,х,узах,рз Ю хзрз|3 рю гце. функции р (т = 1,..., 4) не зависят от з и д и р1 ф. О. Пусть й = (оы ..., о, ы о,.~.ы ..., Оз.-ы азьы ... ..., еы) набор такой, что ззз(а) = 1. тогда ф(х„хз) = з"(оы ..., о, х„а,+ы ..., а, ы хз, азе м ...., а„) нелинейна. 3.15. Пос та т о чн о с т ь, Пусть функция 1(х") такова, что в В" найдется специальная четверка наборов Й, )з, у, д такая, что функция 1' принимает на этих наборах значение 1 нечетное число раз. Положим х = о если тбАз.Еслиже тбАытопусть хы=х при 7ы=1и х =у при у = О. В результате такой подстановки из 1 получается функция 7з(х, д) такая, что р(1Ц = з"(а), р(00) = з"(Д, р(10) = з" (7), р(ОЦ = з'(6). Ясно, что Зз(х, д) ф Ь.
Необходимость. Вытекает из 3.14. 3.16. Указание. Используя 3.14, доказать существование грани размерности 2, на которой функция обращается в 1 нечетное число раз. Из того, что ~6ер~ = 2", вывести существование двух граней таких, что на одной из них функция обращается в 1 один раз, а на другой три раза. 3.18. Ц С помощью супврпозиции из функции з1 еэ хз можно получать любую функцию вида хн В х„бэ... 9 хею путем подстановки 1 любую функцию вила хн Ю х„й... Ю хм б 1. Система А является базисом.
2) 5), 7) 9) А является базисом. 6), 10) А не является базисом. 3.19. Пусть 1 6 Ь. Если 1 зависит существенно от нечетного числа переменных, то 1' б В П А. Если З" зависит существенно от чотного числа переменных, то либо з'(О) = 0 и 1 у ((1")), либо ДО) = 1, з" (1) = 1 и 0 ф ((з")). 3.21. Среди функций уы зг, уз хотя бы одна является нелинейной, поскольку сущеСтвуют лишь две линейные функции, существенно зависящие от хг и хз. Кроме того, каждая из этих функций не является самодвойственной. Подстановкой х и х на места переменных несамолвойственной функции 1 получаем константу.
С помощью отрицания получаем вторую 337 Гл. П. Зомкнун~ыс классы и ооляоти константу. Подстановкой О, 1, х, х, у, у из нелинейной функции получаем функцию вида ху 63 а. Имеем [(х, ху 63 о)] = Рз. 3.23. Функция представима в видо 3' = хуя Ваху-~-13хх СО уях Ю1(х, у, л), где а, 13, у принадлежат множеству (О, Ц, а 1(х, у, з) 6 Ь.
Если а = (3 = у = 1, то Д(х, у, у) = ху 191з (х, у), где П 6 Т. Если а -'; )3 4- у = 2 и, например, а = О, то 3'(х, х, .у) = ху 6312(х, у), Ь 6 Ь. Если а -1-33-~- у < ( 1 и, например, а = )3 = О, то 3(х, у, у) = ху Ю1з(х., у), 1 6 Ь. 4.1 Ц, 3), 4)., 6), 8), 9) 3 6 Тз~,То 2), 5), 7), 10) 3 Ф Тз(То. 4.2. Ц, 2) При четных п 3 2. 3), 4) При и = 2, 3 (шоб 4).
5), 8) При всех и ) 2. 6), 7) При всех четных и. 9), 10) При всех натуральных и х 3 (шоб 4). Указание. (2) нечетко при и = 3 (зпоб 4). уо1 4.3. Ц 22 з. 2) — 22 . 3) 2'. 4) 22 '. 5) 22 -> 2". 6) 2". 4 7) 22 -~- 2" '. 8) 2" '. 9) 22 ' 3- 22 ' -~- 2" 10) — (22 + 2").
15) О. 2 4.4. Указание. Если 3' 6 Т Сз Я, о 6 (О, Ц, то 3' 6 Т вЂ” Сз Я; если 3 6 6 1 О Уо СЗ Т,, то 3 6 Я. 4.5. Ц ху = (х Ч у) Ж х Ю у. Палее см. пример 3. 2) Указание. Использовать пример 3 и то, что То — — Ты 3) Указание. Свести к 2). 4) У к а з а н и е. х 63 у = хх Ф у, ху = (ху Ф я) Ф я. Палее см. пример 3. 5) Полинам всякой функции из То О Тз содержит нечетное число слагаемых и не содержит 1 в качестве свободного члена.
С помощью функций ху, х Ф у Ю я любой такой полинам можно построить. 6) См. 5). 7) Указание. Всякий многочлен не выше первой степени и не содержащий слагаемых, равных 1, является суперпозицией функции х 63 у. 4.6. Ц Ла.Имеем 1=ах х, х у=их у, хФуФя=(х у) х, ху = ху 1. Палее см. задачу 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 возможностей и т.д. Всего и! возможностей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
