Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 67
Текст из файла (страница 67)
2 2.17. 1) 2 ', если п нечетное, и 2 (5'гг!) — 1, если п четное. 2) 22 " ' — 1. 3) 22 ' — 1. 4) 2 — 1, гле А = („) + ( ) + ... + ( ~ ) = 2" + — (,г ), если п четное, и Ь = ( ) + ( „') -!-... + ((„ 1)( ) = 2" ', если п нечетное. 5), 6) 22 ' — 1. 2.18. 1) 2" — п — 1. 2) п -~ 1. 3), 5) (2' и -~- ( — 1)")/3.
4) 2 — 1. 6) 2о '+2. 7) 2 ' — 1, если и нечетное, и 2" ' 4-1, если и четное. 8) 2" ', если п нечетное, и 2" " -~- 1, если п нечетное. 332 Отпветы, уназаннв, решеннв 2.10. Ц 2в . к+2"'.1 — lс.1. 2) 1с 1. 3) (2в — 1) /с+ (2ш — й) 1. 4) (2" — к) 2" + к 1.
2 20. Ц 1з — 1г, где 1г и )г длины совершенных д. н. ф. функций 1 Ч д и 7 д соответственно. 2) 2""' — 1з — 1г, где П и 1г — длины совершенных д.н.ф, функпий ~(х") г д(хТ"') и д(хТ") -з ДхТ") соответственно. 2.21. Ц Всего имеется 10 булевых функций., зависяших от переменных хз и хг, причем от каждой из них существенным образом. 2) Функции хг Ю хг и хг хг имеют минимальные д. н. ф. сложности 4. 2.22. Ц хгхг бз 1.
3) хгхгхз Ю хгхз бз хг. 6) хгха Ф хатха Ю хгхз Щ хг Ф хз 63 1. 10) хгхгхзхс ср хгхзхз 9 хгхз Ю хгхс ср хгхз Ю хгхз Ю хг Ю хг. 2.23. Ц хгхг ер х~ Ю хе ЕО1. 4) хзхгхз Ю х1хз Ф хгхз ерха Фхз. 7) хгхгхс Ю хгхзхс ОЗ хгхз Ю хзхс Ю хгхо 2.24. Ц 11хч ) = хз Ч хг Ч азха = хг Ч хг = хзхг = хзхг Ю 1. 3) Д~ач ) = хг Ч хг хг Ч хз = хз *г хз = (хз ЕО Ц(хг Ю 1Цхз ОЗ Ц Ю 1 = = хгхгхз Ог хгхг Эх~хе 63 х хз Ю хг 9 хг Ю хз. 9) г 1хч ) = х1 Ч хе Ч хг Ч хзхз = хг Ч хг Ч хс = хзхгхс = = (х1 Оз 1)хг1хс Ф Ц Оз 1 = хзхгхс бз хзхг ~3 хгхс бзхг бг 1.
2.25. достаточность. Пусть х, содержится в полиноме веселкина Р1х ) фУнкции Дх"). ПРедставим полинам Р1х~) в виде х,Рз(хз, ... .; х -з, х -н, ..., х„) Ю Рг(хз, ..., х, з, х,~.п ..., х„). Здесь Рг Х: О, так как иначе переменная х, не входила бы явно в РЕх"). Возьмем набор а = = (оы ..., о, г, о,тз....., о ) такой, что Рз(о) = 1. Тогда имеем 1(оы ..., о, ы О, о, з, ..., о„) = О.
Рз(о) Е РЯо) = Рг(о), 1(оз, ..., н, ы 1, сг вы ..., ов) = 1 Рз(о) Ю Рг(о) = 1-т Рг1ог) Р Рг(о). Значит, х, существенная переменная функции 1)х"). 2.26. Ц („). 2)1при т=О и 2 )2" — 1) при т)1,где е( (,) 3) 1 при т = 0 и ) 2 " — 1) 2 при т ) 1, где т() з е г '=(".)'©" '(.-" ) е та з 4) ~ 1 ), где ш = 2" — 1 и 1с четное. При й нечетном таких полиномов нет. 5)1при т=О, ( ) П(1+(.)) при т))1. 2.27. Ц 2" г. 2)-4) 2" '. 5) 2 +2" в — 2. 6) 12"~'+1 — Ц"Ц3.
7) п -~ 1,. если п нечетное, и и, если п четное. 333 Гл. П. Замкнуптые классы и полнота 8)1при п=2, 2при тт=3 и Е( 4Я ) 'Е(4х-~-2)+ .Е (4т-~-3) при и > 4, где р = [(тт — Ц/4], д = [(и — 3)/4] и т = [(и — 4) /4]. ) Е(41 2)+Е(41-~-1) ' ' "= [ ~ " 4= [ 1' ь=о ~=е 2.28.хтхг...х„. 2.29. Применить индукцию по тт. 2.30. Лля и = 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. Ц 7(х,х,х) = 7(х,х.,х) = 1. 2) ](У,х,х) = 1. 2.6. Куб В" разбивается на 2" ' непересекающихся пар противоположных вершин. В каждой такой паре самодвойственная функция 1'(х") обращается в 1 ровно один ра.з. Контрпримером к обратному утворждению является функция х г Ю хе 2.8. Ц, 3) г (х") б В при нечетных п.
2), 4), 5) ~(х") ф В при всех п ~ 3, Дхз) б В. 6) г(х") «с В при всех п = Зй. 2.10. Необходимость. Пусть 1 = х«7« Н хгув. Тогда 7' = (х«1« Н хгув)* = (хг Н (г«)') вг (хг Н (го)*) = = х«(гв)" Н хг(Л')" Н ((в)" (~г')' = хг(г«в)* Н хг(1г')*. 335 Гл. П. Замкнутпыс классы и полнота В силу того, что т' б Я, имеем ) = ), и, следовательно, хт(уо) ттуйт(Л) = хтут ттутуоЦ Полагая х~ = 1, а затем х~ = О, получаем отсюда, что (уо)* = ут' и (т"')" = ~~. достаточность.
Пусть ()т)* = тоЦ Отсюда вытекает., что = ((Л ) ) = (Уо),и, следовательно, 7 = х1 ус 'т Этус = хт(уо ) р бт ( ут )* = (хт утт тт Эт тот)" — т* 2.11. Верно. Вытекает из задачи 2.10. 2.13. 1 является супорпозицией самодвойственных фунхций ш(х ), ут и ут. 2.14. Пусть у ф Я. Требуется доказать, что [(1) О Я = Рт.
Имеем (х, х) С Я. Из леммы о несамодвойственной функции вытекает тогда, что (1, О) С [(х, х, т")). Известно, что [х, ху, х т117) = Рт. Отсюда следует, что [О, 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) = Длы ..., о„ы Ц = д(Н), что противоречит условию.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
