Викиконспекты - Вклад участника [ru]

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

2015-03-17T12:05:31Z

195.88.14.200: /* Метод синтеза схем К.Э.Шеннона */

{{Определение

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

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

==Метод синтеза, основанный на [[СДНФ|совершенной ДНФ]]==

{{Лемма
|id = Lemma1
|about = 1
|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\le 7</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)\le 2n-1 </tex>.

Приведем пример для <tex> f=\bar{x}_{1}\wedge x_{2}\wedge x_{3} \wedge \bar{x}_{4}</tex> (рис. 1).

}}

{{Теорема
|id = Th1
|about = 1
|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 = 0 </tex>, то схема строится в соответствии с представлением <tex> 0=x_{1}\wedge\overline{x}_{1} </tex>, то есть <tex> size_{B}(0) \le 2</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>.(рис. 2) Имеем

::<tex> size_{B}(f)\le s\cdot(2n-1)+s-1 < s\cdot(2n-1)+s = 2ns \le n2^{n+1} </tex>.

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

::<tex> size_{B}(f(x_{1},...,x_{n}))\le n2^{n+1} </tex>.

Поэтому <tex> size_{B}(f)\le n2^{n+1} </tex>.
}}

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

{{Определение

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

{{Определение
|definition= <tex> f(n) \lesssim g(n) </tex> означает, что <tex>\varlimsup\limits_{n \to \infty}\frac{f(n)}{g(n)} \le 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
|about = 2
|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]]
Конъюнкции <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> 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}) \le size_{B}(K_{k}) + size_{B}(K_{n-k}) + 2^n </tex>.

Так как по [[#Th1|теореме 1]] <tex> size_{B}(K_{k}) \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)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> f(x_{1}, ..., 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},...,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>

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

::<tex> size_{B}(f)\lesssim 2^{n+1}. </tex>
}}

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

{{Теорема
|id = Th3
|about = 3
|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_{m} </tex>, где <tex> 1 \le m \le n </tex>:

<tex>f(x_{1},...,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)'''

: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>.

:2. Схема <tex> S_{2} </tex> реализует систему <tex> F(x_{m+1}^{\sigma_{m+1}},...,x_{n}^{\sigma_{n}}) </tex> всех булевых функций от всевозможных наборов переменных <tex> x_{m+1},...,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>.

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

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

[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Схемы из функциональных элементов ]]

Сокращённая и минимальная ДНФ

2015-02-20T14:47:59Z

195.88.14.200: /* Описание алгоритма */

== Сокращенная ДНФ ==

{{Определение
|definition =
Сокращенная ДНФ: форма записи функции, обладающая следующими свойствами:

*Любые два слагаемых различаются как минимум в двух позициях
*Ни один из конъюнктов не содержится в другом. Например, <tex>(x \land y)</tex> содержится в <tex>(x \land y \land z)</tex>.

}}
Функцию можно записать с помощью сокращенной ДНФ не единственным способом.

Запишем [[Определение булевой функции|функцию]] <tex>\left<x, y, z\right> </tex> (медиана) в виде [[СДНФ|совершенной ДНФ]]:
<tex>(x \land y \land z) \lor (x \land y \land \lnot z) \lor (x \land \lnot y \land z) \lor (\neg x \land y \land z)</tex>.
Известно, что это выражение равносильно следующему:
<tex>((x \land y \land z) \lor (x \land y \land \lnot z)) \lor ((x \land \lnot y \land z) \lor (x \land y \land z)) \lor ((\neg x \land y \land z) \lor (x \land y \land z))</tex>.
Вынесем в каждой скобке общий конъюнкт (например, в первой <tex>(x \land y \land z) \lor (x \land y \land \lnot z)=(x \land y) \lor (z \land \lnot z)</tex>.
Так как <tex>z \land \lnot z = 0</tex>, то такой конъюнкт не влияет на значение выражения, и его можно опустить.
Получим в итоге формулу <tex>(x \land y) \lor (y \land z) \lor (x \land z)</tex>.
== Минимальная ДНФ ==
{{Определение
|definition =
Минимальная ДНФ {{---}} такая сокращенная ДНФ, в которой содержится минимальное количество вхождений переменных.
}}
Каждая минимальная ДНФ является сокращенной, но не каждая сокращенная {{---}} минимальна.
Например, запись <tex>(x \land y) \lor (y \land z) \lor (x \land z)</tex> является минимальной ДНФ для медианы (она же сокращенная, как видно в примере выше); а запись <tex>(x \land y \land \lnot z) \lor (\neg x \land y \land z) \lor (x \land z)</tex> {{---}} не минимальная, но сокращенная ДНФ. 

== Минимизация ДНФ ==
Рассмотрим несколько способов минимизации дизъюнктивных нормальных форм:

=== Визуализация гиперкубами ===

[[Файл:Гиперкуб.PNG||right]]
Этот способ работает при количестве переменных не больше трёх (в противном необходимо вводить четвёртое или следующие за ним измерения для представления фигур).
Сначала мы рисуем куб в системе отсчёта <tex>Oxyz</tex> (названия координатных осей соответствуют названиям переменных). Затем каждую вершину обрабатываем следующим образом:
{| border="0"
|'''Описание алгоритма'''
|'''Пример'''
|-
|Если у нас конъюнкт, переменные в котором равны соответствующим координатам вершины, то в эту вершину мы помещаем закрашенный чёрным кружок.
|Вершине с координатами <tex>(0,1,1) </tex>соответствует конъюнкт <tex>(\neg X \wedge Y \wedge Z)</tex>, он равен единице при <tex>X=0, Y=1</tex> и <tex>Z=1</tex>)
|-
|В противном случае мы помещаем в вершину закрашенный белый кружок.

|Для такой ДНФ: <tex>(X \wedge \neg Y \wedge Z)\vee</tex> <tex> (X \wedge Y \wedge Z) \vee </tex><tex> (\neg X \wedge Y \wedge Z) \vee</tex><tex> (\neg X \wedge Y \wedge \neg Z) \vee </tex><tex>( X \wedge Y \wedge \neg Z)</tex> мы получим следующий гиперкуб (см. рисунок)
|-
|Далее обработка гиперкуба идёт следующим образом:
пока у нас есть незакрашенные вершины, мы выбираем грань, либо вершину, либо ребро, на которых больше всего закрашенных чёрным вершин и ещё не обработанных вершин.
|-
|Если в данном гиперкубе есть грань, все вершины на которой закрашены чёрным, то мы можем записать её в качестве конъюнкта, где будет только переменная с неизменяющейся соответствующей ей координатой.
|Грань, на которой лежат закрашенные вершины <tex>(0,1,1), (0,1,0), (1,1,0)</tex> и <tex>(1,1,1)</tex> мы можем записать как конъюнкт <tex>Y</tex>.
|-

|Теперь мы смотрим, остались ли на рёбрах куба закрашенные и не отмеченные нами в ДНФ вершины. Если — да, то рёбра с такими вершинами мы можем записать в качестве конъюнкта, где будут только переменные с неизменяющимися соответствующим им координатами
|Ребро, соединяющее закрашенные вершины (<tex>(0,1,1)</tex> и <tex>(1,1,1)</tex> мы можем записать как конъюнкт <tex>(Y \wedge Z)</tex>.
|-
|И если после такой обработки у нас остались свободные вершины, мы просто переписываем координаты каждой такой вершины в отдельный конъюнкт, равный <tex>1</tex>.
|Вершину <tex>(1,0,1)</tex> мы бы переписали как конъюнкт <tex>(X \wedge \neg Y \wedge Z)</tex>.
|}

В итоге нашу изначальную ДНФ можно записать как <tex>(Y) \vee (X \wedge Z)</tex>.

=== Карты Карно ===

Построим следующую таблицу <tex>n \times n</tex>, где <tex>n</tex> {{---}} количество переменных:
{| border="1"
|
|
!<tex> w </tex>
!<tex> w </tex>
!<tex> \neg w</tex>
!<tex> \neg w</tex>
|-
|
|
!<tex>z</tex>
!<tex> \neg z</tex>
!<tex> \neg z</tex>
!<tex>z</tex>
|-
!<tex>y</tex>
!<tex>x</tex>
|
|
|
|
|-
!<tex>y</tex>
!<tex> \neg x</tex>
|
|
|
|
|-
!<tex> \neg y</tex>
!<tex> \neg x</tex>
|
|
|
|
|-
!<tex> \neg y</tex>
!<tex>x</tex>
|
|
|
|
|}
Теперь для каждого конъюнкта мы помечаем соответствующую ему ячейку таблицы.

Например, ДНФ
 
 
<tex>(\neg X \wedge Y \wedge Z \wedge W) \vee (\neg X \wedge Y \wedge \neg Z \wedge W) \vee (\neg X \wedge Y \wedge \neg Z \wedge \neg W) \vee (\neg X \wedge Y \wedge Z \wedge \neg W) \vee (X \wedge \neg Y \wedge Z \wedge W) \vee (X \wedge \neg Y \wedge \neg Z \wedge W) \vee (\neg X \wedge \neg Y \wedge \neg Z \wedge \neg W)</tex>
 
 
будет выглядеть на картах Карно так:
 
 
{| border="1"
|
|
!<tex> w </tex>
!<tex> w </tex>
!<tex> \neg w</tex>
!<tex> \neg w</tex>
|-
|
|
!<tex>z</tex>
!<tex> \neg z</tex>
!<tex> \neg z</tex>
!<tex>z</tex>
|-
!<tex>y</tex>
!<tex>x</tex>
|
|
|
|
|-
!<tex>y</tex>
!<tex> \neg x</tex>
|
|1
|1
|
|-
!<tex> \neg y</tex>
!<tex> \neg x</tex>
|
|1
|1
|1
|-
!<tex> \neg y</tex>
!<tex>x</tex>
|
|
|1
|1
|}
 
Теперь покрываем прямоугольниками (длины сторон которых {{---}} степени двойки (1, 2, 4)) те ячейки карт Карно, которые содержат в себе единицу (на каждом ходу мы выбираем такой прямоугольник, чтобы он покрывал наибольшее количество ещё не покрытых клеток) до тех пор, пока не покроем все такие ячейки.

Для карт Карно на примере это выглядело бы так:
 
{| border="1"
|
|
!<tex> w </tex>
!<tex> w </tex>
!<tex> \neg w</tex>
!<tex> \neg w</tex>
|-
|
|
!<tex> z </tex>
!<tex> \neg z</tex>
!<tex> \neg z</tex>
!<tex> z </tex>
|-
!<tex> y </tex>
!<tex> x </tex>
|
|
|
|
|-
!<tex> y </tex>
!<tex> \neg x</tex>
|
|style="background:#F4A460"|1
|style="background:#F4A460"|1
|
|-
!<tex> \neg y</tex>
!<tex> \neg x</tex>
|
|style="background:#F4A460"|1
|style="background:#B4D19A"|1
|style="background:#7FFFD4"|1
|-
!<tex> \neg y</tex>
!<tex> x </tex>
|
|
|style="background:#7FFFD4"|1
|style="background:#7FFFD4"|1
|}
 
После этого записываем каждый прямоугольник в виде конъюнкта, в котором будут указаны только те переменные, которые одинаковы для всех ячеек этого прямоугольника.

То есть, в этом примере получаем: <tex>(\neg Z \wedge \neg X) \vee (\neg W \wedge \neg Y)</tex>

===Метод Квайна===
Этот метод основан на применении двух основных операций:
*Операция попарного неполного склеивания:
:<tex>A x \lor A \neg x = A x \lor A \neg x \lor A</tex>
*Операция элементарного поглощения
:<tex>A \tilde x \lor A = A </tex>
:(где A {{---}} любое элементарное произведение, то есть конъюнкт, в который каждая из переменных входит не более одного раза)
Метод состоит в последовательном выполнении всех возможных склеиваний и затем всех поглощений частей СДНФ пока это может быть осуществимо.
====Описание алгоритма====
*Исходным является множество пар вида <tex>Ax</tex> или <tex>A \neg x</tex>
*Выполняются все возможные операции неполного попарного склеивания для элементарных конъюнкций длины n (где n {{---}} количество аргументов).
*Выполняются все возможные операции элементарного поглощения для элементарных конъюнкций длины n-1 (общая часть "p" имеет длину n-1)
*В результате получилось множество элементарных конъюнкций, разделяемых на два подмножества (по длине):
**подмножество элементарных конъюнкций длины <tex>n</tex> (оставшиеся)
**подмножество элементарных конъюнкций длины <tex>n-1</tex>
*Если множество элементарных конъюнкций длины <tex>n-1</tex> не пусто, то заново выполняются операции неполного попарного склеивания и элементарного поглощения для конъюнкций длины <tex>n-1</tex> и так далее.
Алгоритм завершается, когда подмножество является пустым, либо нельзя выполнить ни одной операции неполного попарного склеивания.
После выполнения этого алгоритма будет получена сокращенная (но еще не минимальная) форма.

Переход от сокращённой формы к минимальной осуществляется с помощью специальной таблицы.
Члены СДНФ заданной функции вписываются в столбцы, а в строки — члены сокращённой формы. Отмечаются столбцы членов СДНФ, которые поглощаются отдельными элементами сокращённой формы.

Члены сокращённой формы, не подлежащие исключению, образуют ядро. Такие члены определяются по вышеуказанной матрице. Для каждой из них имеется хотя бы один столбец, перекрываемый только этим членом.

Для получения минимальной формы достаточно выбрать из членов сокращённой формы, не входящих в ядро, такое минимальное их число с минимальным количеством букв в каждом из этих членов, которое обеспечит перекрытие всех столбцов, не перекрытых членами ядра.

====Пример====

Функция от четырёх аргументов задана следующей таблицей:
{|border="1"
|Набор <tex>xyzw</tex>
|0000
|0001
|0010
|0011
|0100
|0101
|0110
|0111
|1000
|1001
|1010
|1011
|1100
|1101
|1110
|1111
|-
|Значение исходной функции
|1
|0
|0
|0
|1
|0
|0
|0
|0
|0
|1
|1
|1
|1
|1
|1
|-
|}

Проведём операции неполного склеивания и поглощения:

{|border="1"
|№
|Элементарная конъюнкция
|Поглощение
|-
|1
|<tex>\neg x\neg y\neg z\neg w</tex>
| +
|-
|2
|<tex>\neg xy\neg z\neg w</tex>
| +
|-
|3
|<tex>x\neg yz\neg w</tex>
| +
|-
|4
|<tex>x\neg y zw</tex>
| +
|-
|5
|<tex>xy\neg z\neg w</tex>
| +
|-
|6
|<tex>xy\neg zw</tex>
| +
|-
|7
|<tex>xyz\neg w</tex>
| +
|-
|8
|<tex>xyzw</tex>
| +
|-
|}

{|border="1"
|№№ склеивания
|Результат
|-
| 1 - 2
|<tex>\neg x \neg z\neg w</tex>
|-
| 2 - 5
|<tex>y \neg z\neg w</tex>
|-
| 3 - 4
|<tex>x \neg yz</tex>
|-
| 3 - 7
|<tex>\neg x \neg z\neg w</tex>
|-
| 4 - 8
|<tex> xzw</tex>
|-
| 5 - 6
|<tex>xy\neg z</tex>
|-
| 5 - 7
|<tex>xy \neg w</tex>
|-
| 6 - 8
|<tex>xyw</tex>
|-
| 7 - 8
|<tex>xyz</tex>
|-
|}

На данном шаге все элементы вида <tex>Ax</tex> или <tex>A \neg x</tex> участвовали в операциях попарного неполного склеивания и были поглощены своими собственными частями. Поэтому элементы сокращённой ДНФ на этом шаге не получены.

{|border="1"
|№
|Элементарная конъюнкция
|Поглощение
|-
| 1
|<tex>\neg x \neg z\neg w</tex>
|
|-
| 2
|<tex>y \neg z\neg w</tex>
|
|-
| 3
|<tex>x \neg yz</tex>
| +
|-
| 4
|<tex>\neg x \neg z\neg w</tex>
| +
|-
| 5
|<tex> xzw</tex>
| +
|-
| 6
|<tex>xy\neg z</tex>
| +
|-
| 7
|<tex>xy \neg w</tex>
| +
|-
| 8
|<tex>xyw</tex>
| +
|-
| 9
|<tex>xyz</tex>
| +
|-
|}

{|border="1"
|№№ склеивания
|Результат
|-
| 3 - 9
|<tex>xz</tex>
|-
| 4 - 5
|<tex>xz</tex>
|-
| 6 - 9
|<tex>xy</tex>
|-
| 7 - 8
|<tex>xy</tex>
|-
|}

На данном этапе получаем элементы сокращённой ДНФ <tex>\neg x \land \neg z \land \neg w</tex> и <tex>y \land \neg z \land \neg w</tex>

{|border="1"
|№
|Элементарная конъюнкция
|Поглощение
|-
| 1
|<tex>xz</tex>
|
|-
| 2
|<tex>xy</tex>
|
|-
|}
Обе элементарные конъюнкции на данном шаге являются элементами сокращённой ДНФ.

В результате выполнения алгоритма мы получаем следующую сокращённую ДНФ: <tex>(\neg x \land \neg z \land \neg w) \lor (y \land \neg z \land \neg w) \lor (x \land z) \lor (x \land y) </tex>

Переход от сокращённой формы к минимальной:

*Единицы ДНФ, покрываемые элементами <tex>Ax</tex> или <tex>A \neg x</tex> обозначаются "+". Пары <tex>Ax</tex> и <tex>A \neg x</tex>, попадающие в ядро помечаются "*".
*Единицы функции, которые покрываются только каким-то одним конъюнктом из системы элементов сокращённой ДНФ, помечаются “>”.
*Единицы функции, покрываемые ядром, но не покрываемые только каким-то одним конъюнктом из системы элементов сокращённой ДНФ помечаются “>>”.

{|border="1"
|
|<tex>\neg x\neg y\neg z\neg w</tex> >
|<tex>\neg x y\neg z\neg w</tex> >>
|<tex>x\neg yz\neg w</tex> >
|<tex>x\neg yzw</tex> >
|<tex>xy\neg z\neg w</tex> >>
|<tex>xy\neg zw</tex> >
|<tex>xyz\neg w</tex> >>
|<tex>xyzw</tex> >>
|-
|<tex>\neg x\neg z\neg w</tex>*
|style="background:#F4A460"| +
| +
|
|
|
|
|
|
|-
|<tex>y\neg z\neg w</tex>
|
| +
|
|
| +
|
|
|
|-
|<tex>xz</tex>*
|
|
|style="background:#F4A460"| +
|style="background:#F4A460"| +
|
|
| +
| +
|-
|<tex>xy</tex>*
|
|
|
|
| +
|style="background:#F4A460"| +
| +
| +
|-
|}

На основе этой таблицы получим ядро <tex>(\neg x \land \neg z \land \neg w) \lor (x \land z) \lor (x \land y) </tex>, которое является также и минимальной ДНФ.

==Ссылки==
<references/>
*[http://ru.wikipedia.org/wiki/%D0%9C%D0%B8%D0%BD%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BB%D0%BE%D0%B3%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D1%85_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B9_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%9A%D1%83%D0%B0%D0%B9%D0%BD%D0%B0 Минимизация логических функций методом Куайна — Википедия]
*[http://matrixcalc.org/pf1.html Метод Квайна]
*[http://ru.wikipedia.org/wiki/%D0%9A%D0%B0%D1%80%D1%82%D0%B0_%D0%9A%D0%B0%D1%80%D0%BD%D0%BE Карта Карно — Википедия]
*[http://vuz.exponenta.ru/PDF/book/kv.html Минимизация булевых функций в классе ДНФ]
*[http://tablica-istinnosti.ru/minimizatsiya-dnf-metodom-kvayna.html Минимизация ДНФ методом Квайна]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Комбинаторика ]]

Обсуждение:Сокращённая и минимальная ДНФ

2015-02-20T14:18:31Z

195.88.14.200: /* Карты Карно */

{{tick | ticked = 1}} Сделать из страницы [[Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно]] страницу перенаправления.

{{tick | ticked = 1}} Так, чтобы она переходила на соответствующий раздел

{{tick | ticked = 1}} Требования - Викификация - 9 пункт.

=== Определение Минимальной ДНФ ===

{{tick | ticked = 1}} Требования - Викификация - 5 пункт.

=== Визуализация гиперкубами ===

{{tick | ticked = 1}} Oxyz", "X=0, Y=1 и Z=1" - в TeX, но тогда нужно все "(0,1,1)" в TeX занести, и даже единицу в " отдельный конъюнкт, равный 1".

{{tick | ticked = 1}} Пример в методе "Визуализация гиперкубами" {{---}} хороший, но комментарии, относящиеся к примеру, нужно отделить не только скобками. Нужно что-то вроде разделения на два столбца {{---}} слева алгоритм, справа то, что происходит с примером.

=== Карты Карно ===

{{tick | ticked = 1}} Ненумерованный список: у него есть два последних пункта, но нет остальных. Наверное, он здесь не нужен.

{{tick | ticked = 1}} комментарии, относящиеся к примеру, нужно отделить от описания метода.

{{tick | ticked = 1}} <s>"n*n" , "n" в TeX Требования - TeX - 3 пункт</s> когда обозначают размер матрицы или пространства, используют <tex>\times</tex>

{{tick}} проверить пример (не соотвествует СДНФ), подробнее расписать алгоритм (сворачивание карты в трубку), если взять последний пример отсюда: http://matrixcalc.org/pf2.html, восстановить таблицу истинности и составить карту Карно с нумерацией переменных в порядке как сейчас (yx\wz), то получится очень показательная карта - квадрат 2х2 будет покрывать углы.

=== Метод Квайна ===

{{tick | ticked = 1}} операция или соотношение {{---}} не путайте читателя.

{{tick | ticked = 1}} Сокращать слова не нужно.

{{tick | ticked = 1}} "то выполняются шаги со второго", а список ненумерованный {{---}} исправить

{{tick | ticked = 1}} Примеру не хватает заголовка.

{{tick | ticked = 1}} Пример непонятен: описывается какая-то функция от четырех аргументов, но не понятно, где в примере, скажем, "множество пар вида <tex>Ax</tex> или <tex>A \neg x</tex>".

{{tick | ticked = 1}} Нужно показать, какую ДНФ мы минимизируем

{{tick | ticked = 1}} Все n, n-1 в TeX

{{tick | ticked = 1}} Что такое "импликанты" ?

{{tick | ticked = 1}} Придумать новое описание пар вида <tex>Ax, A \neg x</tex>

Обсуждение:Сокращённая и минимальная ДНФ

2015-02-20T14:18:13Z

195.88.14.200: /* Карты Карно */

{{tick | ticked = 1}} Сделать из страницы [[Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно]] страницу перенаправления.

{{tick | ticked = 1}} Так, чтобы она переходила на соответствующий раздел

{{tick | ticked = 1}} Требования - Викификация - 9 пункт.

=== Определение Минимальной ДНФ ===

{{tick | ticked = 1}} Требования - Викификация - 5 пункт.

=== Визуализация гиперкубами ===

{{tick | ticked = 1}} Oxyz", "X=0, Y=1 и Z=1" - в TeX, но тогда нужно все "(0,1,1)" в TeX занести, и даже единицу в " отдельный конъюнкт, равный 1".

{{tick | ticked = 1}} Пример в методе "Визуализация гиперкубами" {{---}} хороший, но комментарии, относящиеся к примеру, нужно отделить не только скобками. Нужно что-то вроде разделения на два столбца {{---}} слева алгоритм, справа то, что происходит с примером.

=== Карты Карно ===

{{tick | ticked = 1}} Ненумерованный список: у него есть два последних пункта, но нет остальных. Наверное, он здесь не нужен.

{{tick | ticked = 1}} комментарии, относящиеся к примеру, нужно отделить от описания метода.

{{tick | ticked = 1}} <s>"n*n" , "n" в TeX Требования - TeX - 3 пункт</s> когда обозначают размер матрицы или пространства, используют <tex>\times</tex>

{{tick | ticked = 0}} проверить пример (не соотвествует СДНФ), подробнее расписать алгоритм (сворачивание карты в трубку), если взять последний пример отсюда: http://matrixcalc.org/pf2.html, восстановить таблицу истинности и составить карту Карно с нумерацией переменных в порядке как сейчас (yx\wz), то получится очень показательная карта - квадрат 2х2 будет покрывать углы.

=== Метод Квайна ===

{{tick | ticked = 1}} операция или соотношение {{---}} не путайте читателя.

{{tick | ticked = 1}} Сокращать слова не нужно.

{{tick | ticked = 1}} "то выполняются шаги со второго", а список ненумерованный {{---}} исправить

{{tick | ticked = 1}} Примеру не хватает заголовка.

{{tick | ticked = 1}} Пример непонятен: описывается какая-то функция от четырех аргументов, но не понятно, где в примере, скажем, "множество пар вида <tex>Ax</tex> или <tex>A \neg x</tex>".

{{tick | ticked = 1}} Нужно показать, какую ДНФ мы минимизируем

{{tick | ticked = 1}} Все n, n-1 в TeX

{{tick | ticked = 1}} Что такое "импликанты" ?

{{tick | ticked = 1}} Придумать новое описание пар вида <tex>Ax, A \neg x</tex>

Математическая индукция

2015-02-14T10:00:26Z

195.88.14.200: /* Определение */

[[Категория:Математический анализ 1 курс]]
== Определение ==
Математическая индукция {{---}} способ рассуждения, применяемый, в частности, в [[Математический анализ 1 курс|математическом анализе]], заключающийся в следующем:

Пусть имеется последовательность свойств <tex> P_1, P_2 \dots P_n \dots </tex>
# <tex> P_1 </tex> {{---}} истина
# <tex> P_k \Rightarrow P_{k+1} </tex> {{---}} шаг индукции
# Тогда все <tex> P_n </tex> {{---}} истинны

== Примеры использования ==

=== Неравенство Бернулли ===
{{Утверждение
|about =
неравенство Бернулли
|statement =
<tex> \forall n \in N; \forall x > -1 : {(1 + x)}^n \ge 1 + nx </tex>
|proof = 
# <tex> n = 1: 1 + x \ge 1 + x </tex> {{---}} верно
# <tex> {(1 + x)}^{n + 1} = {(1 + x)}^n (1 + x) \ge (1 + nx) (1 + x) = </tex> <tex> = 1 + x + nx + nx^2 = 1 + (n + 1)x + nx^2</tex>, так как <tex> nx^2 \ge 0 </tex>, то <tex> {(1 + x)}^{n + 1} \ge 1 + (n + 1)x </tex>
}}

=== Конечный бином Ньютона ===

Для того, чтобы сформировать следующее утверждение, определим систему чисел, называемую биномиальными коэффициентами: 
:<tex> 0! = 1 \\ n! = n(n-1)! = n (n-1) (n-2) \dots 1 </tex>
:<tex dpi = "150"> m \le n: C_n^m = \frac {n!} {(n-m)!m!} \\ \\
C_{n+1}^m = C_n^m + C_n^{m-1} = \\ = C_n^m + C_n^{m-1} = \frac {n!} {(n-m)!m!} + \frac {n!} {(n-m+1)!(m-1)!} = \\
= \frac {n!((n - m + 1) + m)} {m!((n+1) - m)!} = \frac {n!(n+1)} {((n+1)-m)!m!} = C_{n+1}^m </tex>

{{Утверждение
|about =
конечный бином Ньютона
|statement =
<tex>a, b \in R; n \in N : {(a + b)}^n = \sum_{k=0}^n C_n^k a^k b^{n - k} </tex>
|proof = 
# Для n = 1 {{---}} очевидно
# <tex> {(a + b)}^{n + 1} = a{(a + b)}^n + b{(a + b)}^n = </tex> 
:<tex> = \sum\limits_{k = 0}^n C_n^k a^{k + 1} b^{n - k} + \sum\limits_{k = 0}^n C_n^k a^k b^{n - k + 1} = </tex>

:<tex> = \sum\limits_{j = 1}^{n + 1} C_n^{j - 1} a^j b^{n - j + 1} + \sum\limits_{i = 0}^n C_n^i a^i b^{n - i + 1} = </tex>

:<tex> = C_n^n a^{n + 1} b^0 + \sum\limits_{j = 1}^n C_n^{j - 1} a^j b^{n - j + 1} + C_n^0 a^0 b^{n+1} + \sum\limits_{i = 1}^n C_n^i a^i b^{n - i + 1} = </tex>

:<tex> = 1 (a^{n + 1} + b^{n + 1}) + \sum\limits_{j = 1}^n (C_n^{j - 1} + C_n^j) a^j b^{n - j + 1}</tex>

:Так как <tex>1 = C_{n + 1}^{n + 1} = C_{n + 1}^0 </tex> , то

:<tex> = C_{n + 1}^{n + 1} a^{n + 1} b^0 + C_{n + 1}^0 a^0 b^{n + 1} + \sum\limits_{j = 1}^n C_{n + 1}^j a^j b^{n - j + 1}</tex>

:Занесем первые два слагаемых под знак суммы и получим:

:<tex> = \sum\limits_{j = 0}^{n + 1} C_{n + 1}^j a^j b^{n + 1 - j}</tex> , что есть разложение для <tex> {(a + b)}^{n + 1} </tex>
}}