О.Б. Лупанов - Курс лекций по дискретной математике, страница 9

· xσnn . Перегруппируем множители, собрав в одномместе переменные с нулевыми степенями. Тогда, перенумеровав переменные и применив правило де Моргана,функцию можно переписать в видеf = (x1 & . . . & xk ) & (xk+1 ∨ xk+2 ∨ . . . ∨ xn ).(1)Заметим, что в этой формуле не более n операций. Значит, сложность схемы данной функции не превосходит n.Постройка схемы по данной формуле предоставляется читателю.Утверждение 3.1.L(n) 6 (n + 1) · 2n .(2) Рассмотрим произвольную функцию f от n переменных и построим её СДНФ.

В ней может быть неболее 2n дизъюнкций выражений вида xσ1 1 · . . . · xσnn . Так как сложность каждого дизъюнкта мы уже оцениличислом n, то сложность всей схемы не превосходит n · 2n + (2n − 1) < (n + 1) · 2n . Для функций, тождественноравных нулю, можно использовать формулу f = x1 & x1 . При этом мы предполагаем, что f — функция покрайней мере от одной переменной.

Схема будет содержать 2 элемента, значит, её сложность L(f ) = 2 6 n · 2n .Итак, сложность любой функции L(n) 6 (n + 1) · 2n . Замечание. На самом деле легко доказать, что L(n) 6 (n + 1) · 2n−1. Действительно, посмотрим на таблицузначений нашей функции и выясним, чего в ней больше: нулей или единиц. В зависимости от этого будем использовать, соответственно, СДНФ либо СКНФ. В самом худшем случае будет 2n−1 дизъюнкций или коньюнкций.Следствие 3.1.

В силу сделанного замечания верна оценка L(n) 6 n · 2n , так как 21 · (n + 1) · 2n 6 n · 2n .Обозначим через Kn множество всех функций вида xσ1 1 · . . . · xσnn . Сейчас мы будем строить схему, котораяреализует все функции из Kn . Сложность такой схемы обозначим C(n).Мы будем делать это индуктивно. При n = 1 делать почти нечего. Предположим, что мы уже построилисхему для всех множеств с номерами меньше n. Зафиксируем число k < n.

Построим схему, реализующую всефункции из Kn , используя в качестве подсхем две схемы: для Kk и для Kn−k .Рассмотрим произвольную конъюнкциюσk+1xσ1 1 · . . . · xσnn = (xσ1 1 · . . . · xσk k ) & (xk+1· . . . · xσnn ).(3)Возьмём по одному выходу из схем для Kk и Kn−k , реализующие множители в скобках, и подключим их кконъюнктору. Получим схему, реализующую одну конъюнкцию n переменных.

Также поступим со всеми 2nконъюнкциями n переменных, то есть будем делать их, используя соответствующие выходы в схемах Kk иKn−k , связывая их конъюнктором. Итого получим схему для Kn , затратив C(k) + C(n − k) + 2n элементов.Теперь возьмём k := n2 . Значит,n n n nnC(n) 6 2n + 2C= 2n + 2 2 2 + 2C 2= 2n + 2 2 +1 + 22 C 2 = · · · . 2n .(4)22228Отсюда следует, что можно (асимптотически) улучшить оценку для L(n): реализовав все конъюнкции ценой∼ 2n элементов, склеим их не более чем 2n дизъюнкциями, в итоге получим схему сложности порядка 2n+1 .3.1.1. Метод Шеннона синтеза схемВсе дальнейшие оценки будут асимптотическими, поэтому мы не будем всякий раз об этом упоминать. Таккак никаких других логарифмов в дискретной математике не встречается, под log мы всегда будем пониматьlog2 .Мы будем использовать разложение функции по переменным:_f (x1 , .

. . , xn ) =xσ1 1 · . . . · xσq q f (σ1 , . . . , σq , xq+1 , . . . , xn ).(5)(σ1 ,...,σq )Пусть q = n − k. Реализуем все конъюнкции Kq первых q переменных, при этом потратим 2q элементов. Кромеkэтого, нам по максимуму может потребоваться реализовать все функции от k переменных, коих имеется 22штук. Не напрягаясь, реализуем каждую из них со сложностью k · 2k . При склейке основной схемы по указаннойвыше формуле потребуется ещё 2q конъюнкторов (для вычисления слагаемых) и ещё 2q −1 дизъюнкторов. ИтогоkkL(f ) . 2q + 2q + (2q − 1) + k · 2k · 22 .

3 · 2q + k · 2k · 22 .(6)Выбор k — дело ответственное. Нам нужно, чтобы последнее слагаемое не было очень большим. Логично взятьk = log n, но, если подставить, получается многовато. Поэтому возьмём k := [log n] − 1. ТогдаL(f ) . 3 · 2 ·2n2[log n]+n log n n2nn log n n2n·22 . 3· 2·2·+· 2 2 . 12 .2n2n(7)3.1.2. Асимптотически наилучший метод построения схемТеорема 3.2 (О.

Б. Лупанов).L(n) .2n.n(8) Рассмотрим произвольную булеву функцию n переменных. Отделим q := n − k первых переменных ирассмотрим таблицу, в которой 2k строк и 2q столбцов. Строки занумеруем всевозможными значениями последних k переменных, а столбцы — всевозможными значениями первых q переменных. Ячейки таблицы заполнимзначениями функции. Каждый столбец представляет собой значения функции, полученной подстановкой констант в первые q переменных, то есть f (σ1 , . . .

, σq , xq+1 , . . . , xn ). Разрежем таблицу на горизонтальные полоскипо s строк в каждой (последняя полоса будет, возможно, меньше; пусть в ней s′ < s строк). Число полос будетравно k22kp :=<+ 1.(9)ssЧерез Ii обозначим индикатор i-й полосы, то есть функцию, которая равна единице на строках этой полосы,и только на них. Обозначим теперь f(σ1 ,...,σq ),i (xq+1 , . . . , xn ) := f (σ1 , . . . , σq , xq+1 , . . . , xn ) · Ii .

Такие функциибудем называть обрезанными функциями. Ясно, чтоf (σ1 , . . . , σq , xq+1 , . . . , xn ) =p_f(σ1 ,...,σq ),i (xq+1 , . . . , xn ).(10)i=1Имеемf (x1 , . . . , xn ) =_(σ1 ,...,σq )xσ1 1 · . . . · xσq q · f (σ1 , . . . , σq , xq+1 , . . . , xn ).(11)Реализуем все конъюнкции первых q переменных, потратив 2q элементов. Кроме этого, реализуем все конъюнкции последних k переменных, потратив 2k элементов. Все обрезанные функции имеют не более s ненулевыхзначений, значит, их количество не превышает 2s . Поскольку все конъюнкции последних переменных уже есть,на изготовление СДНФ для каждой обрезанной функции уйдёт всего s дизъюнкций, значит, всего на реализациюобрезанных функций каждой полосы мы потратим не более s · 2s элементов, а всего — не более p · s · 2s .На сборку каждой f (σ1 , .

. . , σq , xq+1 , . . . , xn ) уйдёт ещё p дизъюнкций (поэтому всего на это уйдёт p · 2qопераций), а на сборку функции f уйдёт ещё 2q конъюнкций и 2q дизъюнкций.Суммируя полученные оценки, имеемL(f ) . 2q + 2k + ps · 2s + p · 2q + 2q + 2q = 3 · 2q + ps · 2s + p · 2q + 2k .29(12)Вспоминая, что p <2ks+ 1, получаемL(f ) . 3 · 2q +2k+ 1 (s · 2s + ·2q ) + 2k .s(13)kВидно, что s должно быть порядка n, но всё же чуть меньше его. Что касается k, то нужно, чтобы 2s → ∞,чтобы нам не мешала единица в скобках.

Положим k := [2 log n] и s := [n − 4 log n]. Подставляя эти значения,nполучаем оценку порядка 2n (выкладки временно предоставляем читателю). 3.1.3. Асимптотическая оценка снизу для сложности схемТеорема 3.3. Для любого ε > 0 выполено асимптотическое неравенствоL(n) & (1 − ε)2n.n(14)Введем следующие обозначения:• P2∗ (n) — функции, существенно зависящие от n переменных.• N (h, n) — число функций, существенно зависящих от n переменных, которые реализуются схемами сложности, не превосходящей h.• N ′ (h, n) — число функций, существенно зависящих от n переменных, которые реализуются схемами сложности ровно h;• N ′′ (h, n) — число схем сложности h для функций, существенно зависящих от n переменных;Очевидно, что N ′ = N , потому что всегда можно дополнить схему ничего не делающими элементами. Очевидно также, что N 6 N ′′ , так как одну функцию можно реализовать разными схемами, но не наоборот.Идея доказательства состоит в том, чтобы показать, что функций, реализуемых схемами сложностью меньшеnn(1 − ε) 2n , гораздо меньше, чем всех функций.

Итак, покажем, что для h0 := (1 − ε) 2n выполнено N (h0 , n) << |P2∗ (n)|. Мы будем оценивать величину N , мажорируя её величиной N ′′ .Пусть γ(p, q) — число графов с q ребрами и p := h + n вершинами (n входов и h элементов), N ′′ (h, n, q) —число схем с q ребрами. Сколько схем можно сделать из одного графа? У нас имеется не более:• 2q способов выбрать ориентацию ребер;• (h + n)n способов выбрать входы;• 3h способов присвоения вершинам различных ФЭ;• h + n способов выбора выхода.Итак, вспоминая оценку для числа графов, получаем:N ′′ (h, n, q) 6 γ(p, q) · 2q · (h + n)n+1 · 3h 6 Ah+n+q (h + n)q−h+1 · 2q · 3h .(15)Вспоминая, что q 6 2h, и собирая константы, окончательно запишем:N ′′ (h, n, q) 6 B 3h+n (h + n)h+1 .(16)Теперь получим оценку для N ′′ (n, h):′′N (n, h) 62hXN ′′ (h, n, q) 6 B 3h+n (h + n)h+1 (h + 1) 6 (C(h + n))h+n .(17)q=hНам нужно убедиться, что N ′′ (h0 , n) < |P2∗ (n)| при достаточно больших n.

Заметим, чтоnn−1|P2∗ (n)| > 22 − n22n∼ 22 .(18)Таким образом, требуемое неравенство будет выполнено, еслиlogN ′′ (h0 , n)= log N ′′ (h0 , n) − 2n + o(1) → −∞, n → ∞.|P2∗ (n)|30(19)Пришло время использовать полученную для N ′′ оценку. Далее все неравенства записаны для достаточно больших n:log N ′′ (h0 , n) − 2n + o(1) 6 (h0 + n) log C(h0 + n) − 2n + o(1) 62n+ n n − 2n + o(1) = (1 − ε)2n + n2 − 2n + o(1) =6 (1 − ε)n= n2 + o(1) − ε2n → −∞,n → ∞, (20)что и требовалось доказать. 3.2. Инвариантные классыВ логике для множества всех булевых функций от n переменных используется обозначение P2 (n). Множествовсех булевых функций обозначается через P2 .Определение.

Множество K ⊂ P2 (n) называется инвариантным классом, если оно замкнуто относительноподстановок констант, переименования переменных (без отождествления) и добавления/отбрасывания несущественных переменных.Пример 2.1.• Очевидно, P2 является инвариантным классом.• Функции, существенно зависящие не более чем от k переменных, образуют инвариантный класс.• Линейные и монотонные функции образуют инвариантный класс.Пусть Q — инвариантный класс. Через PQ (n) будем обозначать количество функций из Q от n переменных.nЯсно, что PQ (n) 6 22 .Будем считать, что Q 6= ∅. Рассмотрим последовательностьqnqn := 2 PQ (n).(21)Утверждение 3.4.

Последовательность {qn } монотонно убывает (нестрого). Возьмём функцию f ∈ Q, зависящую от n + 1 переменной и разложим её по последней переменной:f (x1 , . . . , xn+1 ) = xn+1 f (x1 , . . . , xn , 1) ∨ xn+1 f (x1 , . . . , xn , 0).(22)Имеем f (x1 , . . . , xn , c) ∈ Q, где c = 0, 1. Итак, каждая функция от n+1 переменной может быть сконструированаиз двух функций от n переменных этого же класса.