Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 67
Текст из файла (страница 67)
1.39. 1), 2), 5), 7)-10) Можно. 3), 4), 6) Нельзя. 1.40. 2) Лостаточно рассмотреть одну из функций — ди(х1, хг, хз) = = хгхг Ч хгхз »дхгхз или х16»хг чу аз. 1.41. Если при отождествлении некоторой пары переменных хд и хг (1 < у < й < и) получается функция, тождественно равная О, то д"(ха) должна обрадцаться в 0 на всяхом наборе вида (о», ..., о 1, е, 41,«1,... ..., ог — 1, и, оь«1,..., о„). Но число таких наборов 2" . Значит, выполнялось бы неравенство ~»Уд ~ ( 2" — 2" ' = 2" ', что противоречит условию задачи.
1.42. 2) Тот факт,что 49 нельзя заменить на й и 47, обосновывается, например, с использованием функций 7(х") = хз...х (и ) 3). 1.46. Наборы Д~ и 161+1 соседние при всяком 1' = О, 1, ..., й — 1. Пустыг номер той компоненты, в которой наборы Н и Н „.1 отличаются друг от друга. Если 1(»з ) ~ )(19».1), то хц существенная переменная функции г(хлн). Покажем, что числа 1о, 11, ..., 11, 1 (номера соответствующих компонент) все разные. Прелположим противное, т.е. что для некотоРых Р и 9 (О < Р < У ( й — 1) выполнЯетсЯ Равенство др — — гд.
Тогда имеем р(Др, 484) = р(Д~«1, 4»д) — 1. Используя это соотношение и «свойство треугольника» для расстаяния Хэмминга, пОлучасм й = р9о, (11) < рдо, 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) г Ех ) — хезхгхз ОЗ х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) 12в — 1) lс+12ш — й) 1. 4) 12" — к) 2" + к 1. 2 20. Ц 1з — 1г, где 1г и )г длины совершенных д. н. ф. функций 1 Ч д и 7 д соответственно. 2) 2""' — 1з — 1г, где П и 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хс Ф Ц Оз 1 = хзхгхс бз хзхг ~3 хгхс бзхг бг 1.
2.25. достаточность. Пусть х, содержится в полиноме веселкина Р1х ) функции Дх"). Представим полинам Р1х~) в виде х,Рз1хз, ... .; х -з, х -н, ..., х„) Ю Рг1хз, ..., х, з, х,~.п ..., х„). Здесь Рг Х: О, так как иначе переменная х, не входила бы явно в РЕх"). Возьмем набор а = = 1оы ..., о, г, о,тз....., о ) такой, что Рз1о) = 1. Тогда имеем 11оы ..., о, ы О, о, з, ..., о„) = О.
Рз1о) Е РЯо) = Рг1о), 11оз, ..., н, ы 1, сг е ы ..., ов) = 1 Рз 1о) Ю Рг 1о) = 1 -т Рг1ог) Р Рг 1о). Значит, х, существенная переменная функции 1)х"). 2.26. Ц („). 2)1при т=О и 2 (2" — 1) при т)1,где е( 1,) '=(".)'(")' '(.-и ) 3)1при т=О и (2" — 1) 2 при т)1,где т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) Имеем к=хи«хВОх, хНу=х — «у, ху=х — «у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
