%зачем менять то, что уже идеально?
\section {Классическое представление булевых функций. КНФ. ДНФ.}

Рассмотрим класс $K_0 = \{ \cdot , \vee , \bar{ }\}$
Символом $x^a$, где $a \in \Omega $, обозначим функцию переменной $x$, принимающую значение 1, если $x = a$, и 0 в противном случае. Таким образом:
\begin{center}
	\begin{equation*}
		x^a =
		\begin{cases}
   			$x, a = 1$
			\\
			\bar{x},a = 0
 		\end{cases}
	\end{equation*}
\end{center}

\opr
Пусть $i_1, \dotsc, i_k$ - различные натуральные числа. Формула вида $x_{i_1}^{a_1} \vee \dotsc \vee x_{i_k}^{a_k}$ называется элементарной дизъюнкцией ранга $k$.\par Если заменить $\vee$ на $\&$, то получаем элементарную конъюнкцию ранга $k$. \par Если элементраная дизъюнкция рассматривается как формула от переменной $x_1, \dotsc,x_n$ и её ранг равен $n$, то она назвается совершенной.

\opr Конъюктивной нормальной формой (КНФ) называется $\forall$ формула представляющая собой конъюнкцию конечного числа элементарных дизъюнкций.

\thr $\forall$ булевая функция может быть представлена в виде $f(x_1, \dotsc, x_n) = \mathlarger{\mathlarger{\text{\&}}} _{(b_1, \dotsc, b_k) = \Omega^k} x_{i_1}^{\bar{b}_{i_1}},\dotsc,x_{i_k}^{\bar{b}_{i_k}}f_{i_1, \dotsc, i_n}^{\bar{b}_{i_1},\dotsc,\bar{b}_{i_n}}(x_1,\dotsc,x_n)$ %оставь надежду, всяк сюда смотрящий

\note Аналогичным образом определяется элементарная дизъюнкция(ДНФ).

\thr $\forall$ булевой функции $k\leq n$ представима формулой $f(x_1,\dotsc,x_n) = \mathlarger{\mathlarger{\vee}} _{(a_1, \dotsc, a_k)} x_{i_1}^{a_{i_1}},\dotsc,x_{i_k}^{a_{i_k}}f_{i_1, \dotsc, i_n}^{a_{i_1},\dotsc,a_{i_n}}(x_1,\dotsc,x_n)$ %как и сюда

\conseq $f(x_1,\dotsc,x_n) \equiv \overline{x_1}f(0,x_2,\dotsc,x_n) \vee x_1f(1, x_2, \dotsc, x_n)$

В случае $k = n$ получаем совершенные КНФ и ДНФ, называемые СКНФ и СДНФ.

\utv $\exists!$ СДНФ и СКНФ $\forall f \in F_2$.

\example (две ДНФ одной функции) \par $\overline{x_1}\overline{x_2}x_3 \vee \overline{x_1}x_2x_3 \vee x_1x_2 \equiv \overline{x_1}x_3 \vee x_1x_2$

\opr Многочленом Жегалкина от переменных $x_1, \dotsc, x_n$ называется формула над классом $K_5=\{\oplus, \cdot, 1\}$ вида
\begin{center}
	$a_0 \oplus \sum_{i_1, \dotsc,i_k} a_{i_1, \dotsc, i_n}x_{i_1}\cdot \dotsc \cdot x_{i_n}$\\$1 \leq i_1 \leq \dotsc \leq i_k \leq n; a_0, a_{i_1}, \dotsc, a_{i_n} \in \Omega$
\end{center}
Здесь знак суммы означает исключающее "или" и сумирование ведётся по всем непустым подмножествам $\{i_1, \dotsc, i_k\}$ множества $\{1, \dotsc, n\}$.

\opr Элементарной конъюнкцией входящей в многочлен Жегалкина в качестве слогаемых называется одночлен (моном), элементы $a_{i_1, \dotsc, i_k}$ коэффиценты многочлена, $a_0$ - свободный член. Ранг конъюнкции называется степенью одночлена. \par Степенью неленейности функции представляемой многочленом Жегалкина называется максимальная из степеней многочлена, входящих в многочлен Жегалкина этой функции с коэффицентом 1.

\thr $\forall$ булевая функция однозначно представима многочленом Жегалкина.

\opr Двоичным n-мерным кубом называют множество точек пространства $\R^n$ с координатами $a_1, \dotsc, a_n$, где $a_i \in \Omega$

Для задания булевой функции $f(x_1,\dotsc,x_n)$ на n-мерном кубе отмечают вершины соответствующие носителю этой функции.

\opr Гранью n-мерного куба ранга $k$ (или иначе разморности $n-k$) называется множество его вершин, соответсвующее $N_{\varphi}$, где $\varphi$ - произвольная элементарная конъюнкция ранга k, т.е. $\varphi = x_{i_1}^{a_1}, \dotsc, x_{i_n}^{a_k}$

\utv(свойства)
\begin{enumerate} 
	\item $f = \varphi \Leftrightarrow N_f = N_{\varphi}$
	\item $N_{f \cdot \varphi} = N_f \cap N_{\varphi}$
	\item $N_{f \cup \varphi} = N_f \cup N_{\varphi}$
	\item $f \cup \varphi \equiv f \Leftrightarrow N_{\varphi}\subseteq N_f$
	\item $f \equiv \mathlarger{\mathlarger{\vee}} _{i=1}^m\varphi_i \Leftrightarrow N_f = \mathlarger{\mathlarger{\cup}} _{i=1}^mN_{\varphi_i}$
\end{enumerate}

\opr Длиной ДНФ называется сумма рангов входящих в неё элементарных конъюнкций. ДНФ с минимальной длиной называется минимальной ДНФ (МДНФ).

\opr Элементарная конъюнкция $\psi = x_{i_1}^{a_1}\cdot \dotsc \cdot x_{i_k}^{a_k}$ называется импликантой функции $f(x_1,\dotsc,x_n)$, если она входит в некоторую ДНФ представляющуюю функцию $f$.

\utv (эквивалентно)
\begin{enumerate}
	\item $\psi$ - импликанта функции $f$.
	\item $\psi \cup f \equiv f$
	\item $\psi \rightarrow f \equiv 1$
	\item $\psi \cdot f = \psi$
\end{enumerate}

\opr Говорят, что $g$ поглащается функцией $f$, если $g \vee f \equiv f$, т.е. импликанта это элементарная конъюнкция, поглощаемая функцией $f$.

\opr Имплеканта функции f называется простой, если никакая её собственная часть не поглощается функцией f.

\examplei

$f(x_1, x_2, x_3) \equiv x_1x_2 \vee x_1\overline{x_2}\vee \overline{x_2} \overline{x_3}$

$\overline{x_2} \overline{x_3}$ - простая.

$x_1x_2$ - нет, т.к. $x_1$ поглощается $f$.

\lem Пусть $\varphi_1$ и $\varphi_2$ импликанты $f$, $\varphi_1$ поглощает $\varphi_2 \Leftrightarrow \varphi_1$ - часть $\varphi_2$.

\thr $\forall$ импликанта функции $f$, содержащаяся в какой-либо МДНФ функции $f$ является простой.

\thr Пусть $\varphi_1 \cup\dotsc\cup \varphi_m$ - дизъюнкция всех простых импликант функции $f$, тогда \\ $f \equiv \varphi_1 \vee\dotsc\vee \varphi_m$.

\opr Дизъюнкция всех простых импликант функции $f$ называется сокращенной ДНФ.

\opr ДНФ $\varphi_1 \cup\dotsc\cup \varphi_m$ функции $f$ называется тупиковой, если все $\varphi_i, i \in \overline{1, k}$, входящие в неё, являются простыми импликантами $f$ и $\varphi$.

Всюду далее $f-n$-местная булевая функция отличается от константы.

\subsection {Метод Блейка}
Метод Блейка строит из ДНФ сокращённую ДНФ.\par
Основной операцией данного алгоритма является операция неполного склеивания, в основе которого лежит тождество:
\begin{center}
	$x\varphi_1 \vee \bar{x}\varphi_2 \equiv x\varphi_1 \vee \bar{x}\varphi_2 \vee \varphi_1\varphi_2$
\end{center}
Вход: ДНФ\\
Выход: Сокращённая ДНФ\\
\underline{Этап 1}
В исходной ДНФ нааходим пару импликант, в которой некоторая переменная входит в разных степенях: $\varphi_i = x_k\varphi_i'$ и $\varphi_j = \overline{x_k}\varphi_j'$.
Формируем $\varphi_1\varphi_2$ и добавляем её в ДНФ, повторяем до тех пор, пока не перестанут повялятся новые импликанты.\\
\underline{Этап 2}\\
В полученной ДНФ применяем операцию поглощения используя тождество $\varphi\psi\vee\varphi\equiv\varphi$ до тех пор пока это возможно.

\thr Полученная на выходе алгоритма ДНФ является сокращённой ДНФ.

\proof Покажем, что ДНФ, полученная на \underline{Этапе 1} содержит все простые импликанты функции f(индукция по n).\par
Пусть $n=1$. Утверждение очевидно, т.к. ДНФ функции одной переменной отличной от константы есть $x_1$ или $\overline{x_1}$.\par
Пусть $\forall$ ДНФ и для $\forall$ функции от n-1 переменной после \underline{Этапа 1} образуется ДНФ, содержащая все простые импликанты.\par
Пусть теперь $f$ - функция от $n$ переменных и $\varphi$ её импликанта 
\begin{itemize}
	\item[а)] Если ранг $\varphi$ равен n, то $\varphi$ содержится в $\forall$ ДНФ функции $f$.

Действительно пусть $\varphi = x_1^{a_1}\cdot \dotsc \cdot x_n^{a_n}$, тогда она принимает значения $1 \Leftrightarrow$ все $x_i$ равны $a_i$ в любой ДНФ функции f должна присутствовать импликанта $\varphi'$, принимающая значение 1 на $(a_1, \dotsc, a_n) \Rightarrow$ все переменные входят в неё в тех же степенях, что и в $\varphi$, но

	\item[б)]Если ранг $\varphi$ меньше, то $\exists x_i$ не входящее в $\varphi$.

Представим $f$ в виде $f=x_ih\vee \overline{x_i}g \vee t$, где $h,g,t$ - некоторые булевые функции, независящие от $x_i$.
Т.к. $\varphi$ - импликация функции $f$, то $\varphi\vee x_ih\vee \overline{x_i}g\vee t$ совпадает с $x_ih\vee \overline{x_i}g\vee t$.
Полагая $x_i = 0$ или 1 имеем $\varphi\vee g\vee t\equiv g\vee t$ и $\varphi\vee h\vee t\equiv h\vee t$ соответственно.
Возьмём конъюнкцию этих тождеств и применим к левой части закон дистрибутивности.
Получим $\varphi\vee (g\vee t)(h\vee t) \equiv (g\vee t)(h\vee t) \Rightarrow \varphi$ является импликантой функции $f_1=(h\vee t)(g\vee t)\equiv hg\vee t$.

ДНФ этой функции получается с помощью операции "неполного склеивания" из импликант, входящих в ДНФ функции $x_ih\vee \overline{x_i}g \vee t$.
При этом $\varphi$ - простоая для f, т.к. $\varphi$ - простая для $f_1$, а f поглащает $f_1$.\par

Тогда по предположению индукции $\varphi$ содержится в ДНФ, полученной после \underline{Этапа 1}, применнёного к ДНФ функции $f_1$, но $\varphi \in$ аналогичной ДНФ функции $f$, т.к. $\forall$ непростая импликанта поглащается некоторой простой, то после \underline{Этапа 2} в ДНФ окажутся только простые импликанты.
\end{itemize}

\lem Путь ДНФ $A = \mathlarger{\mathlarger{\cup}} _{i=1}^k\varphi_i$ поглощает элементарную конъюнкцию $\varphi$ и $\varphi \varphi_k \equiv 0$.
Тогда $\varphi$ поглощается ДНФ $A^1=\mathlarger{\mathlarger{\cup}} _{i=1}^k\varphi_i$

\opr Функции $f_1$ и $f_2$ называются ортогональными, если $f_1f_2 \equiv 0$

\thr(Критерий поглощения)

Пусть  $A=\mathlarger{\mathlarger{\cup}} _{i=1}^k u_i$ - ДНФ некоторой функции, $\varphi_0$ - элементарная конъюнкция не ортогональная ни одной из конъюнкций $\varphi_1, \dotsc,\varphi_k$. Обозначим $\varphi_{0_i}$ - конъюнкцию членов входящих в $\varphi_0$  и в $\varphi_i$, а $\varphi_{1_i}$ - конъюнкция членов $\varphi_i$, невходящих в $\varphi_0$ (если $\varphi_i = \varphi_{0_i}, \varphi_{1_i} = 1$) ДНФ поглощает $\varphi \Leftrightarrow \mathlarger{\mathlarger{\vee}} _{i=1}^k\varphi_{1_i} \equiv 1$

\utv Если $f$ монотонна, то сокращённая ДНФ = МДНФ.

\subsection {Метод Квайна}
Составляется таблица, строчки которой обозначают всеми простыми имлекантами длиной функции, столбцы - наборами, на которых функция принимает значение 1. На пересечении ставится значение импликанты на соответствующем наборе. Для построения ДНФ или МДНФ надо удалять строки так, чтобы в каждом столбце была хотя бы одна 1.
