Изменения
Отмена правки 63145 участника 188.242.29.236 (обсуждение)
{{Определение
|definition= '''Синтезом [[Реализация булевой функции схемой из функциональных элементов|схемы из функциональных элементов]]''' называется процедура получения логической схемы, реализующей заданную логическую функцию.
}}
|id = Th1
|about = 1
|statement = Для любой функции <tex dpi = "130"> f(x_{1}, ..., x_{n}) </tex> имеет место неравенство <tex dpi = "130"> size_{B}(f)\le n2^{n+1} </tex>
|proof = [[Файл:Synschemes Theorem1.png|250px|thumb|right|Рис. 2]]
Пусть <tex> f(x_{1},...,x_{n}) </tex> {{---}} произвольная [[Определение булевой функции|булева функция]].
{{Определение
|definition= <tex> f(n) \sim g(n) </tex> означает, что <tex>f</tex> асимптотически эквивалентна <tex>g</tex>, то есть <tex>\lim\limits_{n \to \infty} </tex> <tex dpi = "150"> \frac{f(n)}{g(n)} = 1</tex>
}}
{{Определение
|definition= <tex> f(n) \lesssim g(n) </tex> означает, что <tex>\varlimsup\limits_{n \to \infty} </tex> <tex dpi = "150"> \frac{f(n)}{g(n)} \le 1</tex>
}}
Поэтому схема для <tex> K_{n} </tex> может быть образована из схем для <tex> K_{k}(x_{1}^{\sigma_{1}},\dotsc,x_{k}^{\sigma_{k}}) </tex> и <tex> K_{n-k}(x_{k+1}^{\sigma_{k+1}},\dotsc,x_{n}^{\sigma_{n}}) </tex> и системы из <tex> 2^n </tex> элементов конъюнкции, осуществляющих вышеприведенную операцию, как показано в [[#Th1|теореме 1]] (рис. 3). Левая часть схемы считает конъюнкцию переменных <tex> x_{1}^{\sigma_{1}},\dotsc,x_{k}^{\sigma_{k}} </tex>, а правая часть - переменных <tex> x_{k+1}^{\sigma_{k+1}},\dotsc,x_{n}^{\sigma_{n}}</tex>. Следовательно,
::<tex dpi = "130"> size_{B}(K_{n}) \le size_{B}(K_{k}) + size_{B}(K_{n-k}) + 2^n </tex>.
Так как по [[#Th1|теореме 1]] <tex dpi = "130"> size_{B}(K_{k}) \le k2^{k+1} </tex> , <tex dpi = "130"> size_{B}(K_{n-k}) \le (n-k)2^{n-k+1} </tex>,то
::<tex dpi = "130"> size_{B}(K_{n}) \le k2^{k+1} + (n-k)2^{n-k+1} + 2^n </tex>.
Положим <tex dpi = "130"> k= </tex> <tex dpi = "150"> [\frac{n}{2}]</tex>. Тогда <tex dpi = "130"> k \le </tex> <tex dpi = "150">\frac{n}{2} </tex>, <tex dpi = "130"> n-k \le </tex> <tex dpi = "150">\frac{n}{2}+1 </tex> и
::<tex dpi = "130"> size_{B}(K_{n}) \le </tex> <tex dpi = "150">\frac{n}{2}2^{\frac{n}{2}+1} + (\frac{n}{2}+1)2^{\frac{n}{2}+2} + 2^n =2^n+O(n2^{\frac{n}{2}})</tex>.
С другой стороны, при <tex dpi = "130"> n \ge 2 </tex> каждая конъюнкция реализуется на выходе некоторого элемента, то есть при <tex dpi = "130"> n \ge 2 </tex> выполняется неравенство <tex dpi = "130"> size_{B}(K_{n}) \ge 2^{n} </tex>. Таким образом,
::<tex dpi = "130"> size_{B}(K_{n}) \sim 2^n </tex>.
}}
|id = Th2
|about = 2
|statement =Для любой функции <tex dpi = "130"> f(x_{1}, ..., x_{n}) </tex> имеет место соотношение <tex dpi = "130"> size_{B}(f)\lesssim 2^{n+1} </tex>.
|proof =
[[Файл:Synschemes_ NewTheorem2.png|400px|thumb|right|В верхней части схемы рис.2 все подсхемы, вычисляющие конъюнкции, заменили на <tex>K_n</tex>]]
Пусть <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 dpi = "130"> size_{B}(f) \le size_{B}(K_{n})+s-1 \le size_{B}(K_{n})+2^{n}-1 \lesssim 2^{n+1} </tex>
Таким образом,
::<tex dpi = "130"> size_{B}(f)\lesssim 2^{n+1}. </tex>
}}
==Метод синтеза схем К.Э.Шеннона <ref>[http://en.wikipedia.org/wiki/Claude_Shannon Claude ShannonК.Э.Шеннона]</ref>==
{{Теорема
|id = Th3
|about = 3
|statement =Для любой функции <tex dpi = "130"> f(x_{1}, ..., x_{n}) </tex> имеет место соотношение <tex dpi = "130"> size_{B}(f)\lesssim 12 </tex> <tex dpi = "150"> \frac {2^{n}}{n} </tex>.
|proof = [[Файл:Synschemes-Theorem2.png|300px|thumb|right|Рис. 4]]
Пусть <tex> f(x_{1},...,x_{n}) </tex> {{---}} произвольная булева функция. Рассмотрим разложение <tex> f </tex> по переменным <tex> x_{1},...,x_{m} </tex>, где <tex> 1 \le m \le n </tex>:
<tex dpi = "130">f(x_{1},...,x_{n})=\displaystyle\bigvee_{(\sigma_{1},\dotsc,\sigma_{m})}x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{m}^{\sigma_{m}}\wedge f(\sigma_{1},\dotsc,\sigma_{m},x_{m+1},\dotsc,x_{n}) </tex>.
'''Схема для функции <tex> f </tex> строится из трех подсхем: <tex> S_{1},S_{2},S_{3} </tex>. (рис. 4)'''
:1. Система <tex dpi = "130"> K_{m} (x_{1}^{\sigma_{1}},\dotsc,x_{m}^{\sigma_{m}}) </tex> содержит всевозможные конъюнкции <tex dpi = "130">x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{m}^{\sigma_{m}}</tex>. И схема <tex> S_{1} </tex> реализует все эти конъюнкции. В силу [[#Lemma2|леммы 2]] выполняется неравенство
::<tex dpi = "130"> size_{B}(S_{1}) \le size_{B}(K_{m}) \lesssim 2^{m} </tex>.
:2. Схема <tex> S_{2} </tex> реализует систему <tex dpi = "130"> F(x_{m+1}^{\sigma_{m+1}},...,x_{n}^{\sigma_{n}}) </tex> всех булевых функций от всевозможных наборов переменных <tex> x_{m+1},...,x_{n} </tex>. Другими словами, подсхема <tex> S_{2} </tex> вычисляет все булевы функции, зависящие от последних <tex> n - m </tex> переменных. В силу [[#Th1|теоремы 1]]::<tex dpi = "130"> 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 dpi = "130"> \widetilde{\sigma}=(\sigma_{1},\dotsc,\sigma_{m}) </tex> реализуется конъюнкция
::<tex dpi = "130"> x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{m}^{\sigma_{m}}\wedge f(\widetilde{\sigma},x_{m+1},\dotsc, x_{n}) </tex> (<tex> 2^{m} </tex> элементов конъюнкции) и образуется дизъюнкция таких конъюнкций (<tex dpi = "130"> 2^{m}-1 </tex> элементов дизъюнкции).
Поэтому выполняется неравенство <tex dpi = "130"> size_{B}(S_{3}) \le 2^{m} +2^{m} -1 </tex>. Таким образом,
::<tex dpi = "130"> size_{B}(f) \le size_{B}(S_{1})+size_{B}(S_{2})+size_{B}(S_{3}) \lesssim 3 \cdot 2^{m} +(n-m)2^{n-m+1}2^{2^{n-m}} </tex>.
Положим <tex dpi = "130"> k=n-m </tex>. Тогда
::<tex dpi = "130"> size_{B}(f) \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 dpi = "130"> k=\log_{2}n </tex>. Тогда
::<tex dpi = "130"> 3 \cdot 2^{n-k} = 3 \cdot </tex> <tex dpi = "150"> \frac{2^{n}}{n} </tex>,
::<tex dpi = "130"> k \cdot 2^{k+1} \cdot 2^{2^{k}}=\log_{2}n\cdot (2n)\cdot 2^{n}</tex>,
то есть получили "слишком много". Возьмем <tex> k </tex> на единицу меньше: <tex dpi = "130"> k=\log_{2}n-1 </tex>. Тогда
::<tex dpi = "130"> 3 \cdot 2^{n-k} = 3 \cdot </tex> <tex dpi = "150"> \frac{2^{n}}{n} \cdot 2 </tex>,
::<tex dpi = "130"> k \cdot 2^{k+1} \cdot 2^{2^{k}}=(\log_{2}n-1)\cdot n\cdot 2^{\frac{n}{2}}</tex>.
Вспомним теперь, что <tex> k </tex> должно быть целым числом, и положим <tex dpi = "130"> k=[\log_{2}n-1] </tex>. Тогда<tex dpi = "130"> n-k < n- \log_{2} + 2</tex>,
::<tex dpi = "130"> 3 \cdot 2^{n-k} < 12 \cdot </tex> <tex dpi = "150"> \frac {2^{n}}{n} </tex>,
::<tex dpi = "130"> k\cdot 2^{k+1}\cdot 2^{2^{k}} \le (\log_{2}-1)\cdot n\cdot 2^{\frac{n}{2}} </tex>.
При этом выборе <tex> k </tex> окончательно имеем
::<tex dpi = "130"> size_{B}(n)\lesssim 12 </tex> <tex dpi = "150"> \frac {2^{n}}{n}</tex>.
}}
== Литература ==
