Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике (1048833), страница 13
Текст из файла (страница 13)
Воспользовавшись формулой (10),получаем У(х ') = Х21о ® хгЛ = 3о ~ хг Уо ® Л ) = — Р(0 Х2 ° ° х +г) агх!(Р(0 Х2 ° ° х +1) чгр(1; Х2 ° ° х ег))— =ДО.Кой)32 К1Ю Ю)32--г Кг--гйхг(РОЮ)32-) Ко9 ег (е31 чг 132 е1) ' Кг чг ° ° ег Фг — 1 9 )32 +' — 1) ' К2 — 1) 330 'КО 'ХР1 'Кг ~ 'ХР2 — 1 'Кг' — 1 Ю(РО чг(32 ) 'К2 пг 9 Р1 бз 132 3-1) ' К2 -,'-1 9 « ° лп ()32 — 1 9 132 л~ — 1) ' К2'" л> — 1~ где конъюнкция К рассматривается над множеством (хы хг,... ...,х ег) и при у = О, 1, ..., 2 — 1 совпадает с К, а при 3 = 2"', 2'и + 1...., 2'"ег — 1 она Равна хг . К г»..
Таким обРазом, доказано, что ау = Т(3Р). Утверждение обосновано полностью. Используя доказанное утверждение, можно описать алгоритм построения вектора )3Р коэффициентов полинома Р(х "), реализующего функцию 3(х"), имеющую вектор значений ар 2" 11усть ау =(ао~ аы аг~ аз~ ° ~ агы агав-ы - ~ а2" — 2~ а2" — г) 1- биваем вектор ау~ на двумерные наГюры: 70 = (ао, аг), 72 = (аг, аз), Ъ (а2е, а2гл1), ..., Уг — 1 1 — (а2 2, а2 1). К каждому из них применяем операцию Т; Т(30) = (ао, ао пг аг), Т(Ъ) (а2 а2 9 аз)) ..., ТЬ) = (а2п а22 пг аг~~-1)) ° ~ Т(32" — ' — 1) — (а2'" — 2; а2 — 2 чг а2" — 1) ° Используя построенные наборы, конструируем такие четырехмерные наборы, которые получаются в результате применения операции Т к 56 Гл, 1.
Способы задания и еввйапва функиий алеебрь1 логики четырехмерным наборам, выделяемым из вектора Нг: Т(сто, о1, сгг сгз) = Т( уо у1) = (Т( уо) Т( уо) 9 Т( ~1)), Т(о41 1-14241 1141-1-2; 6141-1-3) = Т(у21~ 'у214-1) = (Т(у21) ~ Т(621) 9 Т(у214-1))~ Т(ог е и иг -з, ог--г, иг 1) = Т('уг-- 2, уг.— 1) = = (Т( ~2 — ~ 2)Т(ув--~ 2) 9 Т( уг -2 1)). Затем от четырехмерных наборов переходим (аналогичным образом) к восьмимерным и т.
д., пока не построим 2п-мерный набор. Он и будет искомым вектором коэффициентов полинома Р(х"). Замечание. Здесь 2'"-мерный вектор изображается многими способами: мы «расщепляем» его на «последовательные» двумерные, четырехмерные, восьмимерные и т.д. наборы, Например, для вектора (сво, аы ог; сгз, ил: сгз, ов, о7) применяются такие записи: ((1.10, 111), (Ог, СЗЗ), (О4: Оз) (Ов О7)) ((1.10., О1,. 112, Сгз), (СЛ4, ОЗ, С16, оу)). Сумма Н 61 13 наборов (векторов) одинаковой длины понимается нами обычным образом: это покомпонентная сумма по модулю 2, т.е. 649,3 = (6719(31, ..., оп 913„), если Н = (оз, ..., сг„) и 13 = ((31, ., 73 ).
3. Меп1од, бопируя17дийвж на преобразовании формул над лвнохвестгь вол связок ( де, — ). Строят некоторую формулу Ф над множеством связок ( вс, — ), реализующую заданную функцию у. Затем заменяют всюду подформулы вида А на А 9 1, раскрывают скобки, 1юльзуясь дистрибутивным законом А (В 9 С) = А В 9 А. С, и применяют эквивалентности А А = А, А . 1 = А, А 61 А = 0 и А 9 0 = А. П р и м е р 11. Методом неопределенных коэффициентов построить полипом Жеголкина для функции 3(х, у) = х Ч у. Решение. Р(х,у) = (уо 9131 т 9Г32 у 9132 ху.
Выписываем систему уравнений для коэффициентов 13о, 121, 132, 17з.' У(0, 0) = О =)3о 9131 09Г32 09дз О. у(0,1) = 1=РО9|31 09,32 09,3з О, у(1, 0) = 1 = (36 9 )31 1 9 132 . 0 9 )3з . О; Г(1, 1) = 1=1309Д 09132 19133 1. Решая эту систему, получаем 73о — — О, 731 = 132 — — 732 — — 1. Следовательно, хну = ху9х9 у. Пример 12. Преобразуя вектор значений функции, построить полипом жегалкина для функции Дхз) = х1хг у хзхзч хгхз. Решение.
Имеем Ну = (00010111). Разбиваем этот вектор на «последовательные»двумерные наборы: уо = (О, 0), у1 = (О, 1),. 'уг = = (О, 1), уз = (1, 1). Затем последовательно применяем операцию Т к соответствующим векторам: Т( уо) = (О, 0 9 0) = (О, 0), Т( уг') = (О, 0 9 1) = (О, 1), у Я. Специальные предетавлепцн булевых функций 57 л (7о, 7з) = (л (7о), л (7о) Ю л (7з)) = = ((О, 0), (О,. 0) Ю (О, 1)) = (О, О., О, 1), л (Уз~ Уз) (Х(Уз), л (Уз) ЮТ(73)) = = ((О, 1), (О, Ц Ю (1, 0)) = (О, 1, 1, 1); Т(оу) = Т(7о, 7ы 7з; 7з) = (Т(7о, 7з), Т(7о, 71) 9 Т(7з, 7з)) = = ((О, О, О, 1), (О, О, О, 1) 9 (О, 1, 1, 1)) = (О, О, О, 1, О, 1, 1, 0) = Вр. Таким образом, Р(х )=О.Ко90 К190.Кз91 Кз90 К491.КзЮ Ю 1 .
Кв Ю 0 Ку — — хзхз Ю х1хз Ю х1хз. Пример 13. Представив функцию у(х, у) = х — у у формулой над множеством связок (4е, — ), преобразовать затем полученную формулу в полипом Жегалкина. Решение. Имеем х-+у= хНу=х у=х у=т.(у91)91= =хуЮх91. Пример 14. На скольких наборах из В" обращается в 1 полипом Р(х") = НУ хх, (и > 2)7 з<~<адп Решение.
бранный полипом можно записать в следующем виде: Р(х )=хзхзЮ(хзЮхз) хзЮ 9(хзЮ . Юх — з) х — 19 9(х, Ю...Юхп,).х„. В силу симметричности вхождения в него всех переменных достаточно рассмотреть наборы вида (1, ..., 1, О....., 0), 0 < 1 < и (при 1 = 0 это будет нулевой набор 0 = (О, .О, ..., 0)). Если х,лз =... ... = х„ = О, то Р(хы ..., х„ О, ..., 0) = хз хз Ю (хз Ю хз) 3ехз 9 ... ...
Ю (хз Ю... Ю х; з) х,; здесь число произведений вида хнх~ равно, очевидно, ( ) (2 < 1 < и), а при 1 = 1 и 1 = 0 таких произведений нет. Значит, Р(1, ..., 1, О,..., 0) равно 0 или 1 в зависимости от ю 'Уз того, четно или нечетно число (2) (при з, = 1 и 1 = 0 значение полинома на соответствующем наборе есть 0). Выясним теперь, прн каких 1 число ( ) является нечетным. Если 1 = 4й или 1 = 4й+ 1 (й > 1), то (2) равно 2й. (4й — 1) или (4й+ 1) . 2й соответственно, а если г = 4й + 2 или 1 = 4й + 3 (й > 0), то ( ' ) равно (2й + 1) (4й + 1) или (4й+ 3)(2й+ 1). Следовательно, число ( ) является нечетным только тогда, когда 1 = 2, 3, 6, 7, ..., 4й+ 2, 4й -~-3, ... Учитывал этот факт, заключаем, что число наборов, на которых полипом Р(х") обращается в 1, равно О,— зП4' Ол — з~Ул; Е (Я+2) ' Ел (4~':3) 58 Гл. 1.
Способы задания и сводыпва функций алгебрь1 логики В частности, если п = 2, то существует только один такой набор ( в этом случае вторая сумма вырождается в нуль: ~ ( й 3) = 0), 1 О ~М4- а если п = 3, то таких наборов четыре (Е(а+2) Е(а -3) (2) (3) ) 2.22. Методом неопределенных коэффициентов найти полиномы Жегалкина для следующих функций: Ц 1(х ) = х1 ~ хг, 2) )(х~) = (0100); 3) )(х~) = х1 хг Чхз); 4) 1" (хе) = х1 — 4 (хг 4 хз)' 5) Дхз) = (0110100Ц' 6) Дх з) (10001110). 7) ((х з) (0000011Ц 8) Дхз) = (01100110) 9) 7(хл) = (100000000000000Ц 10) У(х') = (0000100010010000). 2.23. Преобразуя вектор значений функции 7'(хо), построить по- дином поганкина для этой функпии, если; Ц 7"(хг) = (1000): 2) 7"(хг) = (0010); 3) У(хз) (01101110).
4) У(хе) (0111001Ц 5) У(хз) (10101110); 6) Х(х,з) (10000100) 7) Дх4) = (000001000110011Ц; 8) Дхл) = (1010101010110110); О) У(х,л) = (0100000000010ООЦ; 10) У(хл) = (ООООООО100010ООЦ. 2.24. Представив функцию Д(хп) формулой над множеством свя- зок (8с, — ), преобразовать затем полученную формулу в полипом Жегадкина функции Д(хи) (испопьзуя эквивалентности А = А ~Э 1, А.(ВЮС)=А ВбзА С, А А=А, А 1=А, АбзА=О и АЮ 450 = А): Ц 1(х ) =:с1 -+ (хг 4 Хгхг);.
2) 1(х ) = х1 (хг хгхг); 3) 1(х ) = (х1 4 хг) ~(хг ф хз); 4) 7(х ) = (х1 Ь'хг) (хг ~хз); с) е( 3) . ) (( . ~ х ) ~ х 6) Дх ) = (х1 -4 (хг -4 хз)) .((х1 -4 хг) 4 хз), 7) гл(Х ) = (Х1 Ю Хг)'в'(Хг ). ХЗ); 8) 1(х~) = (х1 -о хг) †(хз †х1хл); О) 1(х ) — х1 " (тг 4 ((хз схг) с хл))~ 10) 1 (х ) = х1 Ч хго хз) х4 о хгхгхз.
2.25. Показать, что х; является существенной переменной функ- ции дхо') тогда и только тогда, когда х; явно входит в полипом Жегалкина этой функции. 2.26. Найти число: Ц монотонных элементарных конъюнкций ранга т над множест- вом переменных Х" = (х1, хг, ..., х„) (О ( г ~ (и); 2) полиномов Жегалкина степени г над множеством перемен- ныхХп (0(г(п); у й Специалвиые предегпавлеапн булевых бгупкццц 59 3) полиномов Жегалкина степени г над множеством Х", обращающихся в 1 на наборе 1 (О < и < п); 4) полиномов Жсгадкина длины 1е над множеством Х", обращающихся в О на наборах О и 1 (О < й < 2и); 5) попиномов Жегалкина степени г над множеством Х', удовлетворяющих условию; в попиноме не могут содержаться одновременно (в качестве слагаемых) конъюнкции одинакового ранга (О < г < и).
2.27. Выяснить, на скольких наборах из В" обращается в 1 полипом Р(хи): 1) Р(х ) =хг'хзчгх1'хзЮ...Юхг'хи — <г)хгхг г'=-2 и 2) Р(х ) — хг ' хз чг а 3 ги ° гх хи — хгхз ги (х) 3) Р(х ) =юг 'хач хг 'хзгихлге ° .гехи = хгхз гхг хгхз пг сгг хгг гг, ~ )4; и г'=4 4) Р(хи) = хгхгхз 6~ гтг х, и. > 4; г=л б) Р(хи) =х, ...х, Ехя„..,х„, 1 < й < п; и б) Р(хи) = ® хг... хе бг 1, и > 1; г=1 7) Р(хи) = ()) хг... х, гхг+г... хиг п > 2; 8)Р(хи)=хгОЗ 9 т,хч п>2; 1<г<1<и и 9) Р(х') = (Э х,х, ~Э (() х„п ) 2.
1<г<1<и г=у 2.28. Найти функцию 7"(хи), у которой длина попинома Жегапкина в 2и раз превосходит длину ее совершенной д. н, ф. (и > 1). 2.29. Локазатьг что функция Дхи), реализуемая попиномом Жегалкина степени й > О, принимает каждое из значений О и 1 не менее чем на 2" Я наборах из В" (т.е. ~Лгу( > 2" " и ~йу~ > 2" ~). 2.30. Показать, что дпя всякого 1 (О < 1 < 2и) существует попином Жегалкина Р(хи), обращающийся в 1 ровно на 1 наборах из В" и имеющий длину, не превосходящую и. 2.31.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
