Простейшие методы синтеза схем из функциональных элементов — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показана 21 промежуточная версия 6 участников) | |||
Строка 1: | Строка 1: | ||
{{Определение | {{Определение | ||
− | |definition= Синтезом [[Реализация булевой функции схемой из функциональных элементов|схемы из функциональных элементов]] называется процедура получения логической схемы, реализующей заданную логическую функцию. | + | |definition= '''Синтезом [[Реализация булевой функции схемой из функциональных элементов|схемы из функциональных элементов]]''' называется процедура получения логической схемы, реализующей заданную логическую функцию. |
}} | }} | ||
− | Приведем несколько простейших алгоритмов синтеза схем, реализующих произвольную функцию от <tex> n </tex> аргументов <tex> f(x_{1}, | + | Приведем несколько простейших алгоритмов синтеза схем, реализующих произвольную функцию от <tex> n </tex> аргументов <tex> f(x_{1}, \ldots, x_{n}) </tex>, в случае когда базис <tex> B = \{\neg, \lor, \land\} </tex>. |
==Метод синтеза, основанный на [[СДНФ|совершенной ДНФ]]== | ==Метод синтеза, основанный на [[СДНФ|совершенной ДНФ]]== | ||
Строка 12: | Строка 12: | ||
|about = 1 | |about = 1 | ||
|statement =Любой конъюнкт в СДНФ можно представить не более, чем <tex> 2n-1 </tex> элементами. | |statement =Любой конъюнкт в СДНФ можно представить не более, чем <tex> 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\ | + | |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> i </tex>-й множитель равен <tex> \bar{x}_{i} </tex>, то присоединяем к выходу <tex> i </tex> элемент отрицания и последовательно присоединяем к элементу конъюнкции, иначе просто присоединяем к "свободному" входу элемента конъюнкции. | Построим данную схему следующим образом: если <tex> i </tex>-й множитель равен <tex> \bar{x}_{i} </tex>, то присоединяем к выходу <tex> i </tex> элемент отрицания и последовательно присоединяем к элементу конъюнкции, иначе просто присоединяем к "свободному" входу элемента конъюнкции. | ||
Очевидно, что сложность построенной схемы <tex> size_{B}(f)= n+n-1 = 2n-1 </tex>. | Очевидно, что сложность построенной схемы <tex> size_{B}(f)= n+n-1 = 2n-1 </tex>. | ||
− | Поэтому <tex> size_{B}(f)\ | + | Поэтому <tex> size_{B}(f)\leqslant 2n-1 </tex>. |
Приведем пример для <tex> f=\bar{x}_{1}\wedge x_{2}\wedge x_{3} \wedge \bar{x}_{4}</tex> (рис. 1). | Приведем пример для <tex> f=\bar{x}_{1}\wedge x_{2}\wedge x_{3} \wedge \bar{x}_{4}</tex> (рис. 1). | ||
Строка 26: | Строка 26: | ||
|id = Th1 | |id = Th1 | ||
|about = 1 | |about = 1 | ||
− | |statement = Для любой функции <tex> f(x_{1}, | + | |statement = Для любой функции <tex> f(x_{1}, \ldots, x_{n}) </tex> имеет место неравенство <tex> size_{B}(f)\leqslant n2^{n+1} </tex> |
|proof = [[Файл:Synschemes Theorem1.png|250px|thumb|right|Рис. 2]] | |proof = [[Файл:Synschemes Theorem1.png|250px|thumb|right|Рис. 2]] | ||
− | Пусть <tex> f(x_{1}, | + | Пусть <tex> f(x_{1}, \ldots,x_{n}) </tex> {{---}} произвольная [[Определение булевой функции|булева функция]]. |
− | Если <tex> f = 0 </tex>, то схема строится в соответствии с представлением <tex> 0=x_{1}\wedge\overline{x}_{1} </tex>, то есть <tex> size_{B}(0) \ | + | Если <tex> f = 0 </tex>, то схема строится в соответствии с представлением <tex> 0=x_{1}\wedge\overline{x}_{1} </tex>, то есть <tex> size_{B}(0) \leqslant 2</tex>. |
Если <tex> f \ne 0 </tex>, то <tex> f </tex> может быть задана [[ДНФ|дизъюнктивной нормальной формой]] | Если <tex> f \ne 0 </tex>, то <tex> f </tex> может быть задана [[ДНФ|дизъюнктивной нормальной формой]] | ||
− | ::<tex> f(x_{1}, | + | ::<tex> f(x_{1}, \ldots,x_{n}) = K_{1} \vee K_{2} \vee \ldots \vee K_{s} </tex>, |
− | где <tex> s \ | + | где <tex> s \leqslant 2^{n} </tex> и каждая конъюнкция имеет вид |
− | ::<tex> K_{j}=x_{1}\wedge\overline{x}_{2}\wedge{x}_{3}\wedge | + | ::<tex> K_{j}=x_{1}\wedge\overline{x}_{2}\wedge{x}_{3}\wedge \ldots \wedge{x}_{i} </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> 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_{B}(f)\ | + | ::<tex> size_{B}(f)\leqslant s\cdot(2n-1)+s-1 < s\cdot(2n-1)+s = 2ns \leqslant n2^{n+1} </tex>. |
− | Таким образом, для любой функции <tex> f(x_{1}, | + | Таким образом, для любой функции <tex> f(x_{1}, \ldots,x_{n}) </tex> выполняется неравенство |
− | ::<tex> size_{B}(f(x_{1}, | + | ::<tex> size_{B}(f(x_{1}, \ldots,x_{n}))\leqslant n2^{n+1} </tex>. |
− | Поэтому <tex> size_{B}(f)\ | + | Поэтому <tex> size_{B}(f)\leqslant n2^{n+1} </tex>. |
}} | }} | ||
Строка 55: | Строка 55: | ||
{{Определение | {{Определение | ||
− | |definition= <tex> f(n) \sim g(n) </tex> означает, что <tex>f</tex> асимптотически эквивалентна <tex>g</tex>, то есть <tex>\lim\limits_{n \to \infty}\ | + | |definition= <tex> f(n) \sim g(n) </tex> означает, что <tex>f</tex> асимптотически эквивалентна <tex>g</tex>, то есть <tex>\lim\limits_{n \to \infty}\dfrac{f(n)}{g(n)} = 1</tex> |
}} | }} | ||
{{Определение | {{Определение | ||
+ | |definition= <tex> f(n) \lesssim g(n) </tex> означает, что <tex>\varlimsup\limits_{n \to \infty}\dfrac{f(n)}{g(n)} \leqslant 1</tex> | ||
+ | }} | ||
+ | |||
+ | {{Определение | ||
+ | |definition= | ||
+ | Пусть есть булева функция от <tex> n </tex> аргументов <tex> f : \lbrace0, 1\rbrace^n \rightarrow \lbrace0, 1\rbrace </tex> и набор из <tex> n </tex> булевых функций <tex> g_1 \dotsc g_n </tex>, таких что <tex> g_i :\lbrace0, 1\rbrace^{m_i} \rightarrow \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_{21},\dotsc,x_{2(m_2)}</tex> <tex>,\dotsc,x_{n1},\dotsc,x_{n(m_n)})</tex><tex>=f(g_1(x_{11},\dotsc,x_{1(m_1)}),g_2(x_{21},\dotsc,x_{2(m_2)}),\dotsc,g_n(x_{n1},\dotsc,x_{n(m_n)}))</tex> | |
}} | }} | ||
'''Примечание''' | '''Примечание''' | ||
− | + | ||
+ | Введем функцию | ||
+ | |||
+ | <tex> x^{\sigma} = \begin{cases} | ||
+ | x, \sigma =1;\\ | ||
+ | \overline{x}, \sigma =0 | ||
+ | \end{cases}</tex> | ||
{{Лемма | {{Лемма | ||
|id = Lemma2 | |id = Lemma2 | ||
|about = 2 | |about = 2 | ||
− | |statement = Пусть <tex> K_{n}(x_{1},\dotsc,x_{n}) </tex> {{---}} система всех <tex> 2^{n} </tex> конъюнкций <tex> x_{1}\wedge\dotsc\wedge x_{n}</tex>, тогда для <tex> K_{n} </tex> имеет место соотношение <tex> size_{B}(K_{n}) \sim 2^n </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> |
|proof = [[Файл:Synschemes Lemma2.png|250px|thumb|right|Рис. 3]] | |proof = [[Файл:Synschemes Lemma2.png|250px|thumb|right|Рис. 3]] | ||
− | + | Конъюнкции <tex> x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{n}^{\sigma_{n}}</tex> соответствуют функциям <tex> g </tex> из определения функции,<tex> K_{n} </tex> соответствует функции <tex> S </tex>, а конъюнкция функций <tex> g </tex> соответствует функции <tex> f </tex>. | |
− | + | Заметим, что на вход схемы подается определенный набор аргументов <tex> x_{1}^{\sigma_{1}},\dotsc,x_{n}^{\sigma_{n}} </tex>, то есть на выходе схемы будет результат конъюнкции этих аргументов. | |
− | + | Разделим цепочки конъюнкций на две части. Каждая конъюнкция <tex> x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{n}^{\sigma_{n}} </tex> может быть представлена в виде конъюнкции двух конъюнкций длины <tex> k </tex> и <tex> n-k </tex> (<tex> k </tex> мы выберем позже): | |
− | ::<tex> | + | ::<tex> x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{n}^{\sigma_{n}} = (x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{k}^{\sigma_{k}})(x_{k+1}^{\sigma_{k+1}}\wedge\dotsc\wedge x_{n}^{\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> x_{1}^{\sigma_{1}},\dotsc,x_{k}^{\sigma_{k}} </tex>, а правая часть - переменных <tex> x_{k+1}^{\sigma_{k+1}},\dotsc,x_{n}^{\sigma_{n}}</tex>. Следовательно, | |
− | ::<tex> size_{B}(K_{n}) \ | + | ::<tex> size_{B}(K_{n}) \leqslant size_{B}(K_{k}) + size_{B}(K_{n-k}) + 2^n </tex>. |
− | + | Так как по [[#Th1|теореме 1]] <tex> size_{B}(K_{k}) \leqslant k2^{k+1} </tex> , <tex> size_{B}(K_{n-k}) \leqslant (n-k)2^{n-k+1} </tex>,то | |
− | ::<tex> size_{B}(K_{n}) \ | + | ::<tex> size_{B}(K_{n}) \leqslant k2^{k+1} + (n-k)2^{n-k+1} + 2^n </tex>. |
− | С другой стороны, при <tex> n \ | + | Положим <tex> k=[\dfrac{n}{2}]</tex>. Тогда <tex> k \leqslant \dfrac{n}{2} </tex>, <tex> n-k \leqslant \dfrac{n}{2}+1 </tex> и |
+ | |||
+ | ::<tex> size_{B}(K_{n}) \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>. Таким образом, | ||
::<tex> size_{B}(K_{n}) \sim 2^n </tex>. | ::<tex> size_{B}(K_{n}) \sim 2^n </tex>. | ||
Строка 94: | Строка 110: | ||
|id = Th2 | |id = Th2 | ||
|about = 2 | |about = 2 | ||
− | |statement =Для любой функции <tex> f(x_{1}, | + | |statement =Для любой функции <tex> f(x_{1}, \ldots, x_{n}) </tex> имеет место соотношение <tex> size_{B}(f)\lesssim 2^{n+1} </tex>. |
− | |proof = Пусть <tex> f(x_{1}, | + | |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) \ | + | ::<tex> size_{B}(f) \leqslant size_{B}(K_{n})+s-1 \leqslant size_{B}(K_{n})+2^{n}-1 \lesssim 2^{n+1} </tex> |
Таким образом, | Таким образом, | ||
Строка 104: | Строка 122: | ||
}} | }} | ||
− | ==Метод синтеза схем [ | + | ==Метод синтеза схем К.Э.Шеннона <ref>[http://en.wikipedia.org/wiki/Claude_Shannon Claude Shannon]</ref>== |
{{Теорема | {{Теорема | ||
|id = Th3 | |id = Th3 | ||
|about = 3 | |about = 3 | ||
− | |statement =Для любой функции <tex> f(x_{1}, | + | |statement =Для любой функции <tex> f(x_{1}, \ldots, x_{n}) </tex> имеет место соотношение <tex> size_{B}(f)\lesssim 12\dfrac {2^{n}}{n} </tex>. |
|proof = [[Файл:Synschemes-Theorem2.png|300px|thumb|right|Рис. 4]] | |proof = [[Файл:Synschemes-Theorem2.png|300px|thumb|right|Рис. 4]] | ||
− | Пусть <tex> f(x_{1}, | + | Пусть <tex> f(x_{1}, \ldots,x_{n}) </tex> {{---}} произвольная булева функция. Рассмотрим разложение <tex> f </tex> по переменным <tex> x_{1}, \ldots,x_{m} </tex>, где <tex> 1 \leqslant m \leqslant n </tex>: |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | <tex>f(x_{1}, \ldots,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(x_{1}, | ||
'''Схема для функции <tex> f </tex> строится из трех подсхем: <tex> S_{1},S_{2},S_{3} </tex>. (рис. 4)''' | '''Схема для функции <tex> f </tex> строится из трех подсхем: <tex> S_{1},S_{2},S_{3} </tex>. (рис. 4)''' | ||
− | :1. | + | :1. Система <tex> K_{m} (x_{1}^{\sigma_{1}},\dotsc,x_{m}^{\sigma_{m}}) </tex> содержит всевозможные конъюнкции <tex>x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{m}^{\sigma_{m}}</tex>. И схема <tex> S_{1} </tex> реализует все эти конъюнкции. В силу [[#Lemma2|леммы 2]] выполняется неравенство |
− | ::<tex> size_{B}(S_{1}) \ | + | ::<tex> size_{B}(S_{1}) \leqslant size_{B}(K_{m}) \lesssim 2^{m} </tex>. |
− | :2. Схема <tex> S_{2} </tex> реализует систему <tex> F(x_{m+1}, | + | :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}) \ | + | ::<tex> size_{B}(S_{2}) \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> реализуется конъюнкция | :3. Схема <tex> S_{3} </tex> производит "сборку" в соответствии с разложением функции <tex> f </tex>: для каждого набора <tex> \widetilde{\sigma}=(\sigma_{1},\dotsc,\sigma_{m}) </tex> реализуется конъюнкция | ||
Строка 137: | Строка 146: | ||
::<tex> 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> 2^{m}-1 </tex> элементов дизъюнкции). | ::<tex> 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> 2^{m}-1 </tex> элементов дизъюнкции). | ||
− | Поэтому выполняется неравенство <tex> size_{B}(S_{3}) \ | + | Поэтому выполняется неравенство <tex> size_{B}(S_{3}) \leqslant 2^{m} +2^{m} -1 </tex>. Таким образом, |
− | ::<tex> size_{B}(f) \ | + | ::<tex> size_{B}(f) \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> size_{B}(f) \lesssim 3 \cdot 2^{n-k} +k2^{k+1}2^{2^{k}} </tex>. | ::<tex> size_{B}(f) \lesssim 3 \cdot 2^{n-k} +k2^{k+1}2^{2^{k}} </tex>. | ||
Строка 147: | Строка 156: | ||
Заметим, что второе слагаемое "очень быстро" растет с ростом <tex> k </tex>, а первое слагаемое убывает с ростом <tex> k </tex> медленней. Поэтому следует взять такое значение <tex> k </tex>, при котором первое и второе слагаемые приблизительно равны, и потом немного уменьшить <tex> k </tex>. Тогда второе слагаемое "сильно" уменьшится, а первое "не очень сильно" возрастет. Возьмем, например, <tex> k=\log_{2}n </tex>. Тогда | Заметим, что второе слагаемое "очень быстро" растет с ростом <tex> k </tex>, а первое слагаемое убывает с ростом <tex> k </tex> медленней. Поэтому следует взять такое значение <tex> k </tex>, при котором первое и второе слагаемые приблизительно равны, и потом немного уменьшить <tex> k </tex>. Тогда второе слагаемое "сильно" уменьшится, а первое "не очень сильно" возрастет. Возьмем, например, <tex> k=\log_{2}n </tex>. Тогда | ||
− | ::<tex> 3 \cdot 2^{n-k} = 3 \cdot \ | + | ::<tex> 3 \cdot 2^{n-k} = 3 \cdot \dfrac{2^{n}}{n} </tex>, |
− | ::<tex> k \cdot 2^{k+1} \cdot 2^{2^{k}}=\log_{2}n\cdot (2n)\cdot 2^ | + | ::<tex> k \cdot 2^{k+1} \cdot 2^{2^{k}}=\log_{2}n\cdot (2n)\cdot 2^{n}</tex>, |
то есть получили "слишком много". Возьмем <tex> k </tex> на единицу меньше: <tex> k=\log_{2}n-1 </tex>. Тогда | то есть получили "слишком много". Возьмем <tex> k </tex> на единицу меньше: <tex> k=\log_{2}n-1 </tex>. Тогда | ||
− | ::<tex> 3 \cdot 2^{n-k} = 3 \cdot \ | + | ::<tex> 3 \cdot 2^{n-k} = 3 \cdot \dfrac{2^{n}}{n} \cdot 2 </tex>, |
− | ::<tex> k \cdot 2^{k+1} \cdot 2^{2^{k}}=(\log_{2}n-1)\cdot n\cdot 2^{\ | + | ::<tex> k \cdot 2^{k+1} \cdot 2^{2^{k}}=(\log_{2}n-1)\cdot n\cdot 2^{\dfrac{n}{2}}</tex>. |
Вспомним теперь, что <tex> k </tex> должно быть целым числом, и положим <tex> k=[\log_{2}n-1] </tex>. Тогда | Вспомним теперь, что <tex> k </tex> должно быть целым числом, и положим <tex> k=[\log_{2}n-1] </tex>. Тогда | ||
<tex> n-k < n- \log_{2} + 2</tex>, | <tex> n-k < n- \log_{2} + 2</tex>, | ||
− | ::<tex> 3 \cdot 2^{n-k} < 12 \cdot \ | + | ::<tex> 3 \cdot 2^{n-k} < 12 \cdot \dfrac {2^{n}}{n} </tex>, |
− | ::<tex> k\cdot 2^{k+1}\cdot 2^{2^{k}} \ | + | ::<tex> k\cdot 2^{k+1}\cdot 2^{2^{k}} \leqslant (\log_{2}-1)\cdot n\cdot 2^{\dfrac{n}{2}} </tex>. |
При этом выборе <tex> k </tex> окончательно имеем | При этом выборе <tex> k </tex> окончательно имеем | ||
− | ::<tex> size_{B}(n)\lesssim 12\ | + | ::<tex> size_{B}(n)\lesssim 12\dfrac {2^{n}}{n} </tex>. |
}} | }} | ||
− | == | + | |
+ | == См. также == | ||
+ | *[[Реализация_булевой_функции_схемой_из_функциональных_элементов|Реализация булевой функции схемой из функциональных элементов]] | ||
+ | *[[Метод_Лупанова_синтеза_схем|Метод Лупанова синтеза схем]] | ||
+ | *[[Контактная_схема|Контактная схема]] | ||
+ | |||
+ | == Примечания == | ||
+ | <references/> | ||
+ | |||
+ | == Источники информации == | ||
* Яблонский С.В. Введение в дискретную математику. — 4-е изд. — М.: Высшая школа, 2003. — 384 с. — ISBN 5-06-004681-8 | * Яблонский С.В. Введение в дискретную математику. — 4-е изд. — М.: Высшая школа, 2003. — 384 с. — ISBN 5-06-004681-8 | ||
[[Категория:Дискретная математика и алгоритмы]] | [[Категория:Дискретная математика и алгоритмы]] | ||
[[Категория: Схемы из функциональных элементов ]] | [[Категория: Схемы из функциональных элементов ]] |
Текущая версия на 19:29, 4 сентября 2022
Определение: |
Синтезом схемы из функциональных элементов называется процедура получения логической схемы, реализующей заданную логическую функцию. |
Приведем несколько простейших алгоритмов синтеза схем, реализующих произвольную функцию от аргументов , в случае когда базис .
Метод синтеза, основанный на совершенной ДНФ
Лемма (1): |
Любой конъюнкт в СДНФ можно представить не более, чем элементами. |
Доказательство: |
Построим данную схему следующим образом: если -й множитель равен , то присоединяем к выходу элемент отрицания и последовательно присоединяем к элементу конъюнкции, иначе просто присоединяем к "свободному" входу элемента конъюнкции.Очевидно, что сложность построенной схемы .Поэтому Приведем пример для . (рис. 1). |
Теорема (1): |
Для любой функции имеет место неравенство |
Доказательство: |
Пусть булева функция. — произвольнаяЕсли , то схема строится в соответствии с представлением , то есть .Если дизъюнктивной нормальной формой , то может быть задана
где и каждая конъюнкция имеет видСхема леммой 1 имеет сложность не более ) и цепочки из элемента дизъюнкции с свободными входами. Свободные входы этой цепочки присоединяются к выходам схем для конъюнкций .(рис. 2) Имеем для состоит из конъюнкций (каждая из них в соответствии с
Таким образом, для любой функции выполняется неравенство
|
Метод синтеза, основанный на более компактной реализации множества всех конъюнкций
Определение: |
означает, что асимптотически эквивалентна , то есть |
Определение: |
означает, что |
Определение: |
Пусть есть булева функция от | аргументов и набор из булевых функций , таких что , где . Тогда системой булевых функций называется функция от всех аргументов функций , которая определяется как
Примечание
Введем функцию
Лемма (2): |
Пусть — система всех конъюнкций , где каждому соответствует свой набор , тогда для имеет место соотношение |
Доказательство: |
Конъюнкции соответствуют функциям из определения функции, соответствует функции , а конъюнкция функций соответствует функции .Заметим, что на вход схемы подается определенный набор аргументов , то есть на выходе схемы будет результат конъюнкции этих аргументов.Разделим цепочки конъюнкций на две части. Каждая конъюнкция может быть представлена в виде конъюнкции двух конъюнкций длины и ( мы выберем позже):
Поэтому схема для теореме 1 (рис. 3). Левая часть схемы считает конъюнкцию переменных , а правая часть - переменных . Следовательно, может быть образована из схем для и и системы из элементов конъюнкции, осуществляющих вышеприведенную операцию, как показано в
Так как по теореме 1 , ,то
Положим . Тогда , и
С другой стороны, при каждая конъюнкция реализуется на выходе некоторого элемента, то есть при выполняется неравенство . Таким образом,
|
Теорема (2): |
Для любой функции имеет место соотношение . |
Доказательство: |
Пусть — произвольная булева функция, . Заменим в схеме (рис. 2) верхнюю часть схемы, реализующую конъюнкции , схемой, реализующей все конъюнкции из . Тогда для любой такой функции (не равной нулю) имеемТаким образом, |
Метод синтеза схем К.Э.Шеннона [1]
Теорема (3): |
Для любой функции имеет место соотношение . |
Доказательство: |
Пусть — произвольная булева функция. Рассмотрим разложение по переменным , где :. Схема для функции строится из трех подсхем: . (рис. 4)
Поэтому выполняется неравенство . Таким образом,
Положим . Тогда
Заметим, что второе слагаемое "очень быстро" растет с ростом , а первое слагаемое убывает с ростом медленней. Поэтому следует взять такое значение , при котором первое и второе слагаемые приблизительно равны, и потом немного уменьшить . Тогда второе слагаемое "сильно" уменьшится, а первое "не очень сильно" возрастет. Возьмем, например, . Тогда
то есть получили "слишком много". Возьмем на единицу меньше: . Тогда
Вспомним теперь, что должно быть целым числом, и положим . Тогда ,
При этом выборе окончательно имеем
|
См. также
Примечания
Источники информации
- Яблонский С.В. Введение в дискретную математику. — 4-е изд. — М.: Высшая школа, 2003. — 384 с. — ISBN 5-06-004681-8