210
правок
Изменения
Новая страница: «Приведем несколько простейших алгоритмов синтеза [[Реализация булевой функции схемой и...»
Приведем несколько простейших алгоритмов синтеза [[Реализация булевой функции схемой из функциональных элементов|схем]], в случае когда базис состоит из элементов: инвертора, конъюнктора и дизъюнктора.
==Метод синтеза, основанный на [[СДНФ|совершенной ДНФ]]==
{{Лемма
|id = Lemma1
|about = 1
|statement =
Для любой конъюнкции <tex> x_{1}\wedge ... \wedge x_{n} </tex> <tex> Size_{B}(x_{1} ... x_{n})\le 2n-1 </tex>
|proof =
Данная схема может быть построена их <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>.
Очевидно, что сложность построенной схемы равна <tex> 2n-1 </tex>. Поэтому <tex> Size_{B}(x_{1} ...x_{n})\le 2n-1 </tex>.
Лемма доказана.
}}
{{Теорема
|id = Th1
|about = 1
|statement = Имеет место неравенство <tex> Size_{B}(n)\le n2^{n+1} </tex>
|proof = Пусть <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>,
где <tex> s \le 2^{n} </tex> и каждая конъюнкция имеет вид
::<tex> K_{j}=x_{1}\wedge\overline{x}_{2}\wedge{x}_{3}\wedge ... \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>. Имеем
::<tex> Size_{B}(n)\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_{B}(0) \le 2</tex>.
Таким образом, для любой функции <tex> f(x_{1},...,x_{n}) </tex> выполняется неравенство
::<tex> Size_{B}(f(x_{1},...,x_{n}))\le n2^{n+1} </tex>.
Поэтому <tex> Size_{B}(n)\le n2^{n+1} </tex>.
Теорема доказана.
}}
==Метод синтеза, основанный на более компактной реализации множества всех конъюнкций==
{{Лемма
|id = Lemma2
|about = 2
|statement = Имеет место соотношение <tex> Size_{B}(K_{n}) \sim 2^n </tex>
|proof = Каждая конъюнкция <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}\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> 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> элементов конъюнкции, осуществляющих вышеприведенную операцию. Следовательно,
::<tex> Size_{B}(K_{n}) \le Size_{B}(K_{k}) + Size_{B}(K_{n-k}) + 2^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> 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_{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_{B}(K_{n}) \ge 2^{n} </tex>. Таким образом,
::<tex> Size_{B}(K_{n}) \sim 2^n </tex>.
Лемма доказана.
}}
{{Теорема
|id = Th2
|about = 2
|statement = Имеет место соотношение <tex> Size_{B}(n)\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> (не равной нулю) имеем
::<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}(n)\lesssim 2^{n+1}. </tex>
Теорема доказана.
}}
==Метод синтеза схем, предложенный К.Э.Шенноном==
{{Теорема
|id = Th3
|about = 3
|statement = Имеет место соотношение <tex> Size_{B}(n)\lesssim 12\frac {2^{n}}{2} </tex>.
|proof = Пусть <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>.
Схема для функции <tex> f </tex> строится из трех подсхем: <tex> S_{1},S_{2},S_{3} </tex>.
:1. Схема <tex> S_{1} </tex> реализует все конъюнкции из множества <tex> K_{m} (x_{1},...,x_{m}) </tex>. В силу [[#Lemma2|Леммы 2]] выполняется неравенство
::<tex> Size_{B}(S_{1}) \le 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]]
::<tex> Size_{B}(S_{2}) \le (n-m)2^{n-m+1}2^{2^{n-m}} </tex>.
:3. Схема <tex> S_{3} </tex> производит "сборку" в соответствии с разложением функции <tex> f </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> Size_{B}(S_{3}) \le 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> k=n-m </tex>. Тогда
::<tex> Size_{B}(n) \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> 3 \cdot 2^{n-k} = 3 \cdot \frac{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 </tex> на единицу меньше: <tex> k=\log_{2}n-1 </tex>. Тогда
::<tex> 3 \cdot 2^{n-k} = 3 \cdot \frac{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 </tex> должно быть целым числом, и положим <tex> k=[\log_{2}n-1] </tex>. Тогда
<tex> n-k < n- \log_{2} + 2</tex>,
::<tex> 3 \cdot 2^{n-k} < 12 \cdot \frac {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 </tex> окончательно имеем
::<tex> Size_{B}(n)\lesssim 12\frac {2^{n}}{2} </tex>.
Теорема доказана.
== Литература ==
* Яблонский С.В. Введение в дискретную математику. — 4-е изд. — М.: Высшая школа, 2003. — 384 с. — ISBN 5-06-004681-8
}}
==Метод синтеза, основанный на [[СДНФ|совершенной ДНФ]]==
{{Лемма
|id = Lemma1
|about = 1
|statement =
Для любой конъюнкции <tex> x_{1}\wedge ... \wedge x_{n} </tex> <tex> Size_{B}(x_{1} ... x_{n})\le 2n-1 </tex>
|proof =
Данная схема может быть построена их <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>.
Очевидно, что сложность построенной схемы равна <tex> 2n-1 </tex>. Поэтому <tex> Size_{B}(x_{1} ...x_{n})\le 2n-1 </tex>.
Лемма доказана.
}}
{{Теорема
|id = Th1
|about = 1
|statement = Имеет место неравенство <tex> Size_{B}(n)\le n2^{n+1} </tex>
|proof = Пусть <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>,
где <tex> s \le 2^{n} </tex> и каждая конъюнкция имеет вид
::<tex> K_{j}=x_{1}\wedge\overline{x}_{2}\wedge{x}_{3}\wedge ... \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>. Имеем
::<tex> Size_{B}(n)\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_{B}(0) \le 2</tex>.
Таким образом, для любой функции <tex> f(x_{1},...,x_{n}) </tex> выполняется неравенство
::<tex> Size_{B}(f(x_{1},...,x_{n}))\le n2^{n+1} </tex>.
Поэтому <tex> Size_{B}(n)\le n2^{n+1} </tex>.
Теорема доказана.
}}
==Метод синтеза, основанный на более компактной реализации множества всех конъюнкций==
{{Лемма
|id = Lemma2
|about = 2
|statement = Имеет место соотношение <tex> Size_{B}(K_{n}) \sim 2^n </tex>
|proof = Каждая конъюнкция <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}\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> 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> элементов конъюнкции, осуществляющих вышеприведенную операцию. Следовательно,
::<tex> Size_{B}(K_{n}) \le Size_{B}(K_{k}) + Size_{B}(K_{n-k}) + 2^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> 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_{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_{B}(K_{n}) \ge 2^{n} </tex>. Таким образом,
::<tex> Size_{B}(K_{n}) \sim 2^n </tex>.
Лемма доказана.
}}
{{Теорема
|id = Th2
|about = 2
|statement = Имеет место соотношение <tex> Size_{B}(n)\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> (не равной нулю) имеем
::<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}(n)\lesssim 2^{n+1}. </tex>
Теорема доказана.
}}
==Метод синтеза схем, предложенный К.Э.Шенноном==
{{Теорема
|id = Th3
|about = 3
|statement = Имеет место соотношение <tex> Size_{B}(n)\lesssim 12\frac {2^{n}}{2} </tex>.
|proof = Пусть <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>.
Схема для функции <tex> f </tex> строится из трех подсхем: <tex> S_{1},S_{2},S_{3} </tex>.
:1. Схема <tex> S_{1} </tex> реализует все конъюнкции из множества <tex> K_{m} (x_{1},...,x_{m}) </tex>. В силу [[#Lemma2|Леммы 2]] выполняется неравенство
::<tex> Size_{B}(S_{1}) \le 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]]
::<tex> Size_{B}(S_{2}) \le (n-m)2^{n-m+1}2^{2^{n-m}} </tex>.
:3. Схема <tex> S_{3} </tex> производит "сборку" в соответствии с разложением функции <tex> f </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> Size_{B}(S_{3}) \le 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> k=n-m </tex>. Тогда
::<tex> Size_{B}(n) \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> 3 \cdot 2^{n-k} = 3 \cdot \frac{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 </tex> на единицу меньше: <tex> k=\log_{2}n-1 </tex>. Тогда
::<tex> 3 \cdot 2^{n-k} = 3 \cdot \frac{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 </tex> должно быть целым числом, и положим <tex> k=[\log_{2}n-1] </tex>. Тогда
<tex> n-k < n- \log_{2} + 2</tex>,
::<tex> 3 \cdot 2^{n-k} < 12 \cdot \frac {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 </tex> окончательно имеем
::<tex> Size_{B}(n)\lesssim 12\frac {2^{n}}{2} </tex>.
Теорема доказана.
== Литература ==
* Яблонский С.В. Введение в дискретную математику. — 4-е изд. — М.: Высшая школа, 2003. — 384 с. — ISBN 5-06-004681-8
}}
