С.Н. Селезнёва, А.Б. Дайняк, М.С. Шуплецов - Булевы функции и полиномы (1123636), страница 6
Текст из файла (страница 6)
. , xn }, не равной 1 , и при этом i(1, Pf ) = 1.Доказательство. Докажем критерий четности функций. Пусть Pf = K1 ⊕. . .⊕Kl . Пусть Ki = xi1 ·. . .·xim .Полином P 0 = Pf (x1 , ..., xn ) получается, если заменить каждое слагаемое Ki в Pf на слагаемое(xi1 ⊕ 1) · . . . · (xim ⊕ 1), и затем раскрыть скобки. Таким образом, каждое слагаемое Ki из Pf даетвклад в P 0 в виде всех ЭК, содержащихся в Ki . Отсюда видно, что после упрощения в P 0 останутсяте и только те ЭК, которые содержались в нечетном числе слагаемых полинома Pf (а этому условиюудовлетворяют, во-первых, те Ki , для которых i(K, Pf ) = 0, и во-вторых не содержащиеся в Pf ЭК,для которых i(K, Pf ) = 1 ). Но для того, чтобы функция f (exn ) была четной, необходимо и достаточно,0чтобы P совпадал с Pf . То есть описанному условию должны удовлетворять все слагаемые Pf итолько они.
Это и равносильно тому, что для любой ЭК K над {x1 , . . . , xn } было выполнено равенство i(K, Pf ) = 0 . Доказательство критерия нечетности функций аналогично, и его мы предоставляемчитателю.Докажем, наконец, основную теорему этого параграфа.Теорема 4.3 ([7]). Существует детерминированный алгоритм, распознающий самодвойственностьфункции f по ее полиному Жегалкина Pf за O(l4 ) операций, где l — длина полинома Pf .Доказательство.
Рассмотрим алгоритм, состоящий из двух этапов:√1. Находим l , и ранг r полинома Pf . Если l < 2r , то, √по следствию 4.1, функция f не являетсясамодвойственной, и алгоритм завершается. Если l > 2r , то переходим ко второму этапу.2. На данном этапе мы рассматриваем все ЭК K , содержащиеся в слагаемых полинома f , и проверяем выполнение условий i(K, Pf ) = 0, i(1, Pf ) = 1. По лемме 9, данной проверки нам достаточнодля определения самодвойственности функции f .На первом этапе мы затрачиваем O(l) операций. На втором этапе для каждого из l слагаемых Kiнеобходимо просмотреть не более 2r ЭК, содержащихся в Ki , и для каждой из этих ЭК подсчитать, вкаком числе слагаемых Pf эта конъюнкция содержится.
На это мы затрачиваем всего O(l·2r ·l) = O(l4 )операций. Здесь мы существенно пользуемся неравенством из следствия 4.1.На втором этапе алгоритма теоремы мы фактически организуем полный перебор. Полиномиальность алгоритма обеспечивается только «мизерным» рангом слагаемых, по сравнению с длиной полинома. Можно ли построить алгоритм распознавания самодвойственности, не использующий оценку изследствия 4.1? Ответ на этот вопрос пока не найден.Глава 5Представление булевых функцийполиномами над ZРанее мы уже рассматривали рекурсивную процедуру нахождения коэффициентов полинома Жегалкина булевой функции через столбец значений.
Пусть f — произвольная функция. Обозначим черезc(eγ ) коэффициент в полиноме Жегалкина функции f при слагаемом Kγe , соответствующем набору γe.При этом c(eγ ) можно рассматривать как функцию от того же числа переменных, что и f . Например,Для функции f (x1 , x2 , x3 ) = x1 x2 ⊕ x2 x3 ⊕ x1 x2 x3 имеем c(1, 1, 0) = c(0, 1, 1) = c(1, 1, 1) = 1, а на всехостальных наборах значение функции c равно нулю.Упражнение 12. Покажите, что имеет место равенствоMf (eα) =c(eγ ).(5.1)γe∈E2nγe6eαСледующая теорема показывает, что функции f и c оказываются в некотором смысле взаимнообратными1 .MТеорема 5.1. Пусть f (exn ) =c(eγ )Kγe . Тогдаγe∈E2nc(eα) =Mf (eγ ).(5.2)γe∈E2nγe6eαДоказательство. Проведем индукцию по рангу набора |eα|.
Если |eα| = 0 , т.е. αe=e0, то утверждениетеоремы верно, поскольку c(e0) = f (e0). Пусть теперь (5.2) выполнено для всех наборов ранга не большеr . Пусть |eα| = r + 1 . Тогда из (5.1) следует, чтоMMc(eγ ).f (eα) =c(eγ ) = c(eα) ⊕γe∈E2nγe<eαγe∈E2nγe6eαДля завершения индуктивного перехода осталось показать, чтоMMf (eγ ).c(eγ) =(5.3)γe∈E2nγe<eαγe∈E2nγe<eα1 Теорема 5.1, также, как и следующая ниже теорема 5.2, является частным примером т.н. обращения Мёбиуса. Подробнее об этом можно узнать из [12]2324ГЛАВА 5. ПРЕДСТАВЛЕНИЕ БУЛЕВЫХ ФУНКЦИЙ ПОЛИНОМАМИ НАД ZПользуясь индуктивным предположением, получаемMM MMe =c(eγ) =f (β)γe∈E2nγe∈E2nγe<eαКаждая суммаMγe<eαneβ∈E2e γβ6eMef (β).γe∈E2nneβ∈E2e γ <ee α β6eαβ<eeα|−|β|e представляет собой сумму из (2|ef (β)− 1) одинаковых слагаемых, поэтомуγe∈E2ne γ <eβ6eαMe = f (β).ef (β)γe∈E2ne γ <eβ6eαОтсюда непосредственно следует (5.3).Весом функции f ∈ P2 (n) называется суммарное число наборов, на которых значение f равно 1 .Вес функции f обозначается через wt(f ).
Из теоремы 5.1 следует, что четность веса функции из P2 (n)совпадает с четностью коэффициента при ЭК x1 · . . . · xn в ее полиноме Жегалкина. Таким образом,существует полиномиальный алгоритм, который определяет четность веса функции по ее полиномуЖегалкина.Обозначим через Z[exn ] кольцо полиномов с целыми коэффициентами от переменных x1 , . . . , xn .b , гдеЧерез Zb [exn ] обозначим множество полиномов из Z[exn ], у которых каждый моном имеет вид bc·Kbbc ∈ Z, а K — произведение вида xi1 · .
. . · xim , где ij 6= ik при j 6= k .x4 ] , 3x1 + x1 x2 x4 − 18x3 x4 ∈ Zb [ex4 ] .Например, 3x21 + x1 x52 x34 − 18x3 x4 ∈ Z[eАналогично тому, как это делалось для полиномов Жегалкина, можно определить произведениеb αe , соответствующее набору αKe ∈ E2n . В это произведение будут входить те и только те xi , для которыхb αeαi = 1. Для фиксированного полинома Pb ∈ Zb [exn ] через bc(eα) будем обозначать коэффициент при Kв этом полиноме.Всякую булеву функцию можно рассматривать как функцию над Z, определенную лишь для наборов значений переменных из E2n . Будем говорить, что полином Pbf ∈ Z[exn ] реализует булеву функциюf , если функция Pbf совпадает с f на E2n .Утверждение 5.1.
Для любой функции из P2 (n) найдется реализующий ее полином из Zb [exn ].Доказательство. Булевы функции 1 , x ∧ y и x ⊕ y реализуются соответственно полиномами 1, xyи x + y − 2xy . Суперпозиция полиномов суть полиномом, поэтому по любой формуле от xen в базисе0nb{1, ⊕, ∧} (в т.ч. по полиному Жегалкина) можно построить полином P ∈ Z[ex ], реализующий ту жебулеву функцию. Очевидно, если в Pb0 заменить все ненулевые показатели степеней xi на единицу, тополученный полином Pb ∈ Zb [exn ] по-прежнему будет реализовывать ту же булеву функцию.Xb αe . ТогдаТеорема 5.2. Пусть f (exn ) =bc(eα)Kαe∈E2nbc(eα) =Xα|−|eγ|(−1)|ef (eγ ).(5.4)γe∈E2nγe6eαДоказательство.
Рассуждение аналогично доказательству теоремы 5.1. Будем вести индукцию порангу набора αe . Если |eα| = 0, т.е. αe=e0, то утверждение теоремы верно, поскольку bc(e0) = f (e0). Пустьтеперь (5.4) выполнено для всех наборов ранга не больше r . Пусть |eα| = r + 1 . ИмеемXXbc(eγ) = bc(eα) +bc(eγ ).f (eα) =γe∈E2nγe6eαγe∈E2nγe<eα25Таким образом,bc(eα) = f (eα) −Xγe∈E2nγe<eαbc(eγ ).Для завершения индуктивного перехода осталось показать, чтоXXα|−|eγ |+1bc(eγ) =(−1)|ef (eγ ).γe∈E2nγe<eαПользуясь индуктивным предположением, получаемXX XXee =bc(eγ) =(−1)|β|−|eγ | f (β)γe∈E2nγe<eα(5.5)γe∈E2nγe<eαneγe∈E2n β∈E2γe<eα eβ6eγXee =(−1)|β|−|eγ | f (β)n γee∈E2nβ∈E2e γ <eeβ6eαβ<eα(5.6)X Xe e(−1)|β|−|eγ | .=f (β) ·nnγe∈E2e γ <eβ6eαeβ∈E2e αβ<ee − |eОбозначив t = |β|γ | , имеемX(−1)e|β|−|eγ|γe∈E2n=t−1 Xtk=0kk(−1) =t Xtk=0k(−1)k − (−1)t = (−1)t+1 .(5.7)e γ <eβ6eαИз (5.6) и (5.7) следует (5.5).Из теоремы 5.2 и утверждения 5.1 вытекает следующее утверждение.Следствие 5.1.
Для любой булевой функции f ∈ P2 (n) во множестве Zb [exn ] существует единbственный реализующий ее полином Pf .Теорема 5.2 позволяет получить выражение для веса булевой функции f через коэффициентыполинома Pbf .XXα|b αe . Тогда wt(f ) =Лемма 10. Пусть f (exn ) =bc(eα)K2n−|ebc(eα) .αe∈E2nαe∈E2nДоказательство.wt(f ) =Xαe∈E2nf (eα) =X Xαe∈E2n γe∈E2nγe6eαbc(eγ) =X X Xbγ)1bc(eγ ) · 2n−|eγ | .c(e=γe∈E2nαe∈E2nαe>eγγe∈E2nПример 5.1. Построим полином из Zb [ex3 ] , реализующий функцию f (ex3 ) = x1 x2 ⊕ x2 x3 ⊕ x1 x3 :Pbf = x1 x2 +x2 x3 +x1 x3 −2x1 x2 x2 x3 −2x1 x2 x1 x3 −2x2 x3 x1 x3 +4x1 x2 x2 x3 x1 x3 = x1 x2 +x2 x3 +x1 x3 −2x1 x2 x3 .Вес этой функции равен 23−2 · 3 + 23−3 · (−2) = 4.26ГЛАВА 5.
ПРЕДСТАВЛЕНИЕ БУЛЕВЫХ ФУНКЦИЙ ПОЛИНОМАМИ НАД ZУпражнение 13.1. Покажите, что функция x1 ⊕ . . . ⊕ xn реализуется полиномомnXX(−2)s−1 xi1 · . . . · xis .s=1 16i1 <...<is 6n2. Покажите, что функция x1 ∨ . . . ∨ xn реализуется полиномомnXX(−1)s−1 xi1 · . . . · xis .s=1 16i1 <...<is 6n3. Пусть K1 ⊕ . .
. ⊕ Kl — полином Жегалкина функции f . Для каждого i, 1 6 i 6 l , пустьb i — произведение, соответствующее тому же набору, что и ЭК Ki . Покажите, что fKреализуется полиномомlXXbi · . . . · Kbi .(−2)s−1 K1ss=1 16i1 <...<is 6lПусть Ki1 , . . . , Kis — монотонные ЭК над переменными x1 , . . . , xn . Через r(Ki1 · . . . · Kis ) будемобозначать ранг набора, которому соответствует ЭК, полученная в результате упрощения выраженияKi1 · .
. . · Kis с применением законов коммутативности, ассоциативности, и тождеств xi · xi = xi .Например, r(x1 x2 · x1 x3 ) = 3.Лемма 11. Пусть f (exn ) = K1 ⊕ . . . ⊕ Kl . Тогдаwt(f ) =lXX(−2)s−1 · 2n−r(Ki1 ·...·Kis ) .(5.8)s=1 16i1 <...<is 6lДоказательство. Пусть f (exn ) = K1 ⊕ . . . ⊕ Kl . Согласно пункту 3 упражнения 13, полином из Zb [exn ] ,реализующий функцию f , будет иметь вид:nf (ex )=lXXbi · .
. . · Kbi .(−2)s−1 K1s(5.9)s=1 16i1 <...<is 6lbi · . . . · Kb i ) = ind(ebi · . . . · KbiВ дальнейшем, запись ind(Kα) будем понимать так: “в произведение K1s1sвходят переменные xi с теми и только теми индексами i , для которых αi = 1 ”. Это аналогичновведенному ранее понятию индексной характеристики монотонной ЭК.Группируя слагаемые в правой части (5.9), получаем:lX Xf (exn ) =αe∈E2n s=1Xbi · . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
