Простейшие методы синтеза схем из функциональных элементов — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Незначительные исправления)
м (rollbackEdits.php mass rollback)
 
(не показано 39 промежуточных версий 8 участников)
Строка 1: Строка 1:
Приведем несколько простейших алгоритмов синтеза [[Реализация булевой функции схемой из функциональных элементов|схем]], в случае когда базис состоит из элементов: инвертора, конъюнктора и дизъюнктора.
+
{{Определение
 +
 
 +
|definition= '''Синтезом [[Реализация булевой функции схемой из функциональных элементов|схемы из функциональных элементов]]''' называется процедура получения логической схемы, реализующей заданную логическую функцию.
 +
}}
 +
 
 +
Приведем несколько простейших алгоритмов синтеза схем, реализующих произвольную функцию от <tex> n </tex> аргументов <tex> f(x_{1}, \ldots, x_{n}) </tex>, в случае когда базис <tex> B = \{\neg, \lor, \land\} </tex>.
  
 
==Метод синтеза, основанный на [[СДНФ|совершенной ДНФ]]==
 
==Метод синтеза, основанный на [[СДНФ|совершенной ДНФ]]==
Строка 6: Строка 11:
 
|id = Lemma1
 
|id = Lemma1
 
|about = 1
 
|about = 1
|statement =  
+
|statement =Любой конъюнкт в СДНФ можно представить не более, чем <tex> 2n-1 </tex> элементами.
Для любой конъюнкции <tex> x_{1}\wedge ... \wedge x_{n} </tex> <tex> Size_{B}(x_{1} ... x_{n})\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>.]]  
|proof =  [[Файл:Synschemes Lemma1.png|250px|thumb|right|Рис. 1]]  
+
Построим данную схему следующим образом: если <tex> i </tex>-й множитель равен <tex> \bar{x}_{i} </tex>, то присоединяем к выходу <tex> i </tex> элемент отрицания и последовательно присоединяем к элементу конъюнкции, иначе просто присоединяем к "свободному" входу элемента конъюнкции.
Построим данную схему следующим образом: возьмем <tex> n </tex> элементов отрицания, присоединенных к выходам, и цепочки из элементов конъюнкции,    имеющих <tex> n </tex> "свободных" входов.  
 
  
Каждый <tex> i </tex>-й вход этой цепочки присоединяется к входу схемы, если <tex> i </tex>-й множитель равен <tex> x_{i} </tex>, или к выходу <tex> i </tex>-го элемента отрицания, если <tex> i </tex>-й множитель равен <tex> \overline{x}_{i} </tex>.(рис. 1)
+
Очевидно, что сложность построенной схемы <tex> size_{B}(f)= n+n-1 = 2n-1 </tex>.  
  
Очевидно, что сложность построенной схемы равна <tex> 2n-1 </tex>.  
+
Поэтому <tex> size_{B}(f)\leqslant 2n-1 </tex>.
  
Поэтому <tex> Size_{B}(x_{1} ...x_{n})\le 2n-1 </tex>.
+
Приведем пример для <tex> f=\bar{x}_{1}\wedge x_{2}\wedge x_{3} \wedge \bar{x}_{4}</tex> (рис. 1).
  
Лемма доказана.
 
 
}}
 
}}
  
Строка 23: Строка 26:
 
|id = Th1  
 
|id = Th1  
 
|about = 1
 
|about = 1
|statement = Имеет место неравенство <tex> Size_{B}(n)\le n2^{n+1} </tex>
+
|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},...,x_{n}) </tex> произвольная [[Определение булевой функции|булева функция]]. Если <tex> f \ne 0 </tex>, то <tex> f </tex> может быть задана нормальной дизъюнктивной формой
+
Пусть <tex> f(x_{1}, \ldots,x_{n}) </tex> {{---}} произвольная [[Определение булевой функции|булева функция]].
  
::<tex> f(x_{1},...,x_{n}) = K_{1} \vee K_{2} \vee ... \vee K_{s} </tex>,
+
Если <tex> f = 0 </tex>, то схема строится в соответствии с представлением <tex> 0=x_{1}\wedge\overline{x}_{1} </tex>, то есть <tex> size_{B}(0) \leqslant 2</tex>.
  
где <tex> s \le 2^{n} </tex> и каждая конъюнкция имеет вид
+
Если <tex> f \ne 0 </tex>, то <tex> f </tex> может быть задана [[ДНФ|дизъюнктивной нормальной формой]]
  
::<tex> K_{j}=x_{1}\wedge\overline{x}_{2}\wedge{x}_{3}\wedge ... \wedge{x}_{i} </tex>
+
::<tex> f(x_{1}, \ldots,x_{n}) = K_{1} \vee K_{2} \vee \ldots \vee K_{s} </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 \leqslant 2^{n} </tex> и каждая конъюнкция имеет вид
  
::<tex> Size_{B}(n)\le s(2n-1)+s-1 < s(2n-1)+s = 2ns \le n2^{n+1} </tex>.
+
::<tex> K_{j}=x_{1}\wedge\overline{x}_{2}\wedge{x}_{3}\wedge \ldots \wedge{x}_{i} </tex>
  
Если <tex> f = 0 </tex>, то схема строится в соответствии с представлением <tex> 0=x_{1}\wedge\overline{x}_{1} </tex>, то есть<tex> Size_{B}(0) \le 2</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> f(x_{1},...,x_{n}) </tex> выполняется неравенство
+
::<tex> size_{B}(f)\leqslant s\cdot(2n-1)+s-1 < s\cdot(2n-1)+s = 2ns \leqslant n2^{n+1} </tex>.
  
::<tex> Size_{B}(f(x_{1},...,x_{n}))\le n2^{n+1} </tex>.
+
Таким образом, для любой функции <tex> f(x_{1}, \ldots,x_{n}) </tex> выполняется неравенство
  
Поэтому <tex> Size_{B}(n)\le n2^{n+1} </tex>.
+
::<tex> size_{B}(f(x_{1}, \ldots,x_{n}))\leqslant n2^{n+1} </tex>.
  
Теорема доказана.
+
Поэтому <tex> size_{B}(f)\leqslant n2^{n+1} </tex>.
 +
}}
  
 +
==Метод синтеза, основанный на более компактной реализации множества всех конъюнкций==
 +
 +
{{Определение
 +
 +
|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> 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}\wedge\overline{x}_{2}\wedge{x}_{3}\wedge ... \wedge{x}_{i} </tex> может быть представлена в виде конъюнкции двух конъюнкций длины <tex> k </tex> и <tex> n-k </tex>:
+
Конъюнкции <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}\wedge\overline{x}_{2}\wedge{x}_{3}\wedge ... \wedge{x}_{n} = (x_{1}\wedge\overline{x}_{2}\wedge{x}_{3}\wedge ... \wedge{x}_{k})(x_{k+1}\wedge\overline{x}_{k+2}\wedge{x}_{k+3}\wedge ... \wedge{x}_{n}) </tex>.
+
Заметим, что на вход схемы подается определенный набор аргументов <tex> x_{1}^{\sigma_{1}},\dotsc,x_{n}^{\sigma_{n}} </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> x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{n}^{\sigma_{n}} </tex> может быть представлена в виде конъюнкции двух конъюнкций длины <tex> k </tex> и <tex> n-k </tex> (<tex> k </tex> мы выберем позже):
  
::<tex> Size_{B}(K_{n}) \le Size_{B}(K_{k}) + Size_{B}(K_{n-k}) + 2^n </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>.
  
Так как по [[#Th1|Теореме 1]] <tex> Size_{B}(K_{n}) \le k2^{k+1} </tex> , <tex> Size_{B}(K_{n-k}) \le (n-k)2^{n-k+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> Size_{B}(K_{n}) \le k2^{k+1} + (n-k)2^{n-k+1} + 2^n </tex>.
+
::<tex> size_{B}(K_{n}) \leqslant size_{B}(K_{k}) + size_{B}(K_{n-k}) + 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> и
+
Так как по [[#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}) \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> size_{B}(K_{n}) \leqslant k2^{k+1} + (n-k)2^{n-k+1} + 2^n </tex>.
  
С другой стороны, при <tex> n \ge 2 </tex> каждая конъюнкция реализуется на выходе некоторого элемента, то есть при <tex> n \ge 2 </tex> выполняется неравенство <tex> Size_{B}(K_{n}) \ge 2^{n} </tex>. Таким образом,
+
Положим <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}) \sim 2^n </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>.
 
}}
 
}}
  
Строка 83: Строка 110:
 
|id = Th2
 
|id = Th2
 
|about = 2
 
|about = 2
|statement = Имеет место соотношение <tex> Size_{B}(n)\lesssim 2^{n+1} </tex>.
+
|statement =Для любой функции <tex> f(x_{1}, \ldots, 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>. Заменим в схеме верхнюю часть схемы, реализующую конъюнкции <tex> K_{1} \vee K_{2} \vee ... \vee K_{s} </tex>, схемой, реализующей все конъюнкции из <tex> K_{n} </tex>. Тогда для любой такой функции <tex> f(x_{1},...,x_{n}) </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 L(K_{n})+s-1 \le L(K_{n})+2^{n}-1 \lesssim 2^{n+1} </tex>
+
::<tex> size_{B}(f) \leqslant size_{B}(K_{n})+s-1 \leqslant size_{B}(K_{n})+2^{n}-1 \lesssim 2^{n+1} </tex>
  
 
Таким образом,
 
Таким образом,
  
::<tex> Size_{B}(n)\lesssim 2^{n+1}. </tex>
+
::<tex> size_{B}(f)\lesssim 2^{n+1}. </tex>
 
 
Теорема доказана.
 
 
}}
 
}}
  
==Метод синтеза схем, предложенный К.Э.Шенноном==
+
==Метод синтеза схем К.Э.Шеннона <ref>[http://en.wikipedia.org/wiki/Claude_Shannon Claude Shannon]</ref>==
  
 
{{Теорема
 
{{Теорема
 
|id = Th3
 
|id = Th3
 
|about = 3
 
|about = 3
|statement = Имеет место соотношение <tex> Size_{B}(n)\lesssim 12\frac {2^{n}}{2} </tex>.
+
|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},...,x_{n}) </tex> произвольная булева функция. Рассмотрим разложение <tex> f </tex> по переменным <tex> x_{1},...,x_{n} </tex>, где <tex> 1 \le m \le n </tex>:
+
Пусть <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},...,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>.
+
<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 </tex> строится из трех подсхем: <tex> S_{1},S_{2},S_{3} </tex>. (рис. 4)
+
'''Схема для функции <tex> f </tex> строится из трех подсхем: <tex> S_{1},S_{2},S_{3} </tex>. (рис. 4)'''
  
:1. Схема  <tex> S_{1} </tex> реализует все конъюнкции из множества <tex> K_{m} (x_{1},...,x_{m}) </tex>. В силу [[#Lemma2|Леммы 2]] выполняется неравенство
+
: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}) \le Size_{B}(K_{m}) \lesssim 2^{m} </tex>.
+
::<tex> size_{B}(S_{1}) \leqslant size_{B}(K_{m}) \lesssim 2^{m} </tex>.
  
:2. Схема <tex> S_{2} </tex> реализует <tex> F(x_{m+1},...,x_{n}) </tex> всех булевых функций от переменных <tex> x_{m+1},...,x_{n} </tex>. В силу [[#Th1|Теоремы 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}) \le (n-m)2^{n-m+1}2^{2^{n-m}} </tex>.
+
::<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>: для каждого набора реализуется конъюнкция
+
:3. Схема <tex> S_{3} </tex> производит "сборку" в соответствии с разложением функции <tex> f </tex>: для каждого набора <tex> \widetilde{\sigma}=(\sigma_{1},\dotsc,\sigma_{m}) </tex> реализуется конъюнкция
  
::<tex> 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> (<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}) \le 2^{m} +2^{m} -1 </tex>. Таким образом,
+
Поэтому выполняется неравенство <tex> size_{B}(S_{3}) \leqslant 2^{m} +2^{m} -1 </tex>. Таким образом,
  
::<tex> Size_{B}(S) \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> 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> k=n-m </tex>. Тогда  
  
::<tex>  Size_{B}(n) \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>.
  
 
Заметим, что второе слагаемое "очень быстро" растет с ростом <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 \frac{2^{n}}{n} </tex>,
+
::<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^{\frac{n}{2}}</tex>,
+
::<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 \frac{2^{n}}{n} \cdot 2 </tex>,
+
::<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^{\frac{n}{2}}</tex>.
+
::<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 \frac {2^{n}}{n} </tex>,
+
::<tex> 3 \cdot 2^{n-k} < 12 \cdot \dfrac {2^{n}}{n} </tex>,
  
::<tex> k\cdot 2^{k+1}\cdot 2^{2^{k}} \le (\log_{2}-1)\cdot n\cdot 2^{\frac{n}{2}} </tex>.
+
::<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\frac {2^{n}}{2} </tex>.
+
::<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

Определение:
Синтезом схемы из функциональных элементов называется процедура получения логической схемы, реализующей заданную логическую функцию.


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

Метод синтеза, основанный на совершенной ДНФ

Лемма (1):
Любой конъюнкт в СДНФ можно представить не более, чем [math] 2n-1 [/math] элементами.
Доказательство:
[math]\triangleright[/math]
Рис 1. Схема для [math] \bar{x}_{1}\wedge x_{2}\wedge x_{3} \wedge \bar{x}_{4}[/math]. Сложность построенной схемы [math]size_{B}(f)=2+3=5\leqslant 7[/math].

Построим данную схему следующим образом: если [math] i [/math]-й множитель равен [math] \bar{x}_{i} [/math], то присоединяем к выходу [math] i [/math] элемент отрицания и последовательно присоединяем к элементу конъюнкции, иначе просто присоединяем к "свободному" входу элемента конъюнкции.

Очевидно, что сложность построенной схемы [math] size_{B}(f)= n+n-1 = 2n-1 [/math].

Поэтому [math] size_{B}(f)\leqslant 2n-1 [/math].

Приведем пример для [math] f=\bar{x}_{1}\wedge x_{2}\wedge x_{3} \wedge \bar{x}_{4}[/math] (рис. 1).
[math]\triangleleft[/math]
Теорема (1):
Для любой функции [math] f(x_{1}, \ldots, x_{n}) [/math] имеет место неравенство [math] size_{B}(f)\leqslant n2^{n+1} [/math]
Доказательство:
[math]\triangleright[/math]
Рис. 2

Пусть [math] f(x_{1}, \ldots,x_{n}) [/math] — произвольная булева функция.

Если [math] f = 0 [/math], то схема строится в соответствии с представлением [math] 0=x_{1}\wedge\overline{x}_{1} [/math], то есть [math] size_{B}(0) \leqslant 2[/math].

Если [math] f \ne 0 [/math], то [math] f [/math] может быть задана дизъюнктивной нормальной формой

[math] f(x_{1}, \ldots,x_{n}) = K_{1} \vee K_{2} \vee \ldots \vee K_{s} [/math],

где [math] s \leqslant 2^{n} [/math] и каждая конъюнкция имеет вид

[math] K_{j}=x_{1}\wedge\overline{x}_{2}\wedge{x}_{3}\wedge \ldots \wedge{x}_{i} [/math]

Схема [math] S [/math] для [math] f [/math] состоит из конъюнкций [math] K_{j} [/math] (каждая из них в соответствии с леммой 1 имеет сложность не более [math] 2n-1 [/math]) и цепочки из [math] s-1 [/math] элемента дизъюнкции с [math] s [/math] свободными входами. Свободные входы этой цепочки присоединяются к выходам схем для конъюнкций [math] K_{j} [/math].(рис. 2) Имеем

[math] size_{B}(f)\leqslant s\cdot(2n-1)+s-1 \lt s\cdot(2n-1)+s = 2ns \leqslant n2^{n+1} [/math].

Таким образом, для любой функции [math] f(x_{1}, \ldots,x_{n}) [/math] выполняется неравенство

[math] size_{B}(f(x_{1}, \ldots,x_{n}))\leqslant n2^{n+1} [/math].
Поэтому [math] size_{B}(f)\leqslant n2^{n+1} [/math].
[math]\triangleleft[/math]

Метод синтеза, основанный на более компактной реализации множества всех конъюнкций

Определение:
[math] f(n) \sim g(n) [/math] означает, что [math]f[/math] асимптотически эквивалентна [math]g[/math], то есть [math]\lim\limits_{n \to \infty}\dfrac{f(n)}{g(n)} = 1[/math]


Определение:
[math] f(n) \lesssim g(n) [/math] означает, что [math]\varlimsup\limits_{n \to \infty}\dfrac{f(n)}{g(n)} \leqslant 1[/math]


Определение:
Пусть есть булева функция от [math] n [/math] аргументов [math] f : \lbrace0, 1\rbrace^n \rightarrow \lbrace0, 1\rbrace [/math] и набор из [math] n [/math] булевых функций [math] g_1 \dotsc g_n [/math], таких что [math] g_i :\lbrace0, 1\rbrace^{m_i} \rightarrow \lbrace0, 1\rbrace [/math], где [math] i=1,\dotsc, n[/math]. Тогда системой булевых функций называется функция [math] S [/math] от всех аргументов функций [math] g_i[/math], которая определяется как [math] S(x_{11},\dotsc,x_{1(m_1)},x_{21},\dotsc,x_{2(m_2)}[/math] [math],\dotsc,x_{n1},\dotsc,x_{n(m_n)})[/math][math]=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)}))[/math]

Примечание

Введем функцию

[math] x^{\sigma} = \begin{cases} x, \sigma =1;\\ \overline{x}, \sigma =0 \end{cases}[/math]

Лемма (2):
Пусть [math] K_{n}(\lbrace x_{1}^{\sigma_{1}},\dotsc,x_{n}^{\sigma_{n}} \rbrace^{2^n}_{i=1}) [/math] — система всех [math] 2^{n} [/math] конъюнкций [math] x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{n}^{\sigma_{n}}[/math], где каждому [math] i [/math] соответствует свой набор [math] \lbrace \sigma_{1},\dotsc,\sigma_{n} \rbrace [/math], тогда для [math] K_{n} [/math] имеет место соотношение [math] size_{B}(K_{n}) \sim 2^n [/math]
Доказательство:
[math]\triangleright[/math]
Рис. 3

Конъюнкции [math] x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{n}^{\sigma_{n}}[/math] соответствуют функциям [math] g [/math] из определения функции,[math] K_{n} [/math] соответствует функции [math] S [/math], а конъюнкция функций [math] g [/math] соответствует функции [math] f [/math].

Заметим, что на вход схемы подается определенный набор аргументов [math] x_{1}^{\sigma_{1}},\dotsc,x_{n}^{\sigma_{n}} [/math], то есть на выходе схемы будет результат конъюнкции этих аргументов.

Разделим цепочки конъюнкций на две части. Каждая конъюнкция [math] x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{n}^{\sigma_{n}} [/math] может быть представлена в виде конъюнкции двух конъюнкций длины [math] k [/math] и [math] n-k [/math] ([math] k [/math] мы выберем позже):

[math] 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}}) [/math].

Поэтому схема для [math] K_{n} [/math] может быть образована из схем для [math] K_{k}(x_{1}^{\sigma_{1}},\dotsc,x_{k}^{\sigma_{k}}) [/math] и [math] K_{n-k}(x_{k+1}^{\sigma_{k+1}},\dotsc,x_{n}^{\sigma_{n}}) [/math] и системы из [math] 2^n [/math] элементов конъюнкции, осуществляющих вышеприведенную операцию, как показано в теореме 1 (рис. 3). Левая часть схемы считает конъюнкцию переменных [math] x_{1}^{\sigma_{1}},\dotsc,x_{k}^{\sigma_{k}} [/math], а правая часть - переменных [math] x_{k+1}^{\sigma_{k+1}},\dotsc,x_{n}^{\sigma_{n}}[/math]. Следовательно,

[math] size_{B}(K_{n}) \leqslant size_{B}(K_{k}) + size_{B}(K_{n-k}) + 2^n [/math].

Так как по теореме 1 [math] size_{B}(K_{k}) \leqslant k2^{k+1} [/math] , [math] size_{B}(K_{n-k}) \leqslant (n-k)2^{n-k+1} [/math],то

[math] size_{B}(K_{n}) \leqslant k2^{k+1} + (n-k)2^{n-k+1} + 2^n [/math].

Положим [math] k=[\dfrac{n}{2}][/math]. Тогда [math] k \leqslant \dfrac{n}{2} [/math], [math] n-k \leqslant \dfrac{n}{2}+1 [/math] и

[math] 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}})[/math].

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

[math] size_{B}(K_{n}) \sim 2^n [/math].
[math]\triangleleft[/math]
Теорема (2):
Для любой функции [math] f(x_{1}, \ldots, x_{n}) [/math] имеет место соотношение [math] size_{B}(f)\lesssim 2^{n+1} [/math].
Доказательство:
[math]\triangleright[/math]
В верхней части схемы рис.2 все подсхемы, вычисляющие конъюнкции, заменили на [math]K_n[/math]

Пусть [math] f(x_{1}, \ldots,x_{n}) [/math] — произвольная булева функция, [math] f \ne 0 [/math]. Заменим в схеме (рис. 2) верхнюю часть схемы, реализующую конъюнкции [math] K_{1} \vee K_{2} \vee \ldots \vee K_{s} [/math], схемой, реализующей все конъюнкции из [math] K_{n} [/math]. Тогда для любой такой функции [math] f(x_{1}, \ldots,x_{n}) [/math] (не равной нулю) имеем

[math] size_{B}(f) \leqslant size_{B}(K_{n})+s-1 \leqslant size_{B}(K_{n})+2^{n}-1 \lesssim 2^{n+1} [/math]

Таким образом,

[math] size_{B}(f)\lesssim 2^{n+1}. [/math]
[math]\triangleleft[/math]

Метод синтеза схем К.Э.Шеннона [1]

Теорема (3):
Для любой функции [math] f(x_{1}, \ldots, x_{n}) [/math] имеет место соотношение [math] size_{B}(f)\lesssim 12\dfrac {2^{n}}{n} [/math].
Доказательство:
[math]\triangleright[/math]
Рис. 4

Пусть [math] f(x_{1}, \ldots,x_{n}) [/math] — произвольная булева функция. Рассмотрим разложение [math] f [/math] по переменным [math] x_{1}, \ldots,x_{m} [/math], где [math] 1 \leqslant m \leqslant n [/math]:

[math]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}) [/math].

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

1. Система [math] K_{m} (x_{1}^{\sigma_{1}},\dotsc,x_{m}^{\sigma_{m}}) [/math] содержит всевозможные конъюнкции [math]x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{m}^{\sigma_{m}}[/math]. И схема [math] S_{1} [/math] реализует все эти конъюнкции. В силу леммы 2 выполняется неравенство
[math] size_{B}(S_{1}) \leqslant size_{B}(K_{m}) \lesssim 2^{m} [/math].
2. Схема [math] S_{2} [/math] реализует систему [math] F(x_{m+1}^{\sigma_{m+1}}, \ldots,x_{n}^{\sigma_{n}}) [/math] всех булевых функций от всевозможных наборов переменных [math] x_{m+1}, \ldots,x_{n} [/math]. Другими словами, подсхема [math] S_{2} [/math] вычисляет все булевы функции, зависящие от последних [math] n - m [/math] переменных. В силу теоремы 1
[math] size_{B}(S_{2}) \leqslant (n-m)2^{n-m+1}2^{2^{n-m}} [/math].
3. Схема [math] S_{3} [/math] производит "сборку" в соответствии с разложением функции [math] f [/math]: для каждого набора [math] \widetilde{\sigma}=(\sigma_{1},\dotsc,\sigma_{m}) [/math] реализуется конъюнкция
[math] x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{m}^{\sigma_{m}}\wedge f(\widetilde{\sigma},x_{m+1},\dotsc, x_{n}) [/math] ([math] 2^{m} [/math] элементов конъюнкции) и образуется дизъюнкция таких конъюнкций ([math] 2^{m}-1 [/math] элементов дизъюнкции).

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

[math] 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}} [/math].

Положим [math] k=n-m [/math]. Тогда

[math] size_{B}(f) \lesssim 3 \cdot 2^{n-k} +k2^{k+1}2^{2^{k}} [/math].

Заметим, что второе слагаемое "очень быстро" растет с ростом [math] k [/math], а первое слагаемое убывает с ростом [math] k [/math] медленней. Поэтому следует взять такое значение [math] k [/math], при котором первое и второе слагаемые приблизительно равны, и потом немного уменьшить [math] k [/math]. Тогда второе слагаемое "сильно" уменьшится, а первое "не очень сильно" возрастет. Возьмем, например, [math] k=\log_{2}n [/math]. Тогда

[math] 3 \cdot 2^{n-k} = 3 \cdot \dfrac{2^{n}}{n} [/math],
[math] k \cdot 2^{k+1} \cdot 2^{2^{k}}=\log_{2}n\cdot (2n)\cdot 2^{n}[/math],

то есть получили "слишком много". Возьмем [math] k [/math] на единицу меньше: [math] k=\log_{2}n-1 [/math]. Тогда

[math] 3 \cdot 2^{n-k} = 3 \cdot \dfrac{2^{n}}{n} \cdot 2 [/math],
[math] k \cdot 2^{k+1} \cdot 2^{2^{k}}=(\log_{2}n-1)\cdot n\cdot 2^{\dfrac{n}{2}}[/math].

Вспомним теперь, что [math] k [/math] должно быть целым числом, и положим [math] k=[\log_{2}n-1] [/math]. Тогда [math] n-k \lt n- \log_{2} + 2[/math],

[math] 3 \cdot 2^{n-k} \lt 12 \cdot \dfrac {2^{n}}{n} [/math],
[math] k\cdot 2^{k+1}\cdot 2^{2^{k}} \leqslant (\log_{2}-1)\cdot n\cdot 2^{\dfrac{n}{2}} [/math].

При этом выборе [math] k [/math] окончательно имеем

[math] size_{B}(n)\lesssim 12\dfrac {2^{n}}{n} [/math].
[math]\triangleleft[/math]


См. также

Примечания

Источники информации

  • Яблонский С.В. Введение в дискретную математику. — 4-е изд. — М.: Высшая школа, 2003. — 384 с. — ISBN 5-06-004681-8