Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 13
Текст из файла (страница 13)
Опишем три метода построения полиномов Жегалкина. Сначала введем специальную нумерацинг монотонных элемвнтар- НЫХ КОНЪЮНКЦИЙ (Э. К.) НаД МНОжсотВОМ ПЕРЕМСННЫХ Хи = (Х1г Хг,... ..., х„). Монотонной э.к. К сопоставляем вектор о(К) = (сг1, ог,... ..., ои) из В"', в котором о, = 1 тогда и только тогда, когда х, входит п в К. Номером э, к. К будем называть число р(д(К)) = 2 и; 2" г=1 Константа 1 в этой нумерации будет иметь номер О. 1.
Метод неопределенных коэффициентов. Пусть Р(х") - . искомый полинам Жегалкина (реализующий заданную функцию 1(хгг)). Запишем его в виде Р(х") =1эв 19А К1 Гй132 Кг йэ иг122--1 Кг- — 1г (16) где К, --. элементарная конъюнкция с номером у ( у = 1г 2, .... 2" — Ц. Псктор Вр = (Во, А, г А 1) будем в дальнейшем называть вектором коэффициентов полинома Р(хи). Нам нужно найти неизвестные коэффициенты,Зо, А, ..., )12- Поступаем так.
Для каждого а й В" составляем уравнение Р(о) = = Д(сг), где Р(И) --- выражение, получающееся из формулы (16) при х = И, Это дает систему из 2" уравнений с 2" неизвестными; она имеет единственное решение. Решив систему, находим коэффициенты полинома Р(хи). 2. Метод, б зируюгцийся на преобразовании вектора значений функции. Пад векторами из Вг определяется (индукцией по и) операция Т.
а) Если и = 1 и гй = (оо,м1), то Т(И) = (мо, оо 61о1). б) Предположим, что операция Т уже определена для каждого 2" +' вектора д из Вг, и рассмотрим произвольный вектор а из В Пусть гй = (ьго, ьг1, ..., ьгг 1, ув, 11, ..., 12 1) и т(Я, А, Вг" -1) = (бо, йгг . г бг 1), Т(70 ~1 12 — 1) (зо. в1 .. вг — 1) 54 Гл, 1. Способы задание и сввйапва 41упкиий алгебры логики (б, и е по индуктивному предположению известны).
Полагаем Т(о) = (до, ды ..., бг- ч; до 9 го, бз 9 ем . дг- г 9ег- г). Мы сейчас покажем, что вектор ааг значений функции»(хп) Х связан с вектором 13р коэффициентов полинома Р(х"), реализующего функцию»(хп), следующим образом: Др = Т(а») и а» = Т(1)р). Сделаем это с помощью индукции по п. Базис индукции: и = 1. Тогда а» = (ао, аг) и в силу формулы (10) имеем»'(х1) = гц»"(0) 9 хг»'(1) = ао Уо 9 а1 хг = =ао.(хг91)9а1 х1=ао 19(оо9а1).хы т.е. А =(ао,ао9 9аг) = Т(а»). Обратно, если 1»р = (11о, 1эд), то Р(хг) = 13о 19 9 1эг .
хы а следовательно, »(0) = Р(0) = 1эо и»" (1) = Р(1) =,Зо 9 Д, т, е, а» = Т()др). Базис индукции обоснован. Индуктивный шаг. Предположим, что утверждение верно для и = т > 1, и установим его справедливость при п = т+ 1. Пусть вектором значений функции»"(хйпеы) будет а» = (ао,аы ... ..., аг- ы аг-, аг-лз» ..., аг-л~ г). Тогда вектор значений хг-компоненты функции»(х~+г) есть а»1 = (ао, аы ..., аг- г), а вектор значений хыкомпоненты есть ар = (аг, аг-эы ..., аг»л~ 1).
1 (Здесь обе компоненты рассматриваются как функции, зависящие от переменных хг, ..., хв,. ы и наборы значений этих переменных считаются стандартно упорядоченными при естественном, по возрастанию номеров индексов, упорядочении самих переменных.) Используя индуктивное предположение, можем написать Т(о», ) = Т((ао, аы ..., .аг- г)) = (бо, бы ..., дг- — г), Т(а»1 ) = Т((аг, аг *+1,..., ог л1 — 1)) = (ео, еы ..., ег 1), 1 где (бо, бы ..., дг- г) — вектор коэффициентов полинома Ро(хг, ... ..., х~, 1), реализуюгцего хыкомпоненту Д, а (ео, гы ..., ег- 1) вектор коэффициентов полинома Р,(хг, ..., х,„ъг), реализующего хыкомпоненту»'г . Применяя формулу (10) и расписывая полиномы Ро и Р, в виде (16), имеем »е(х™+1) = х1»о 9 хг»1 — — х1(бо Ко 9 дг .
Кг 9... 9 дг г Кг — г) 9 9х„(ео Ко 9ег Кг 9...9ег-* г Кг- — г) = ба Ко 9бг Кг 9 . 9 бг --г Кг -1 9 хг((бо 9 го) Ло 9 (бг 9 ег) Кз 9... 9 (бг" — г 9 ег- — г) Лг- — г), где К вЂ” конъюнкция с номером» (» = О, 1, ..., 2 — 1) над множеством переменных (хг, ..., х,„лг ). Если конъюнкцию К, рассматривать над множеством (хы хг,..., х тг), то ее номер не изменится, так как в соответствующем ей новом наборе первая координата нулевая. В то же время номер конъюнкции хгЛ равен 2'и+», »' = О, 1,... ..., 2п' — 1. Отсюда следует, что вектор коэффициентов полино- г Я.
Специальиые предспгавлеипн булевых фракций 55 ма Р(х"'+'), реализующего функцию 1(хп'+г), имеет вид )3р = (бо, бы ..., бг ы до 61ео, бг югы ..., дг г бзег 2), т.е. совпадает с тем, который указан в определении операции Т. Итак, установлено, что (3р = Т(ау). Докажем теперь обратное утверждение, т.е, что ау = Т((3Р). Пусть РР = РО, 33ы..., )32 1, 332, 132 . 1, ..., )32 ь 1).
Тогда )3Р, = (130, 33ы ., 132- — 2) и )3Р~ = ()32, )32 е-ы 132"*'-1 — 2) где Ро и Рг - полиномы, реализующие соответственно хюкомпоненту 302 и хг-компоненту )г' функции 3(х~+г). Очевидно, что г (О, Хг, ..., Хпльг) = Р(0, Х2, ..., Хтпз-' )— — )30 ' КО 6~ е31 ' К1 чг ° ° ° бз е32 — 1 ' К2' — 1 ~ 3(1,х~,...,х +2)=Р(1,хг,...,х, +1)= =132 'Коб~дг' 01'К1~Э...Ю)32'"'1 — 1'К2 — 1 где К вЂ” конъюнкция с номером 3 (3 = О, 1, ..., 2 — 1) над множеством переменных (хг, ..., х, ег).
Воспользовавшись формулой (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 Гл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
