?

Log in

No account? Create an account

Thu, Apr. 6th, 2006, 11:55 pm
Четвертый семинар

Тема: Полнота системы булевых функций. Графы.. Читаем, комментируем, решаем ДЗ.

Системы булевых функций. Базис Жегалкина

Конечное множество булевых функций $ \mathcal{F} = \{ f_1, f_2, \dots f_n \}$ называют системой булевых функций. Систему булевых функций называют полной, если любая булева функция может быть выражена в виде формулы над этой системой (другими словами, если она представима через функции данной системы).

Примером полной системы является так называемый стандартный базис, содержащий дизъюнкцию, коньюнкцию и отрицание: $ \mathcal{F}_0 = \{ \vee, \wedge, \overline{\phantom{x}}\}$. Полнота этой системы легко доказывается тем, что любая булева функция может быть представлена в виде ДНФ или КНФ. А учитывая, что $ x \vee y = \overline{\overline{x} \wedge\overline{y}}$ и $ x \wedge y = \overline{\overline{x} \vee \overline{y}}$, полными являются даже системы $ \{ \vee, \overline{\phantom{x}}\}$ и $ \{ \wedge, \overline{\phantom{x}}\}$.

Другой распространённой полной системой булевых функций является базис Жегалкина: $ \mathcal{F}_{\mbox{Ж}} = \{ \oplus, \cdot, 1 \}$, включающий исключающее или, коньюнкцию и константу 1. Можно доказать, что любая булева функция представима в виде так называемого полинома Жегалкина:

$\displaystyle f(x_1, \dots x_n) = \sum\limits_{\begin{array}{c} i_1, i_2, \dots......end{array} } a_{i_1, i_2, \dots i_k} x_{i_1} x_{i_2} \dots x_{i_k}\oplus a_0,$

где $ a_j \in \{0, 1\}$. В частном случае, полином Жегалкина имеет линейный вид:

$\displaystyle f(x_1, \dots x_n) = \sum\limits_{i \in \overline{1, n}} a_i x_i \oplus a_0.$

Булева функция, представимая в виде линейного полинома Жегалкина, называется линейной.

Существует простой способ выражения любой булевой функции над базисом Жегалкина. Этот способ носит название метода неопределённых коэффициентов. Рассмотрим этот метод на примере:

Рассмотрим функцию $ f(x_1, x_2, x_3) = (0 0 1 1 1 0 0 1) $. В общем виде полином Жегалкина для этой функции имеет вид:

$\displaystyle f(x_1, x_2, x_3) = a_{1 2 3} x_1 x_2 x_3 \oplus a_{1 2} x_1 x_2 \......\oplus a_{1 3} x_1 x_3 \oplus a_1 x_1 \oplus a_2 x_2 \oplus a_3 x_3 \oplus a_0$

Вычислим все коэффициенты начиная с $ a_0$, последовательно подставляя в полином известные значения функции $ f$:

\begin{displaymath}\begin{array}{l}f (0, 0, 0) = a_0 = 0,\\f (0, 0, 1) = a_3...... = a_{1 2 3} \oplus 1 = 1 \Rightarrow a_{1 2 3} = 0\end{array}\end{displaymath}

Таким образом, функция имеет вид:

$\displaystyle f(x_1, x_2, x_3) = x_1 x_3 \oplus x_1 \oplus x_2$

и не является линейной.

Теорема Поста

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

класс функций сохраняющих 0
$ f \in T_0 \Leftrightarrow f(0, 0, \dots 0) = 0$,
класс функций сохраняющих 1
$ f \in T_1 \Leftrightarrow f(1, 1, \dots 1) = 1$,
класс самодвойственных функций
$ f \in S \Leftrightarrow (\forall\alpha)(f(\overline{\alpha}) = \overline{f(\alpha)})$,
класс монотонных функций
$ f \in M \Leftrightarrow (\forall \alpha, \beta)(\alpha\leqslant \beta \Rightarrow f(\alpha) \leqslant f(\beta))$, где подразумевается стандартный порядок булевой алгебры (при котором существуют и несравнимые элементы!),
класс линейных функций
$ f = \sum\limits_{i \in \overline{1, n}} a_i x_i \oplus a_0$, т.е. функция представима в виде полинома Жегалкина первой степени.

Можно доказать, что все эти классы являются замкнутыми, т.е. любая комбинация функций из одного класса остаётся в том же классе.

Теорема (Поста): система булевых функций полна тогда и только тогда, когда она целиком не лежит ни в одном из классов Поста.

Рассмотрим пример: $ f(x_1, x_2, x_3) = x_1 (\overline{x_1} \vert x_3) (\overline{x_1} \oplus\overline{x_3}) \rightarrow (x_2 \sim x_3), w = (1 1 1 0 0 1 1 0)$. Необходимо проверить полноту системы $ \{f, w\}$.

Функция $ f$ принимает следующие значения: $ f = (1 1 1 1 1 1 0 1)$. Проверка принадлежности первых четырёх классов поста может быть проведена очень быстро. Для проверки линейности построим представление данных функций в виде полинома Жегалкина:

\begin{displaymath}\begin{array}{l}f (0, 0, 0) = a_0 = 1,\\f (0, 0, 1) = a_3...... 0 \oplus 0 \oplus 1 = 1\Rightarrow a_{1 2 3} = 1.\end{array}\end{displaymath}

Поучается, что $ f = x_1 x_2 x_3 \oplus x_1 x_2 \oplus 1$ нелинена.

\begin{displaymath}\begin{array}{l}w (0, 0, 0) = a_0 = 1,\\w (0, 0, 1) = a_3...... 0 \oplus 0 \oplus 1 = 0\Rightarrow a_{1 2 3} = 1.\end{array}\end{displaymath}

Поучается, что $ w = x_1 x_2 x_3 \oplus x_1 x_2 \oplus x_2 x_3 \oplus x_1 x_3 \oplus x_1\oplus 1$ нелинена.

Принадлежность классам Поста обощим в таблице:

  $ T_0$ $ T_1$ $ S$ $ M$ $ L$
$ f$ - + - - -
$ w$ - - - - -

Система функций $ \{f, w\}$ является полной, более того, полной является уже система $ \{ w\}$.

Выразим стандартный базис $ \{ \wedge, \overline{\phantom{x}}\}$ через функцию $ w$. Воспользуемся тем, что $ w$ не сохраняет ни 0, ни 1, значит:

$\displaystyle w(x, x, x) = \overline{x}.$

Так как $ w$ -- несамодвойственна, выразим константы через отрицание. Для этого найдём такой вектор $ \alpha$, что $ w(\alpha) = w(\overline{\alpha})$. Видно, что это выполняется при $ \alpha = (0 1 0)$. Значит, $ w(\overline{x}, x, \overline{x}) = w(x, \overline{x},x) = 1$. Тогда 0 можно получить с помощью отрицания.

$ w$ -- нелинейна, выразим коньюнкцию из полинома Жегалкина этой функции. Можно получить, что $ w(x_1, x_2, 0) = x_1 x_2 \oplus x_1 \oplus 1$. Тогда

$\displaystyle w(x_1, x_2 \oplus 1, 0) \oplus 1 = x_1 (x_2 \oplus 1) \oplus x_1 \oplus 1 \oplus 1 = x_1 x_2,$

откуда $ x y = \overline{w(x, \overline{y}, 0)}$.

Схемы из функциональных элементов

Часто для формального задания булевых функций используется схемы из функциональных элементов (СФЭ) -- графы специального вида, основу которых составляют собственно функциональные элементы, т.е. булевы функции, принимающие на вход переменные и выдающие результат.

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

Рис. 1: Функциональные элементы для стандартных функций
\includegraphics[width=5cm]{schema_std.eps}

Рис. 2: СФЭ для функции исключающего или
\includegraphics[width=8cm]{schema_xor.eps}

Аналогичным образом могут быть построены схемы для булевых функций любой сложности. В электронике часто используются схемы, выполняющие сложение битовых переменных. Такие схемы называются сумматорами. Таблица истинности для булевых функций сложения двух $ x_1 +x_2 = y_1 y_2$ и трёх $ x_1 + x_2 + x_3 = y_1 y_2$ однобитовых (булевых) переменных содержит два столбца результата (результат имеет большее число разрядов, чем аргументы), т.е. мы имеем две булевых функции для каждой из операций сложения:

$ x_1$ $ x_2$ $ y_1$ $ y_2$
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0
$ x_1$ $ x_2$ $ x_3$ $ y_1$ $ y_2$
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 1 1

СФЭ для сумматора сложения трёх переменных представлен на рисунке 3. Удобство использования этого сумматора таково, что на его основе можно стоить сумматоры для сложнения сколь угодно больших чисел. Например, на рисунке 4 проказан сумматор для сложения двух трёхразрядных переменных $ x_1 x_2 x_3 + y_1 y_2 y_3 = z_1 z_2 z_3 z_4$:

Рис. 3: СФЭ сумматора
\includegraphics[width=8cm]{schema_sum3.eps}

Рис. 4: СФЭ для сумматора трёхразрядных переменных
\includegraphics[width=8cm]{schema_sum_many.eps}

Графы

В теории графов выделяют два вида графов: неориентированные и ориентированные.

Неориентированные графы

Неориентированным графом называют пару $ (V, E)$, где $ V$ -- конечное множество вершин, а $ E$ -- множество рёбер такое, что $ E \subseteq \{ \{v, w\} \vert v, w\in V \And v \neq w \}$. Важно, что рёбра могут соединять какие-то две вершины. Вершины можно представить в виде точек на плоскости, а дуги -- линиями, их соединяющими. При этом для нас представляют интерес не координаты точек или длина и форма линий, а связь между дугами и вершинами.

На рисунке 5 показаны примеры неориентированных графов. Граф (а) определяется как:

\begin{displaymath}\begin{array}{l}V = \{\mbox{\lq\lq Киев''}, \mbox{\lq\lq Лондон''}, \......ва''}\}, \{\mbox{\lq\lq Лондон''},\mbox{\lq\lq Москва''}\}\}.\end{array}\end{displaymath}

А вот в графе (в) все вершины соедины с каким-либо ребром:

\begin{displaymath}\begin{array}{l}V = \{1, 2, 3, 4, 5, 6, 7\},\\E = \{\{1,2......},\{1,7\},\{2,4\},\{2,5\},\{3,6\},\{4,5\},\{6,7\}\}\end{array}\end{displaymath}

Рис. 5: Примеры неориентированных графов
\includegraphics[width=13cm]{graph_examples.eps}

Можно легко получить число возможных графов для заданного числа вершин $ \vert V\vert =n$. Максимальное число рёбер в таком графе -- число неупорядоченных пар из $ n$, т.е. $ C_n^2 = \frac{n (n - 1)}{2}$. Тогда общее число неориентированных графов равно мощности множества подмножеств всех рёбер, т.е. $ 2^{\frac{n (n - 1)}{2}}$.

Для каждой вершины вводится понятие степени:

$\displaystyle dg(v) = \vert\{ u \vert \{u, v\} \in E\}\vert,$

т.е. число рёбер, соединённых с вершиной.

Цепью в графе называют произвольную конечную или бесконечную последовательность вершин, в которой каждая последующая соединена ребром с предыдущей. Для конечной цепи число рёбер в ней называют длиной. Цепь называется простой, если все её вершины, кроме, быть может, первой и последней, попарно различны и все её рёбра попарно различны. Простая цепь ненулевой длины, начало и конец которой совпадают, называется циклом. Неориентированный граф, не имеющий циклов называют ацикличным. На рисунке 6 показаны цепь, простая цепь и цикл.

Рис. 6: Цепь, простая цепь и цикл
\includegraphics[width=13cm]{graph_chain.eps}

Подграфом $ \mathcal{G}' = (V', E')$ графа $ \mathcal{G} = (V, E)$ называют такой граф, что: $ V' \subseteq V \And E' \subseteq E$. Так как $ \mathcal{G}'$ -- граф, в нём не могут быть только вершины, соединённые с ребрами. Подграф называется остовным, если $ V = V'$.

Неориентированный граф называется связным, если в нём любые две вершины соединены цепью. Максимальный связный подграф -- компонента связности этого графа (или просто компонента). Компоненты не имеют ни общих вершин, ни общих рёбер.

Для двух вершин можно ввести бинарное отношение достижимости: $ u v$ выполняется, когда вершины $ u$ и $ v$ можно соединить цепью. Можно доказать, что это отношение является отношением эквивалентности. Тогда граф может быть факторизован, и элементами фактор-множества будут являться компоненты данного графа. На рисунке 7 показан пример графа из нескольких компонент связности.

Рис. 7: Компоненты неориентированного графа
\includegraphics[width=7cm]{graph_com.eps}

Особый интерес представляют особые виды графов. Ациклический связный граф называется деревом. Обычно в дереве одна из вершин выделяется в качестве корня. Более общим случаем дерева является лес: граф, состоящий из двух и более деревьев (ациклический граф). Вершины, степень которых равна 1 и не являющиеся корнем, называют листьями. Граф, состоящий только из корня и листьев, называют кустом. На рисунке 8 показаны дерево, куст и лес.

Рис. 8: Дерево, куст и лес
\includegraphics[width=10cm]{graph_tree.eps}

Помимо перечисления множеств $ V$ и $ E$, неориентированные графы можно представлять в виде матрицы смежности: матрица имеет квадратный и симметрический вид, размером $ n\times n$, где $ n$ -- число вершин. Элементы матрицы равны:

\begin{displaymath}a_{i,j} = \left\{\begin{array}{l}1, \mbox{если}\, \{v_i, ......\0, \mbox{если}\, \{v_i, v_j\} \notin E.\end{array}\right.\end{displaymath}

Для графа на рисунке 5, (а) матрица смежности будет иметь вид:

\begin{displaymath}A = \left(\begin{array}{cccc}1 & 1 & 0 & 0\\1 & 1 & 1 & 0\\0 & 1 & 1 & 0\\0 & 0 & 0 & 1\end{array}\right)\end{displaymath}

Другой матрицей, представляющей для нас интерес, является матрица достижимости, размер которой также $ n\times n$. Элементы матрицы равны:

\begin{displaymath}a_{i,j} = \left\{\begin{array}{l}1, \mbox{если}\, v_i \Rightarrow^* v_j\\0, \mbox{иначе}.\end{array}\right.\end{displaymath}

В том же примере матрица достижимости отличается от матрицы смежности:

\begin{displaymath}C = \left(\begin{array}{cccc}1 & 1 & 1 & 0\\1 & 1 & 1 & 0\\1 & 1 & 1 & 0\\0 & 0 & 0 & 1\end{array}\right)\end{displaymath}

Оринтированные графы

Ориентированный граф отличается наличием направления на дугах, соединяющих вершины. Ориентированный граф определяется как пара $ (V, E)$, где $ V$ -- множество вершин, как в неориентированном графе, а $ E \subseteq V \times V$ -- множество дуг. Каждая дуга -- упорядоченная пара вершин, стрелка на которой направлена от первой вершины ко второй. Отметим также, что в случае неориентированного графа возможны петли, т.е. дуги вида $ (v, v)$. На рисунке 9 показан пример ориентированного графа. Для него множество вершин и дуг равно:

\begin{displaymath}\begin{array}{l}V = \{\mbox{\lq\lq Вася''}, \mbox{\lq\lq Гога''}, \mb......x{\lq\lq Оля''}), \\(\mbox{\lq\lq Оля''}, \mbox{\lq\lq Оля''})\}\end{array}\end{displaymath}

Рис. 9: Пример ориентированного графа
\includegraphics[width=7cm]{ograph_example.eps}

Число ориентированных графов для заданного числа вершин больше, чем неориентированных. Всего между $ n$ вершинами можно провести $ n^2$ дуг (число упорядоченных пар). Значит число графов будет равно мощности множества подмножеств всех дуг: $ 2^{n^2}$.

Для ориентированных графов степень вершины состоит из двух частей:

полустепень захода
$ dg^{-}(v) = \vert\{ v \vert (w, v) \in E\}\vert$ -- число дуг, входящих в вершину;
полустепень исхода
$ dg^{+}(v) = \vert\{ v \vert (v, w) \in E\}\vert$ -- число дуг, исходящих из вершины.

Например, для вершины ``Оля'' на рисунке 9 полустепень захода равна 3, а полустепень исхода -- 1.

Аналогом цепи в ориентированных графах является путь -- при этом движение возможно только в направлении стрелок. Также определяется и простой путь, а аналог цикла называется контуром.

В ориентированных графах определяется три вида связности:

связность
Ориентированный граф называется связным (просто связным, связным односторонне), если $ (\forall v, u \in V)(v \Rightarrow^* u \vee u \Rightarrow^* v)$, т.е. существует путь нулевой или большей длины из $ u$ в $ v$ или из $ v$ в $ u$.
сильная связность
Ориентированный граф называется сильно связным (связным двусторонне), если $ (\forall v, u \in V)(v \Rightarrow^* u \And u \Rightarrow^* v)$, т.е. существуют пути нулевой или большей длины из $ u$ в $ v$ и из $ v$ в $ u$.
слабая связность
Ориентированный граф называется слабо связным, если соответствующий ему неориентированный граф (стереть все стрелочки и удалить петли) связен.

На рисунке 10 показаны связный, сильно и слабо связные подграфы исходных графов.

Рис. 10: Связность в ориентированных графах
\includegraphics[width=12cm]{ograph_conn.eps}

Ориентированное дерево определяется следующим образом:

  1. $ dg^-(v) \leqslant 1$ для всех вершин;
  2. $ dg^-(v) = 0$ для единственной вершины, называемой корнем;
  3. в графе нет контуров.

Куст и лес определяются аналогично. Граф более общего вида, не имеющий контуров, называется сетью.

Ориентированные графы также могут задаваться матрицей смежности. В этом случае элементы матрицы равны:

\begin{displaymath}a_{i,j} = \left\{\begin{array}{l}1, \mbox{если}\, (v_i, v......,\\0, \mbox{если}\, (v_i, v_j) \notin E.\end{array}\right.\end{displaymath}

Такая матрица уже не является в общем случае симметричной. Для графа на рисунке 9 матрица будет равна:

$\displaystyle A = \left(\begin{array}{ccccccc}0 & 0 & 0 & 1 & 0 & 0 & 0\\0 &......0\\0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0\end{array}\right)$

Аналогично определяется и матрица достижимости. Для нашего примера такая матрица будет равна:

$\displaystyle C = \left(\begin{array}{ccccccc}1 & 0 & 0 & 1 & 0 & 0 & 0\\0 &......0\\0 & 0 & 0 & 0 & 0 & 1 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 1\end{array}\right)$

Все семинары:
В виде PDF
Исходный вариант

Sat, Apr. 8th, 2006 10:47 am (UTC)
me_koorych

божественно!!