210
правок
Изменения
м
Нет описания правки
{{Определение
|definition= Синтезом [[Реализация булевой функции схемой из функциональных элементов|схемы из функциональных элементов ]] называется процедура получения логической схемы, реализующей заданную логическую функцию.
}}
Приведем несколько простейших алгоритмов синтеза [[Реализация булевой функции схемой из функциональных элементов|схем]], реализующих произвольную функцию от <tex> n </tex> аргументов <tex> f(x_{1}, ..., x_{n}) </tex>, в случае когда базис <tex> B = \{\neg, \lor, \land\} </tex>.
==Метод синтеза, основанный на [[СДНФ|совершенной ДНФ]]==
|statement = Для любой функции <tex> f(x_{1}, ..., x_{n}) </tex> имеет место неравенство <tex> size_{B}(f)\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> f(x_{1},...,x_{n}) = K_{1} \vee K_{2} \vee ... \vee K_{s} </tex>,
|about = 2
|statement =Для любой функции <tex> f(x_{1}, ..., x_{n}) </tex> имеет место соотношение <tex> size_{B}(f)\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_{B}(f) \le size_{B}(K_{n})+s-1 \le size_{B}(K_{n})+2^{n}-1 \lesssim 2^{n+1} </tex>
}}
==Метод синтеза схем [http://http://en.wikipedia.org/wiki/Claude_Shannon К.Э.Шеннона]==
{{Теорема
|statement =Для любой функции <tex> f(x_{1}, ..., x_{n}) </tex> имеет место соотношение <tex> size_{B}(f)\lesssim 12\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_{n} </tex>, где <tex> 1 \le m \le n </tex>:
<tex> f(x_{1},...,x_{n})= \bigvee 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>.
