210
правок
Изменения
м
Нет описания правки
==Метод синтеза, основанный на более компактной реализации множества всех конъюнкций==
{{Определение
|definition= <tex> f(n) \sim g(n) </tex> означает, что <tex>f</tex> асимптотически эквивалентна <tex>g</tex>, то есть <tex>\lim_{n \to \infty}\frac{f(n)}{g(n)} = 1</tex>
}}
{{Определение
|definition= <tex> f(n) \lesssim g(n) </tex> означает, что <tex>\overline{\lim}_{n \to \infty}\frac{f(n)}{g(n)} \le 1</tex>
}}
{{Лемма
|id = Th2
|about = 2
|statement = Имеет Для любой функции <tex> f(x_{1}, ..., x_{n}) </tex> имеет место соотношение <tex> Size_size_{B}(nf)\lesssim 2^{n+1} </tex>.|proof = Пусть <tex> f(x_{1},...,x_{n}) </tex> произвольная булева функция,<tex> f \ne 0 </tex>. Заменим в схеме (рис. 2) верхнюю часть схемы, реализующую конъюнкции <tex> K_{1} \vee K_{2} \vee ... \vee K_{s} </tex>, схемой, реализующей все конъюнкции из <tex> K_{n} </tex>. Тогда для любой такой функции <tex> f(x_{1},...,x_{n}) </tex> (не равной нулю) имеем
::<tex> Size_size_{B}(f) \le Lsize_{B}(K_{n})+s-1 \le Lsize_{B}(K_{n})+2^{n}-1 \lesssim 2^{n+1} </tex>
Таким образом,
::<tex> Size_size_{B}(nf)\lesssim 2^{n+1}. </tex>
Теорема доказана.
|id = Th3
|about = 3
|statement = Имеет Для любой функции <tex> f(x_{1}, ..., x_{n}) </tex> имеет место соотношение <tex> Size_size_{B}(nf)\lesssim 12\frac {2^{n}}{2} </tex>.
|proof = [[Файл:Synschemes Theorem2.png|300px|thumb|right|Рис. 4]]
Пусть <tex> f(x_{1},...,x_{n}) </tex> произвольная булева функция. Рассмотрим разложение <tex> f </tex> по переменным <tex> x_{1},...,x_{n} </tex>, где <tex> 1 \le m \le n </tex>:
:1. Схема <tex> S_{1} </tex> реализует все конъюнкции из множества <tex> K_{m} (x_{1},...,x_{m}) </tex>. В силу [[#Lemma2|Леммы 2]] выполняется неравенство
::<tex> Size_size_{B}(S_{1}) \le Size_size_{B}(K_{m}) \lesssim 2^{m} </tex>.
:2. Схема <tex> S_{2} </tex> реализует <tex> F(x_{m+1},...,x_{n}) </tex> всех булевых функций от переменных <tex> x_{m+1},...,x_{n} </tex>. В силу [[#Th1|Теоремы 1]]
::<tex> Size_size_{B}(S_{2}) \le (n-m)2^{n-m+1}2^{2^{n-m}} </tex>.
:3. Схема <tex> S_{3} </tex> производит "сборку" в соответствии с разложением функции <tex> f </tex>: для каждого набора реализуется конъюнкция
::<tex> x_{1}\wedge\overline{x}_{2}\wedge{x}_{3}\wedge ... \wedge{x}_{m}f(x_{m+1}\wedge\overline{x}_{m+2}\wedge{x}_{m+3}\wedge ... \wedge{x}_{n}) </tex> (<tex> 2^{m} </tex> элементов конъюнкции) и образуется дизъюнкция таких конъюнкций (<tex> 2^{m}-1 </tex> элементов дизъюнкции).
Поэтому выполняется неравенство <tex> Size_size_{B}(S_{3}) \le 2^{m} +2^{m} -1 </tex>. Таким образом,
::<tex> Size_size_{B}(Sf) \le Size_size_{B}(S_{1})+Size_size_{B}(S_{2})+Size_size_{B}(S_{3}) \lesssim 3 \cdot 2^{m} +(n-m)2^{n-m+1}2^{2^{n-m}} </tex>.
Положим (для упрощения дальнейших выкладок) <tex> k=n-m </tex>. Тогда
::<tex> Size_size_{B}(nf) \lesssim 3 \cdot 2^{n-k} +k2^{k+1}2^{2^{k}} </tex>.
Заметим, что второе слагаемое "очень быстро" растет с ростом <tex> k </tex>, а первое слагаемое убывает с ростом <tex> k </tex> медленней. Поэтому следует взять такое значение <tex> k </tex>, при котором первое и второе слагаемые приблизительно равны, и потом немного уменьшить <tex> k </tex>. Тогда второе слагаемое "сильно" уменьшится, а первое "не очень сильно" возрастет. Возьмем, например, <tex> k=\log_{2}n </tex>. Тогда
При этом выборе <tex> k </tex> окончательно имеем
::<tex> Size_size_{B}(n)\lesssim 12\frac {2^{n}}{2} </tex>.
Теорема доказана.}}
