Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике (1048833), страница 67
Текст из файла (страница 67)
Лля и = 1 утверждение очевидно (соответствующими полино- мами являются О, хт и Ц. Пусть утверждение верно для и = к (й ) Ц. Покажем его для и = 1 -~- 1. Если 1 ( 2 ', то по индуктивному предположеь нию существует полинам Р(х ), длина которого не превосходит й и такой, что [тЧ; ] = 1. Но тогда полинам хялтР(х") обращается в 1 в ( вершинах куба Вьл'.
Если 2ь (1 ( 2а~', то рассмотрим полинам Р(х"), обращаюпгийся в 1 на 2~+~ — 1 наборах из Вь. Полинам хтлтР(х~) йт 1 является искомым. Глава 11 1.1. Ц (хт, хт, хг, хг). 2) (О, хт, хг, хт чт хг). 3) (О, 1, хт, хг, хт, хг) 4) (хт, хг, хтхг). 5) (хт, хг). 6) (1, хт, хг, хч Ч хг, хт Ч хг, хт Ч хг). 1.2. Ц ~ = х -+ О, 2) )' = ((х ф х) 4 (у 4 у)) 4 (х ф У).
3) у = (х Озх) б~х. 1) 7 = (х у) г, 5) ~ = хх Озх. 6) ~ = х(ух). 7) 1 = (х Ч х) Ч (У Ч ту). 1.3. ц (О, 1, х, х). 2) (х, ху, хуг). 3) (1, х, х у, х бз у Ю г). 4) (х., хтт Ч уг Ч хх). 5 (х, х, х ОЗ д ОЗ г, х й у Ю г йт Ц. 1.4. Ц (О, х). 2) (х ОЗ у, 1). 3) (х 9 у). 4) (ху, х Ч у].
5) (х — т у). 1.5. Ц, 3), 7) Множество является замкнутым. 2), 4)-6), 8) Множество не является замкнутым. 1.7. Пусть А предполный класс замхнутого хласса К. Это означает по определению, что [А] ~ К и [Аст'(1)] = К для всякой функции 1 б К'тА. Предлотюжив, что А не является замкнутым, имели бы [А]ттА ф О.
Но тогда, с одной стороны, [А 0 ([А]'1А)] = К., а с другой стороны, А С1 ([А](А) = [А] и [[А]] = [А] в силу замкнутости [А]. Пришли к противоречию. 1.9. Ц, 3), 5), 7), 8), 10) Множество А является замкнутым. 2), 4), 6), 9) Множество А не является замкнутым. 1.10. Ц (0]., (1), (1, О). 2) Кроме классов п. Ц еше [О, х], [1, х], [О, 1, х], [х], [О, х], [х]. 3) а) [ху]; б) х бт у, х у]. 1.12. Ц Система (х, ху, х Ч у) является полной в Рг, поскольку всякая 1 б Рг может быть представлена в виде д.н.ф.
или к.н.ф. С другой стороны, х=х4х, ху=(х(х)ф(уфу), гЧУ=(хфу)ф(хфу). 334 Ответы, указания, решения 2) Имеем 0 = хх «9 х, ху = ху 6«0, х = (х х) б«х. Система (х, ху) полна, поскольку х Н у = х у. 3) Имеем к=хи«хВОх, хНу=х — «у, ху=х — «у. 4)Имоем 0=1(х,х,х), х=х — «О,.
ху=х — «у. 5) Имеем х =хб«06«1, ху=т(х, у, 0). 1.13. 1) Кг С Кг. 2) Вообще говоря, Л«,7Кг. Рассмотреть Аг = (х, ху), Аг = (х, х О«у). Ф 1.14. 1) Например, К« = (0), Кг = (Ц. 2) Например, Л« = [х, 0], Лг = [х, Ц. 3) Кг = [О, х], Кг = [О, 1, х]. 1.15. Ц Мг = [О, 1, х], Мг = [х] предполные в К.
2) М« = (0), Мг = (Ц. 3) [х]. 4) [х«йу«рг]. 1.17. Пусть К - — предполный класс в Рг. Если х ~ К, то в силу пред- полноты К имеем [К С (х)] = Р . Но в силу 1.7 и 1.1б имеем [К С (хИ = = К С (х). По условию х]у ф [Л], а значит, х ] у ф Л С (х) = Рг. Противоречие.
118. Пусть 1(х") не является константой Если «(х, х, ..., х) С (х, х], то на «, очевидно, можно получить х. В противном случае «(х, х, ..., х) б б (О, Ц, Пусть для определенности ((х, х, ..., х) = О. Поскольку [(х"') х Х О, то существует набор о = (аг, ..., а„) такой, что 1(Н) = 1. Заменим в 1 переменную х, на х, если сп = 1, и на у, если л, = О. Тогда получим функцию д(х, у). Ясно, что д(х, у) б (ху, х Ж у) и что х б [д(х, у)].
1.19. Предположим, что Рг = Кг С Кг С... С К,, где К, непустые попарно непересекаюгциеся замкнутые классы. Тогда существует г такое, что х ] у б Л;. Но тогда К, = Рг в противоречии с тем, что в ) 1. 1.21. Утверждение вытекает из 1.18 и из того, что система, содержащая функцию х, не может быть расширена до базиса. 1.22. Указание.
Провести индукцию по числу вхождений связки — « в формулу, реализующую функцию 7" б [т — «у]. 1.23. Указание. Использовать задачу 1.22. 2.1. В задачах Ц, 3), 4), 8), 10) функция 7" самодвойственна. В задачах 2), 5) — 7), 9) функция 1" на является самодвойственной. 2.2. В задачах Ц, 3), 5) 8) 7 б В. В задачах 2), 4), 9), 10) 7" 7 В. 2.3.
Ц (1100). 4) (0110100Ц. 8) (1001000011110110). 2.4. 1) 7(х,х,х) = 7(х,х.,х) = 1. 2) ](У,х,х) = 1. 2.6. Куб В" разбивается на 2" ' непересекающихся пар противоположных вершин. В каждой такой паре самодвойственная функция 1'(х") обращается в 1 ровно один ра.з. Контрпримером к обратному утворждению является функция х г Ю хе 2.8. Ц, 3) г (х") б В при нечетных п. 2), 4), 5) ~(х") ф В при всех п ~ 3, Дхз) б В.
6) г(х") «с В при всех п = Зй. 2.10. Необходимость. Пусть « = х«7« Н хгув. Тогда 7' = (х«1« Н хгув)* = (хг Н (г«)') вг (хг Н (го)*) = = х«(гв)" Н хг(Л')" Н ((в)" (~г')' = хг(г«в)* Н хг(1г')*. 335 Гл. П. Замкпутпые классы и полнота В силу того, что т' б Я, имеем ) = ), и, следовательно, хт(уо) ттуйт(Л) = хтут ттутуоЦ Полагая х~ = 1, а затем х~ = О, получаем отсюда, что (уо)* = ут' и (т"')" = ~~. достаточность. Пусть ()т)* = тоЦ Отсюда вытекает., что = ((Л ) ) = (Уо),и, следовательно, 7 = х1 ус 'т Этус = хт(уо ) р бт ( ут )* = (хт утт тт Эт тот)" — т* 2.11. Верно. Вытекает из задачи 2.10.
2.13. 1 является супорпозицией самодвойственных фунхций ш(х ), ут и ут. 2.14. Пусть у ф Я. Требуется доказать, что [(1) О Я = Рт. Имеем (х, х) С Я. Из леммы о несамодвойственной функции вытекает тогда, что (1, О) С [(х, х, 1)). Известно, что [х, ху, х Ч тт) = Рт. Отсюда следует, что [О, 1, х 10 у От э, т(хп у, х)) = Рт, ибо Э = х тЭ 1 <Э О, ху = тп(х, у, О), х тту = т(х, у, Ц.
Имеем Рг С [О, 1, т От у Ю э, тп(хук)) С [(х, х, тт) О Я) = [(тт) О Я). 2.15. Верно для п = 1, 3 и не верно для остальных натуральных п. 2.16. Ц Из условий этой задачи и из задачи 2.10 следует, что уо = ут'. Но тогда т не зависит сушественно от хп 2) Утверждение остается верным. 2.18. Ц 11етрудно получить все функции т б Я, зависящие не балов чем от трех переменных (см, задачу 2.9). Если для некоторого и все самодвойственные функции 1(х" ) получены, то с помощью представления из задачи '2.17 получим любую функцию Д(Э") из Я. 2.19. В задачах Ц, 3), 5) 7), 10) множества М являются самодвойственными. В задачах 2), 4), 8), 9) множества М не являются самодвойственными. 3.1.
Ц, 4), 7), 10) У' ф Ь. 2), 3), 5), 6), 8), 9) 7' б А. 3.2. Ц, 3) — 5)., 7) — 10) т" б Ь. 2), 6) 1 в Ь. 3.3. Ц Имеем ( = ахт Э бхт ~Э с, )'(00) = с = 1, )'(ОЦ = 6 Ю с = О, т'(1Ц = а От б 8 с = 1. Отсюда т" = хт тЭ хз 9 1, оу = (100Ц. 2) 7 = хо. 3), 4) У = хт Э хз <В хз щ 1. 5) ~ = хз тЭ 1. 6) т = х~ ~Э хт. 9) т = х~ бт хз бт хл От 1. 10) 7 = х~ тЭ хз От хт ОЭ 1. 3.4. Ц ((х, .у, у) = ((х, у., Ц = ху. 2) 7(х, у, у) = ху. 3) ((хб у, 0) = х у.
4) 7(х, 1, у) = ху. б) ~(у, О, 1, х) = ху. 6) 7(у,х,у,у)=ху. 1Ц((х,х,х,у)=ху. 12) 7'(х,1,у, Ц=ху. 3.5. Ц, 4), 7), 9) Нельзя, так как [1ту[ < 2. 2) ху = Дх, у, Ц. 3), 8), 1Ц Нельзя, так как т" б А. 5), 6) Нельзя. Указание. Подстановка констант и любое отождествление переменных приводит к уменьшению числа нулей. 3.6. Ц Пусть от, ..., о„т -- произвольный набор значений переменных хт, ..., х т.
Тогда 1(от, ..., оо т, х ) = х„Ю Зт(от, ..., о„т). Отсюда ясно, что т" (от, ..., о„т, О) ф 1"(от, ..., о„т, Ц. 336 Ответы, указания, решения 2) Представим функцию в виде х„6(х" ) Ф д(х" ). Так как У существенно зависит от х„, то 6 х О. Предположим, что 6 х 1. Тогда существует набор а = (оы ..., а з) такой, что 6(а) = О. Но тогда З" (оы..., а 0) = Длы ..., о„ы Ц = д(Н), что противоречит условию. Таким образом, 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 получаем константу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
