С.Н. Селезнёва, А.Б. Дайняк, М.С. Шуплецов - Булевы функции и полиномы (1123636), страница 5
Текст из файла (страница 5)
Из определения следует, что она не сравнима со всеми другими нижними единицами f . Поскольку на наборе αe хотя бы одно слагаемое в Pfв нуль не обращается, то на αe не обращается в нуль и какое-то из слагаемых Ki1 , . . . , Kim . Отсюда αeсовпадает с одной из нижних единиц αe1 , . . . , αem . Лемма доказана.Упражнение 9. Найдите все нижние единицы функции f (x1 , x2 , x3 ) = x1 x2 ⊕ x1 x2 x3 ⊕ x3 .Какое максимальное и минимальное число нижних единиц может быть у функции из P2 (n) ,заданной полиномом длины l ?Останется ли верным утверждение леммы 5, если отбросить ограничение f (e0) = 0?ikxn ) функцию, получающуюся из функции f подстановкой константОбозначим через fαi11,, ...,..., αk (eαj на места соответствующих переменных xij .
Непосредственно из определений вытекает следующееутверждение.Утверждение 4.1. Функция f монотонна тогда и только тогда, когда для каждой ее нижнейi1 , ..., ikединицы αe выполнено f1,xn ) ≡ 1, где {i1 , . . . , ik } = ind(eα) ...., 1 (eТеорема 4.1 ([7]). Существует детерминированный алгоритм, распознающий монотонность функции f по ее полиному Жегалкина Pf за O(l3 ) операций, где l — длина полинома Pf .Доказательство. Если в Pf есть слагаемое 1 , то функция f является монотонной в том и толькотом случае, если Pf = 1. Разбор этого тривиального случая требует выполнения O(l) операций. Пустьтеперь Pf = K1 ⊕ . . .
⊕ Kl .20ГЛАВА 4. РАСПОЗНАВАНИЕ СВОЙСТВ ФУНКЦИЙ, ЗАДАННЫХ ПОЛИНОМАМИЭтап 1. Из леммы 5 следует, что для нахождения всех нижних единиц функции f достаточно найтивсе минимальные элементы во множестве {K1 , . . . , Kl } . Укажем схему, по которой это можносделать. Положим P := Pf .
Построим множество S1 следующим образом. Положим вначалеS1 := {K1 } . Вычеркнем из P слагаемое K1 . Теперь будем просматривать последовательно всеслагаемые в P в некотором фиксированном порядке. Пусть просматривается слагаемое Ki , ипусть в этот момент S1 = {Kj } .• Если Kj < Ki , то вычеркиваем слагаемое Ki из P и продолжаем просмотр дальше.• Если Kj > Ki , то полагаем S1 := {Ki } и вычеркиваем Kj из P .• Если же Kj и Ks несравнимы, то продолжаем просмотр дальше.После окончания просмотра множество S1 содержит некоторый минимальный элемент Ki1 , а вполиноме P нет слагаемых, сравнимых с Ki1 .
Если полином P пуст, то других минимальныхэлементов нет. В противном случае, аналогичным образом находим множество S2 = {Ki2 } , гдеKi2 — минимальный элемент, и так далее.В итоге мы найдем все минимальные элементы Ki1 , . . . , Kim . Поскольку m 6 l , и при поискеочередного минимального элемента нам требуется просмотреть каждое слагаемое в P всего одинраз (а слагаемых в P не более l ). Отсюда на поиск всех минимальных элементов потребуетсяO(l2 ) элементарных операций алгоритмической модели, описанной в предыдущем параграфе.Этап 2. Теперь для каждой нижней единицы αe , выполняем подстановку констант 1 в Pf на места всехпеременных с номерами из ind(eα). Затем упрощаем Pf , используя тождество K ⊕ K = 0.
Еслив результате получается полином, тождественно равный 1, то переходим к следующей нижнейединице, в противном случае выдаем ответ «нет» (f не монотонна). В случае, если проверенывсе нижние единицы, выдаем ответ «да» (f монотонна). Корректность ответа обеспечиваетсяутверждением 4.1. Число всех нижних единиц функции f не превосходит l , и для каждой нижнейединицы на упрощение полинома требуется не более O(l2 ) операций. Отсюда на втором этапевсего необходимо выполнить O(l3 ) операций.Нетрудно видеть, что второй этап является самым трудоемким в алгоритме.
Итак, за O(l3 ) операциймы нашли ответ на вопрос о монотонности функции f , что и завершает доказательство теоремы.Упражнение 10. Постройте по описанному алгоритму распознавания монотонности набросок схемы из функциональных элементов в базисе {∨, ∧, ¬} , сложность которой ограничена полиномом отразмера входа.
Вход схемы задается вектором длины n · l видаα1,1 , α1,2 , . . . , α1,n , α2,1 , α2,2 , . . . , α2,n , . . . , αl,1 , αl2 , . . . , αl,n ,где αi,j = 1 ⇔ xj ∈ Ki . Схема выдает на выходе 1 если и только если функция, задаваемая входнымполиномом, монотонна.Упражнение 11. Двойственным к понятию нижней единицы является понятие верхнего нуля.Можно ли по функции, заданной полиномом длины l , найти все ее нижние нули за полиномиальноепо l число операций?4.3Распознавание самодвойственностиПерейдем к вопросу о распознавании самодвойственности функций.
Распознавание самодвойственности с алгоритмической точки зрения оказывается более сложной задачей, чем распознавание монотонности, и нам придется вначале заняться исследованием свойств четных и нечетных булевых функций.Функция f назывется четной, если f (x1 , . . . , xn ) = f (x1 , . . . , xn ).Функция f назывется нечетной, если f (x1 , . . . , xn ) = f (x1 , . . . , xn ) .Доказательство трех следующих утверждений предоставляется читателю.4.3. РАСПОЗНАВАНИЕ САМОДВОЙСТВЕННОСТИ21Утверждение 4.2. Функция f (exn ) четна (нечетна) тогда и только тогда, когда функция f (exn )четна (соответственно, нечетна).Утверждение 4.3. Сумма двух четных, или двух нечетных функций является четной функцией.Сумма четной и нечетной функции есть нечетная функция.Утверждение 4.4.
Функция f (exn ) четна тогда и только тогда, когда функция g(exn ) = f (exn ) ⊕ xiнечетна.Лемма 6. Пусть f (x1 , . . . , xn ) = xi g(x1 , . . . , xi−1 , xi+1 , . . . , xn ) ⊕ h(x1 , . . . , xi−1 , xi+1 , . . . , xn ) . Тогда,если функция f четна, то g тоже четна.Доказательство.f (x1 , . . . , xn ) = xi g(x1 , . . .
, xi−1 , xi+1 , . . . , xn ) ⊕ h(x1 , . . . , xi−1 , xi+1 , . . . , xn ) == xi g(x1 , . . . , xi−1 , xi+1 , . . . , xn ) ⊕ (g(x1 , . . . , xi−1 , xi+1 , . . . , xn ) ⊕ h(x1 , . . . , xi−1 , xi+1 , . . . , xn ))Из единственности представления функции f полиномом Жегалкина следует, чтоg(x1 , . . . , xi−1 , xi+1 , . . . , xn ) = g(x1 , . . . , xi−1 , xi+1 , . .
. , xn ),то есть g — четная функция.Лемма 7. Пусть f (exn ) — четная, не равная тождественно нулю функция. Тогда в Pf найдутсяслагаемые K1 и K2 (не обязательно различные), для которых K1 ∩ K2 = ∅ .Доказательство. 1. Если f (0̃n ) = 1, то полином Pf содержит слагаемое 1. Выберем K1 = K2 = 1.2. Пусть f (0̃n ) = 0, тогда полином Pf не содержит слагаемое 1. Так как f (x̃n ) не тождественно равная нулю функция, найдется набор αe , на котором значение f равно 1. Следовательно, в Pf найдетсяслагаемое K1 6= 1 , обращающееся на αe в единицу. По определению четной функции, f (eα) = f (eα) .Значит в Pf есть слагаемое K2 , не обращающееся в нуль на наборе αe . Поэтомуind(K2 ) ⊆ ind(eα) = {1, 2, . . .
n} \ ind(eα) ⊆ {1, 2, . . . n} \ ind(K1 ),откуда следует, что ind(K1 ) ∩ ind(K2 ) = ∅.Лемма 8. Пусть f (exn ) — четная, не равная тождественно нулю функция. Пусть K — произвольная монотонная ЭК. Тогда, если в Pf найдется слагаемое L такое, что K ⊆ L, то в Pf найдутсяслагаемые L1 и L2 (не обязательно различные) такие, что L1 ∩ L2 = K .Доказательство. Проведем доказательство индукцией по рангу конъюнкции K . Если r(K) = 0 (т.е.K = 1), то достаточно воспользоваться леммой 7.
Предположим теперь, что утверждение леммы вернодля всех ЭК ранга, не превосходящего r . Пусть K 0 = xi · K , где r(K) = r . Пусть в Pf есть слагаемоеL0 такое, что K 0 ⊆ L0 . Значит xi — существенная переменная функции f . Представим f в видеf (x1 , . . . , xn ) = xi g(x1 , . . . , xi−1 , xi+1 , . . . , xn ) ⊕ h(x1 , .
. . , xi−1 , xi+1 , . . . , xn ). По лемме 6, функция g— четная. По предположению индукции, в Pg найдутся слагаемые L1 , L2 такие, что L1 ∩ L2 = K . Нотогда в Pf входят слагаемые L01 = xi ·L1 и L02 = xi ·L2 . Очевидно, L01 ∩L02 = K 0 , а это и требовалось.Теорема 4.2. Пусть f (exn√) — четная функция. Тогда тогда длина l и ранг r полинома Pf удовлетворяют неравенству l > 2r .Доказательство. Пусть f (e0) = 0. Так как r(Pf ) = r , то в Pf найдется слагаемое K ранга r . Умножества K всего 2r подмножеств K1 , . .
. , K2r . По лемме 8, для каждого Ki в Pf найдется параслагаемых L0i и L00i , дающих в пересечении это подмножество. Очевидно, при i 6= j пары (L0i , L00i ) и(L0j , L00j ) различны. Но всего в Pf можно выбрать не более l2 различных пар слагаемых. Отсюда иследует утверждение теоремы.22ГЛАВА 4.
РАСПОЗНАВАНИЕ СВОЙСТВ ФУНКЦИЙ, ЗАДАННЫХ ПОЛИНОМАМИСледствие 4.1. √Пусть функция f нечетна. Тогда для ранга r и длины l полинома Pf выполненонеравенство l > 2r − 1 .Доказательство. По утверждению 4.4, функция f ⊕ x1 четна. Применим к этой функции теорему4.2.Пусть K — произвольная монотонная ЭК, P — полином Жегалкина.
Обозначим через i(K, P )остаток от деления на 2 мощности множества {K 0 ∈ P | K ⊂ K 0 } . Справедливо следующее утверждение.Лемма 9.1. Функция f (exn ) является четной тогда и только тогда, когда i(K, Pf ) = 0 длялюбой монотонной ЭК K над {x1 , . . . , xn } .2. Функция f (exn ) является нечетной тогда и только тогда, когда i(K, Pf ) = 0 для любой монотонной ЭК K над {x1 , . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
