Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 66
Текст из файла (страница 66)
Если при отождествлении некоторой пары переменных хг и хг (1 < у < й < и) получается функция, тождественно равная О, то 1"(ха) должна обрадцаться в 0 на всяхом наборе вида (о», ..., о 1, е, 41,«1,... ..., од — 1, и, оьрг,..., о„). Но число таких наборов 2" . Значит, выполнялось бы неравенство ~гд'7 ~ ( 2" — 2" ' = 2" ', что противоречит условию задачи. 1.42. 2) Тот факт,что 49 нельзя заменить на й и 47, обосновывается, например, с использованием функций 7(х") = хз...х (и ) 3).
1.46. Наборы Д~ и 191+1 соседние при всяком 1' = О, 1, ..., й — 1. Пустыг номер той компоненты, в которой наборы Н и Н „.1 отличаются друг от друга. Если 1(»з ) ~ )(19».1), то хц существенная переменная функции г(злн). Покажем, что числа 1о, 11, ..., 11, 1 (номера соответствующих компонент) все разные. Прелположим противное, т.е. что для некотоРых Р и 9 (О < Р < У ( й — 1) выполнЯетсЯ Равенство гр — — гд. Тогда имеем р(1)р, 484) = р(Д~«1, 4»д) — 1. Используя это соотношение и «свойство треугольника» для расстаяния Хэмминга, пОлучасм й = РУо, дг ) < РЯо, 3р) ц- РУр, дд) + РЦЭР«, дг) < р — 1 1 — 1 < ) р(»81, д1« ) + р()Зр»-1, А) — 1»-') .
р(ТЗЬ д1- ) < »=О 1=4 330 Ответы, указвнпя, решенпя < р + у р1)зп !дг~.з) — 1 + й — д = р + (д — р — 1) — 1 + й — д = й — 2, г =.гее Это противоречие показывает, что наше предположение ложно. Следовательно, все номера го, гы ..., гь г разные, а поэтому число существенных переменных у функции 7!х") не меньше числа перемен ее значений на рассматриваемой цепи, т.е. нс меньше пь 2.1. 3) (10001000). 4) 10111011Ц.
7) (1111111111001100). 10) !1111111100000000). 2 2. 1) г !хо) = Уз (хг -з хА Н х ~ хо! УДУз) = Уг = (11001100). 3) 7(*з) = )ОППООО)! 7г)хчз) = (01ОПО10). 7) г Ех ) — хезхгхз 0З х4) Н хзузеж ); уо (х~) = 10101010110011001). 2.3. 2) хзхгхз Ч хзУгхз Н хзхгхз. 4) хгхгхз Ч хехгУ Ч:сехгхз Ч хзУгхз. 7) УзхгУзх4 Ч УзхгУзх4 Ч хзх хзУ4 Н хсйгхзх4 Ч хзхгхзхо 24. 1) езхз Ч хг)зеУз Ч Уг). 2) зехз Н Уг)зеУз Н хг)зеУз Н хг).
6) серег ч хг ч хз) еехз ч хг ч Уз)еехз и хг ч хз)еехз н хг ч Уз). 8) (Уз ЧУ Н хз Н хс)1Уе Ч Уг Н хз Н Уз)!Уз Ч Уг 'Н Уз Ч х4). 2.5. 2) 7о!ехз, хг) = хз ~ хг = УзУ Ч хо.'сг Ч хзУг. 5) ггз'еехм хг) = зе1101) = Уг Ч хг; 7) уз (хз, хз, х4) = хз — е хз — з хс = = 1хз Ч хз Н х4)1хз Ч хз Ч хз)1Уз Ч хз Н Ув). 9) гсоз (хы хз) = хз хз = УзхзН хзхз.
ги 2.6. 2) Пусть д(хм х, ..., х„) = 1Ех ', х. г, ..., х„"), где х * = У, при о., = 0 и х,* = х, при сг, = 1. Подходящее взаимно однозначное соответствие между подфункциями функций д и 7" задается так: подфункции д,"„'* *,"„"" 1хЗ") сопоставляется подфункция у~во ' '~, 1х"), где шь, = е =т, ' (0<пг(гс; 7=1,...,т). 4) Вытекает из 2) и 3). 2.7. 1) 7(х") = хз Н хг Ч... Н х„. Число разных подфункций равно 2ч -Ь 1. 2), 3) Разных попфункций 2" т~ — 1. 4) При л = 2 число разных подфункций равно 5, а при п > 3 их число 3 2" 5) 3 2" ' + 1. 6) 2о + 1. 7) При и = 3 число разных подфункций 9, а при и.
> 4 их 3 2г" г 4-5. 8) 2" 4- 7 при и > 4; 12 при п = 3. 2.8. При и = 2, используя прямой перебор, легко находим, что таких функций 8. (Это,7о(хз, х ) = О, зз(хз, хг) з— в 1, хз бз хг, хз тг, тз -э хг, хз -в хг, хг з хз и хг з хз.) При и > 3 сначала следует доказать, что функция 71хн) обладает таким свойством: если веса наборов а" и Сз" либо одновременно четные, либо одновременно нечетные, то 1!о") = 7))го). Значит, при п > 3 функция 7(х7') однозначно опродоляется значениями на 1"л. 1 Способы эа!)анин и свойства функций алгебры логики 331 наборах 0 и(1, О, ..., 0). Следовательно, тахих функций 4 (это фо(хо) = О, — ! ра 22(х") = 1, фг(х") = х! бах со...
чг х и фз(х") = х! 62 ха чг .. Ю х Ю 1). 2.10. 4) ф(х ) = х! Ч хгхз хгхг Н хз = (х! Н хгха~ Ч (Уатг Н хз) = = х! Ч хгха Н х! Н х Н хз = т! Ч Уг Н тз. 10) ф(х ) = х! Ч х2(х2хз Н хзх4)х! Ч хзха = хахг(ха Н ха Н хаза)У!хала = хахгхзх4. 2.11. 1) ф(х ) = ((У! Н хг) б!Уах )(х! Хг(У! Н хг)) = = (тах Ю хахг)(х! Хг) = (Х449 тг)(х! Хг) = 0 = = (х! Ч хг)(х! Ч хг)(х! Н хг)(х! Н хг). 3) Дх ) = ха ха Ч хгхз Н х! Н хгхз = х! Н хг Н хз.
б) 1(х ) = (х! Н хг Ч хз Н У4)(х! Н хг Н ха 'Н х4). 2.12. 2) 24(хч ) = хай!ха Ч УЗУгхз Н хахгхзЧ хахгхз Н хахУ2УЗ Ч хахгхз = = хзУгУз Ч хзхгхз Ч хахгхз Ч хахгхз Ч хзхгхз. 5) 1(х ) = х!У! Н хахг Ч хахг Н хахг Ч хахгхз Н хахгхз = = хзхгхз Ч хахгхз Ч хзхгхз Н ха хгхзЧ УзУгУз Ч хайгхзЧ хатгхз. 2 13 1) Дтз) = (х! Ч хг Ч хз)(х! Ч хг Н Уз)(х! Н хзКх! Ч хз) = = (х! Ч х Н хз)(х! Ч хг Н хз)(х! Ч хг Н хз)(х! Ч хг 'Н хз)(х! Ч хг Ч тз). 5) (х! Ч Уг Н хзЦх! Ч Уг Н хз)(х! Н хг Н хзЦх! Ч ха Ч хз) бс бс (У! Н хг Ч хз)(х. Ч хзЧ ха) се (х! ЧУг Чха)(х! ЧУ! Ч хз). 2.14.
3) 24(хз) = (х! Н хгхЯх! Н х! Н хз) = = хахг Н хахз Н хзхгУз Н хгУз = хзх Н хахз Н Угхз = хзхз Н хгхз. б) ф(х ) = (хгхг Н хзхз Н хгхз)(хгхз Н хгУ4 Н хзха) = = хах2хз Ч хзх2Х4 Ч аах2хзл4 Ч хах2хзх4 = хзх2хз Ч хах2ха. 2.15. 2) Дх ) = (х! Ч хг)(хг Ч хг)(х! Ч хз)(хг Н хз) Ч хгхз = = (х! Ч хгЧ хг)(х! Н хг Н хз)(хг Ч хз Н хг)(х! Н хг Ч хз) Й Й (х! Н хз Ч хз)(хг Ч хзЧ хз) = (х! Ч тг Н Уз)(хг НУ!)(х! Н хг Ч хз) = = (х2 Ч хз)(х! Н х2 Н хз). 5) Дх ) = (х! Ч хг)(хг Н хг) Ч хгхз = (х! Н хг)хг Н хгхз = = хг Ч хгхз = (хг Ч хг)(хг Ч хз) = хг Ч Уз.
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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
