Изменения

|definition= '''Синтезом [[Реализация булевой функции схемой из функциональных элементов|схемы из функциональных элементов ]]''' называется процедура получения логической схемы, реализующей заданную логическую функцию.

Приведем несколько простейших алгоритмов синтеза [[Реализация булевой функции схемой из функциональных элементов|схем]], реализующих произвольную функцию от <tex> n </tex> аргументов <tex> f(x_{1}, ...\ldots, x_{n}) </tex>, в случае когда базис <tex> B = \{\neg, \lor, \land\} </tex>.

|statement = Для любой функции <tex> f(x_{1}, ..., x_{n}) </tex>, реализующей конъюнкцию <tex> n </tex> аргументовЛюбой конъюнкт в СДНФ можно представить не более, чем <tex> size_{B}(f)\le 2n-1 </tex>элементами.|proof = [[Файл:Synschemes Lemma1.png|250px|thumb|right|Рис1. Схема для <tex> \bar{x}_{1}\wedge x_{2}\wedge x_{3} \wedge \bar{x}_{4}</tex>. Сложность построенной схемы <tex>size_{B}(f)=2+3=5\leqslant 7</tex>.]] Построим данную схему следующим образом: возьмем если <tex> n i </tex>-й множитель равен <tex> \bar{x}_{i} </tex> элементов отрицания, присоединенных то присоединяем к выходам, и цепочки из элементов конъюнкции, имеющих выходу <tex> n i </tex> элемент отрицания и последовательно присоединяем к элементу конъюнкции, иначе просто присоединяем к "свободныхсвободному" входоввходу элемента конъюнкции.

Каждый <tex> i </tex>-й вход этой цепочки присоединяется к входу Очевидно, что сложность построенной схемы, если <tex> i </tex>-й множитель равен <tex> x_size_{iB} </tex>, или к выходу <tex> i </tex>(f)= n+n-го элемента отрицания, если <tex> i </tex>1 = 2n-й множитель равен <tex> \overline{x}_{i} 1 </tex>.(рис. 1)

Очевидно, что сложность построенной схемы равна Поэтому <tex> size_{B}(f)\leqslant 2n-1 </tex>.

Поэтому Приведем пример для <tex> size_f=\bar{x}_{1}\wedge x_{2}\wedge x_{B3}(f)\le 2n-1 wedge \bar{x}_{4}</tex>(рис. 1).

|statement = Для любой функции <tex> f(x_{1}, ...\ldots, x_{n}) </tex> имеет место неравенство <tex> size_{B}(f)\le leqslant n2^{n+1} </tex>

Пусть <tex> f(x_{1},...\ldots,x_{n}) </tex> {{---}} произвольная [[Определение булевой функции|булева функция]]. Если <tex> f \ne 0 </tex>, то <tex> f </tex> может быть задана нормальной дизъюнктивной формой

::Если <tex> f(= 0 </tex>, то схема строится в соответствии с представлением <tex> 0=x_{1},...,x_\wedge\overline{nx}) = K__{1} \vee K_</tex>, то есть <tex> size_{2B} (0) \vee ... \vee K_{s} leqslant 2</tex>,.

где Если <tex> s f \le 2^{n} ne 0 </tex> и каждая конъюнкция имеет вид , то <tex> f </tex> может быть задана [[ДНФ|дизъюнктивной нормальной формой]]

::<tex> K_{j}=f(x_{1}, \wedge\overlineldots,x_{xn}_) = K_{21}\wedgevee K_{x}_{32}\wedge ... vee \ldots \wedge{x}_vee K_{is} </tex>,

Схема где <tex> S </tex> для <tex> f </tex> состоит из конъюнкций <tex> K_s \leqslant 2^{jn} </tex> (и каждая из них в соответствии с [[#Lemma1|Леммой 1]] конъюнкция имеет сложность не более <tex> 2n-1 </tex>) и цепочки из <tex> s-1 </tex> элемента дизъюнкции с <tex> s </tex> свободными входами. Свободные входы этой цепочки присоединяются к выходам схем для конъюнкций <tex> K_{j} </tex>.(рис. 2) Имеемвид

::<tex> size_K_{Bj}=x_{1}(f)\le swedge\overline{x}_{2}\wedge{x}_{3}\cdot(2n-1)+s-1 < swedge \cdot(2n-1)+s = 2ns ldots \le n2^wedge{n+1x}_{i} </tex>.

Если Схема <tex> S </tex> для <tex> f = 0 </tex>, то схема строится состоит из конъюнкций <tex> K_{j} </tex> (каждая из них в соответствии с представлением [[#Lemma1|леммой 1]] имеет сложность не более <tex> 0=x_{2n-1}\wedge\overline{x}_{</tex>) и цепочки из <tex> s-1} </tex>, то естьэлемента дизъюнкции с <tex> s </tex> свободными входами. Свободные входы этой цепочки присоединяются к выходам схем для конъюнкций <tex> size_K_{Bj}(0) \le 2</tex>.(рис. 2) Имеем

Таким образом, для любой функции ::<tex> size_{B}(f)\leqslant s\cdot(2n-1)+s-1 < s\cdot(x_{2n-1},...,x_)+s = 2ns \leqslant n2^{n+1}) </tex> выполняется неравенство .

::Таким образом, для любой функции <tex> size_{B}(f(x_{1},...\ldots,x_{n}))\le n2^{n+1} </tex>.выполняется неравенство

Поэтому ::<tex> size_{B}(f(x_{1}, \ldots,x_{n}))\le leqslant n2^{n+1} </tex>. Теорема доказана.

|definition= <tex> f(n) \sim g(n) </tex> означает, что <tex>f</tex> асимптотически эквивалентна <tex>g</tex>, то есть <tex>\lim_lim\limits_{n \to \infty}\fracdfrac{f(n)}{g(n)} = 1</tex>

{{Определение|definition= Пусть есть булева функция от <tex> n </tex> аргументов <tex> f(: \lbrace0, 1\rbrace^n) \lesssim g(rightarrow \lbrace0, 1\rbrace </tex> и набор из <tex> n) </tex> означаетбулевых функций <tex> g_1 \dotsc g_n </tex>, таких что <tex>g_i :\overlinelbrace0, 1\rbrace^{m_i} \limrightarrow \lbrace0, 1\rbrace </tex>, где <tex> i=1,\dotsc, n</tex>. Тогда системой булевых функций называется функция <tex> S </tex> от всех аргументов функций <tex> g_i</tex>, которая определяется как  <tex> S(x_{11},\dotsc,x_{1(m_1)}_,x_{n 21},\to dotsc,x_{2(m_2)}</tex> <tex>,\inftydotsc,x_{n1},\fracdotsc,x_{n(m_n)})</tex><tex>=f(ng_1(x_{11},\dotsc,x_{1(m_1)}),g_2(x_{21},\dotsc,x_{g2(m_2)}),\dotsc,g_n(x_{n1},\dotsc,x_{n(m_n)} \le 1))</tex>

|statement = Для функции Пусть <tex> K_{n}(\lbrace x_{1}^{\sigma_{1}},\dotsc,x_{n}^{\sigma_{n}} \rbrace^{2^n}_{i=1}) </tex> {{---}} система всех <tex> 2^{n} </tex> конъюнкций <tex> x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{n}^{\sigma_{n}} </tex>, реализующей конъюнкцию где каждому <tex> i </tex> соответствует свой набор <tex> \lbrace \sigma_{1},\dotsc,\sigma_{n } \rbrace </tex> элементов, тогда для <tex> K_{n} </tex> имеет место соотношение <tex> size_{B}(K_{n}) \sim 2^n </tex>

Разделим цепочки конъюнкций на две части. Каждая конъюнкция Конъюнкции <tex> x_{1}^{\wedge\overlinesigma_{x1}_{2}\wedge\dotsc\wedge x_{xn}_^{3}\wedge ... \wedgesigma_{xn}_}</tex> соответствуют функциям <tex> g </tex> из определения функции,<tex> K_{in} </tex> может быть представлена в виде конъюнкции двух конъюнкций длины соответствует функции <tex> k S </tex> и , а конъюнкция функций <tex> g </tex> n-k соответствует функции <tex> f </tex>:.

::Заметим, что на вход схемы подается определенный набор аргументов <tex> x_{1}\wedge\overline{x}_{2}\wedge{x}_^{3}\wedge ... \wedge{x}_{n} = (x_sigma_{1}\wedge\overline{x}_{2}\wedge{x}_{3},\wedge ... \wedge{x}_{k})(dotsc,x_{k+1}\wedge\overline{xn}_^{k+2}\wedgesigma_{x}_{k+3}\wedge ... \wedge{xn}_{n}) </tex>, то есть на выходе схемы будет результат конъюнкции этих аргументов.

Поэтому схема для Разделим цепочки конъюнкций на две части. Каждая конъюнкция <tex> K_x_{n1} </tex> может быть образована из схем для <tex> K_^{k}(x_\sigma_{1}}\wedge\overline{x}_{2}dotsc\wedgex_{xn}_^{3}\wedge ... \wedgesigma_{xn}_{n}) </tex> может быть представлена в виде конъюнкции двух конъюнкций длины <tex> k </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 k </tex> элементов конъюнкции, осуществляющих вышеприведенную операцию.(рис. 3мы выберем позже) Следовательно,:

::<tex> size_x_{B1}(K_^{\sigma_{1}}\wedge\dotsc\wedge x_{n}) ^{\le size_sigma_{Bn}}= (K_x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{k}^{\sigma_{k}}) (x_{k+ size_1}^{B\sigma_{k+1}}(K_\wedge\dotsc\wedge x_{n-k}) + 2^{\sigma_{n }}) </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> size_x_{B1}(K_^{\sigma_{n1}}) ,\le k2dotsc,x_{k}^{\sigma_{k+1}} </tex> , а правая часть - переменных <tex> size_x_{Bk+1}(K_^{\sigma_{n-k+1}) },\le (dotsc,x_{n-k)2}^{\sigma_{n-k+1}} </tex>. Следовательно,то

::<tex> size_{B}(K_{n}) \le k2^leqslant size_{B}(K_{k}) +1size_{B} + (n-k)2^K_{n-k+1} ) + 2^n </tex>.

Положим Так как по [[#Th1|теореме 1]] <tex> k=[\fracsize_{nB}(K_{2k}]</tex>. Тогда <tex> k ) \le \fracleqslant k2^{n}{2k+1} </tex>, <tex> size_{B}(K_{n-k }) \le \fracleqslant (n-k)2^{n}{2}-k+1 } </tex> и ,то

::<tex> size_{B}(K_{n}) \le \frac{n}{2}2leqslant k2^{\frac{n}{2}k+1} + (\frac{n}{2}+1-k)\frac{n}{2}2^{\frac{n}{2}-k+21} + 2^n =2^n+O(n2^{\frac{n}{2}})</tex>.

С другой стороны, при Положим <tex> k=[\dfrac{n \ge }{2 }]</tex> каждая конъюнкция реализуется на выходе некоторого элемента, то есть при . Тогда <tex> k \leqslant \dfrac{n \ge }{2 } </tex> выполняется неравенство , <tex> size_n-k \leqslant \dfrac{Bn}(K_{n}) \ge 2^{n} +1 </tex>. Таким образом,и

::<tex> size_{B}(K_{n}) \sim leqslant \dfrac{n}{2}2^{\dfrac{n}{2}+1} + (\dfrac{n}{2}+1)2^{\dfrac{n }{2}+2} + 2^n =2^n+O(n2^{\dfrac{n}{2}})</tex>.

Лемма доказанаС другой стороны, при <tex> n \geqslant 2 </tex> каждая конъюнкция реализуется на выходе некоторого элемента, то есть при <tex> n \geqslant 2 </tex> выполняется неравенство <tex> size_{B}(K_{n}) \geqslant 2^{n} </tex>.Таким образом,

|statement =Для любой функции <tex> f(x_{1}, ...\ldots, x_{n}) </tex> имеет место соотношение <tex> size_{B}(f)\lesssim 2^{n+1} </tex>.|proof = [[Файл:Synschemes_ NewTheorem2.png|400px|thumb|right|В верхней части схемы рис.2 все подсхемы, вычисляющие конъюнкции, заменили на <tex>K_n</tex>]]Пусть <tex> f(x_{1},...\ldots,x_{n}) </tex> {{---}} произвольная булева функция,<tex> f \ne 0 </tex>. Заменим в схеме (рис. 2) верхнюю часть схемы, реализующую конъюнкции <tex> K_{1} \vee K_{2} \vee ... \ldots \vee K_{s} </tex>, схемой, реализующей все конъюнкции из <tex> K_{n} </tex>. Тогда для любой такой функции <tex> f(x_{1},...\ldots,x_{n}) </tex> (не равной нулю) имеем

::<tex> size_{B}(f) \le leqslant size_{B}(K_{n})+s-1 \le leqslant size_{B}(K_{n})+2^{n}-1 \lesssim 2^{n+1} </tex>

==Метод синтеза схем К.Э.Шеннона<ref>[http://en.wikipedia.org/wiki/Claude_Shannon Claude Shannon]</ref>==

|statement =Для любой функции <tex> f(x_{1}, ...\ldots, x_{n}) </tex> имеет место соотношение <tex> size_{B}(f)\lesssim 12\frac dfrac {2^{n}}{n} </tex>.|proof = [[Файл:Synschemes -Theorem2.png|300px|thumb|right|Рис. 4]]Пусть <tex> f(x_{1},...\ldots,x_{n}) </tex> {{---}} произвольная булева функция. Рассмотрим разложение <tex> f </tex> по переменным <tex> x_{1},...\ldots,x_{nm} </tex>, где <tex> 1 \le leqslant m \le leqslant n </tex>:

<tex> f(x_{1},...\ldots,x_{n})= \bigvee x_displaystyle\bigvee_{(\sigma_{1},\wedgedotsc,\overlinesigma_{xm})}_x_{21}^{\wedgesigma_{x1}_{3}\wedge ... \dotsc\wedgex_{xm}_^{\sigma_{m} }\wedge f(x_\sigma_{m+1},\wedgedotsc,\overline{x}_sigma_{m+2}\wedge{x}_,x_{m+31},\wedge ... \wedge{x}_dotsc,x_{n}) </tex>.

'''Схема для функции <tex> f </tex> строится из трех подсхем: <tex> S_{1},S_{2},S_{3} </tex>. (рис. 4)'''

:1. Схема Система <tex> S_K_{m} (x_{1}^{\sigma_{1} },\dotsc,x_{m}^{\sigma_{m}}) </tex> реализует все содержит всевозможные конъюнкции из множества <tex> K_x_{m1} (x_^{\sigma_{1},...,}\wedge\dotsc\wedge x_{m}) ^{\sigma_{m}}</tex>. И схема <tex> S_{1} </tex>реализует все эти конъюнкции. В силу [[#Lemma2|Леммы леммы 2]] выполняется неравенство

::<tex> size_{B}(S_{1}) \le leqslant size_{B}(K_{m}) \lesssim 2^{m} </tex>.

:2. Схема <tex> S_{2} </tex> реализует систему <tex> F(x_{m+1}^{\sigma_{m+1}},...\ldots,x_{n}^{\sigma_{n}}) </tex> всех булевых функций от всевозможных наборов переменных <tex> x_{m+1},...\ldots,x_{n} </tex>. Другими словами, подсхема <tex> S_{2} </tex> вычисляет все булевы функции, зависящие от последних <tex> n - m </tex> переменных. В силу [[#Th1|Теоремы теоремы 1]]::<tex> size_{B}(S_{2}) \le leqslant (n-m)2^{n-m+1}2^{2^{n-m}} </tex>.

:3. Схема <tex> S_{3} </tex> производит "сборку" в соответствии с разложением функции <tex> f </tex>: для каждого набора <tex> \widetilde{\sigma}=(\sigma_{1},\dotsc,\sigma_{m}) </tex> реализуется конъюнкция

::<tex> x_{1}^{\wedge\overlinesigma_{x1}_{2}\wedge{x}_{3}\wedge ... dotsc\wedgex_{xm}_^{\sigma_{m}f(x_{m+1}\wedgef(\overline{x}_widetilde{m+2}\wedge{xsigma}_,x_{m+31},\wedge ... \wedge{x}_dotsc, x_{n}) </tex> (<tex> 2^{m} </tex> элементов конъюнкции) и образуется дизъюнкция таких конъюнкций (<tex> 2^{m}-1 </tex> элементов дизъюнкции).

Поэтому выполняется неравенство <tex> size_{B}(S_{3}) \le leqslant 2^{m} +2^{m} -1 </tex>. Таким образом,

::<tex> size_{B}(f) \le leqslant 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> k=n-m </tex>. Тогда

::<tex> 3 \cdot 2^{n-k} = 3 \cdot \fracdfrac{2^{n}}{n} </tex>,

::<tex> k \cdot 2^{k+1} \cdot 2^{2^{k}}=\log_{2}n\cdot (2n)\cdot 2^{\frac{n}{2}}</tex>,

::<tex> 3 \cdot 2^{n-k} = 3 \cdot \fracdfrac{2^{n}}{n} \cdot 2 </tex>,

::<tex> k \cdot 2^{k+1} \cdot 2^{2^{k}}=(\log_{2}n-1)\cdot n\cdot 2^{\fracdfrac{n}{2}}</tex>.

::<tex> 3 \cdot 2^{n-k} < 12 \cdot \frac dfrac {2^{n}}{n} </tex>,

::<tex> k\cdot 2^{k+1}\cdot 2^{2^{k}} \le leqslant (\log_{2}-1)\cdot n\cdot 2^{\fracdfrac{n}{2}} </tex>.

::<tex> size_{B}(n)\lesssim 12\frac dfrac {2^{n}}{2n} </tex>.}}

Теорема доказана == См.}}также ==*[[Реализация_булевой_функции_схемой_из_функциональных_элементов|Реализация булевой функции схемой из функциональных элементов]]*[[Метод_Лупанова_синтеза_схем|Метод Лупанова синтеза схем]]*[[Контактная_схема|Контактная схема]] == Примечания ==<references/>

== Литература Источники информации ==