210
правок
Изменения
м
Нет описания правки
{{Определение |definition= Синтезом схемы из функциональных элементов называется процедура получения логической схемы, реализующей заданную логическую функцию.}} Приведем несколько простейших алгоритмов синтеза [[Реализация булевой функции схемой из функциональных элементов|схем]], реализующих произвольную функцию от <tex> n </tex> аргументов <tex> f(x_{1}, ..., x_{n}) </tex>, в случае когда базис состоит из элементов: инвертора<tex> B = \{\neg, \lor, конъюнктора и дизъюнктора\land\} </tex>.
==Метод синтеза, основанный на [[СДНФ|совершенной ДНФ]]==
|about = 1
|statement =
Для любой конъюнкции функции <tex> f(x_{1}\wedge , ... \wedge , x_{n} ) </tex>, реализующей конъюнкцию <tex> n </tex> аргументов, <tex> Size_size_{B}(x_{1} ... x_{n}f)\le 2n-1 </tex>
|proof = [[Файл:Synschemes Lemma1.png|250px|thumb|right|Рис. 1]]
Построим данную схему следующим образом: возьмем <tex> n </tex> элементов отрицания, присоединенных к выходам, и цепочки из элементов конъюнкции, имеющих <tex> n </tex> "свободных" входов.
Очевидно, что сложность построенной схемы равна <tex> 2n-1 </tex>.
Поэтому <tex> Size_size_{B}(x_{1} ...x_{n}f)\le 2n-1 </tex>.
Лемма доказана.
|id = Th1
|about = 1
|statement = Имеет Для любой функции <tex> f(x_{1}, ..., x_{n}) </tex> имеет место неравенство <tex> Size_size_{B}(nf)\le n2^{n+1} </tex>
|proof = [[Файл:Synschemes Theorem1.png|250px|thumb|right|Рис. 2]]
Пусть <tex> f(x_{1},...,x_{n}) </tex> произвольная [[Определение булевой функции|булева функция]]. Если <tex> f \ne 0 </tex>, то <tex> f </tex> может быть задана нормальной дизъюнктивной формой
Схема <tex> S </tex> для <tex> f </tex> состоит из конъюнкций <tex> K_{j} </tex> (каждая из них в соответствии с [[#Lemma1|Леммой 1]] имеет сложность не более <tex> 2n-1 </tex>) и цепочки из <tex> s-1 </tex> элемента дизъюнкции с <tex> s </tex> свободными входами. Свободные входы этой цепочки присоединяются к выходам схем для конъюнкций <tex> K_{j} </tex>.(рис. 2) Имеем
::<tex> Size_size_{B}(nf)\le s(2n-1)+s-1 < s(2n-1)+s = 2ns \le n2^{n+1} </tex>.
Если <tex> f = 0 </tex>, то схема строится в соответствии с представлением <tex> 0=x_{1}\wedge\overline{x}_{1} </tex>, то есть<tex> Size_size_{B}(0) \le 2</tex>.
Таким образом, для любой функции <tex> f(x_{1},...,x_{n}) </tex> выполняется неравенство
::<tex> Size_size_{B}(f(x_{1},...,x_{n}))\le n2^{n+1} </tex>.
Поэтому <tex> Size_size_{B}(nf)\le n2^{n+1} </tex>.
Теорема доказана.
|id = Lemma2
|about = 2
|statement = Имеет Для функции <tex> K_{n} </tex>, реализующей конъюнкцию <tex> n </tex> элементов, имеет место соотношение <tex> Size_size_{B}(K_{n}) \sim 2^n </tex>
|proof = [[Файл:Synschemes Lemma2.png|250px|thumb|right|Рис. 3]]
Разделим цепочки конъюнкций на две части. Каждая конъюнкция <tex> x_{1}\wedge\overline{x}_{2}\wedge{x}_{3}\wedge ... \wedge{x}_{i} </tex> может быть представлена в виде конъюнкции двух конъюнкций длины <tex> k </tex> и <tex> n-k </tex>:
Поэтому схема для <tex> K_{n} </tex> может быть образована из схем для <tex> K_{k}(x_{1}\wedge\overline{x}_{2}\wedge{x}_{3}\wedge ... \wedge{x}_{n}) </tex> и <tex> K_{n-k}(x_{k+1}\wedge\overline{x}_{k+2}\wedge{x}_{k+3}\wedge ... \wedge{x}_{n}) </tex> и системы из <tex> 2^n </tex> элементов конъюнкции, осуществляющих вышеприведенную операцию.(рис. 3) Следовательно,
::<tex> Size_size_{B}(K_{n}) \le Size_size_{B}(K_{k}) + Size_size_{B}(K_{n-k}) + 2^n </tex>.
Так как по [[#Th1|Теореме 1]] <tex> Size_size_{B}(K_{n}) \le k2^{k+1} </tex> , <tex> Size_size_{B}(K_{n-k}) \le (n-k)2^{n-k+1} </tex>,то
::<tex> Size_size_{B}(K_{n}) \le k2^{k+1} + (n-k)2^{n-k+1} + 2^n </tex>.
Положим <tex> k=[\frac{n}{2}]</tex>. Тогда <tex> k \le \frac{n}{2} </tex>, <tex> n-k \le \frac{n}{2}+1 </tex> и
::<tex> Size_size_{B}(K_{n}) \le \frac{n}{2}2^{\frac{n}{2}+1} + (\frac{n}{2}+1)\frac{n}{2}2^{\frac{n}{2}+2} + 2^n =2^n+O(n2^{\frac{n}{2}})</tex>.
С другой стороны, при <tex> n \ge 2 </tex> каждая конъюнкция реализуется на выходе некоторого элемента, то есть при <tex> n \ge 2 </tex> выполняется неравенство <tex> Size_size_{B}(K_{n}) \ge 2^{n} </tex>. Таким образом,
::<tex> Size_size_{B}(K_{n}) \sim 2^n </tex>.
Лемма доказана.
