?

Log in

No account? Create an account

Thu, Mar. 23rd, 2006, 02:03 am
Третий семинар

Тема: Кольца. Булевы функции. Минимизация ДНФ.. Читаем, комментируем, решаем ДЗ.

Исследование группоидов

Рассмотрим ещё один пример группоида и исследуем свойства его бинарной операции. $ \mathcal{A}(\mathbb{R}, \circ)$, где $ (\forall x, y) (x \circ y = y)$.

Очевидно, что эта операция некоммутативна, так как $ x \circ y = y \neq y \circ x =x$. С другой стороны, ассоциативность может быть доказана следующим образом:

\begin{displaymath}\begin{array}{l}x \circ (y \circ z) = x \circ z = z\\(x \circ y) \circ z = y \circ z = z\end{array}\end{displaymath}

Значит, это полугруппа. При попытке найти нейтральный элемент, получим:

$\displaystyle x \circ \varepsilon = x \Leftrightarrow \varepsilon = x,$

это значит, что нейтральный элемент не существует, и данная алгебра - не моноид.

Кольца, тела и поля

Алгебраическую структуру с двумя бинарными операциями $ \mathcal{R}(R, +, \cdot, 0, 1)$ называется кольцом, если выполняются следующие соотношения:

  • $ a + (b + c) = (a + b) + c$;
  • $ a + b = b + a$;
  • $ a + 0 = a$;
  • $ (\forall a)(\exists -a: a + (-a) = 0)$;
  • $ a \cdot (b \cdot c) = (a \cdot b) \cdot c$;
  • $ a \cdot 1 = 1 \cdot a = a$;
  • $ a \cdot (b + c) = a \cdot b + a \cdot c$ и $ (a + b) \cdot c = a \cdot c + b \cdot c$.

Другими словами, алгебра $ (R, +, 0)$ является абелевой группой, алгебра $ (R,\cdot, 1)$ -- моноидом, а операция умножения дистрибутивна относительно сложния.

Можно доказать, что в кольце имеет место аннулирующее свойство нуля: $ a \cdot 0 = 0 \cdota = 0$.

В качестве примеров колец можно привести:

  • кольцо действительных чисел с привычными операциями сложения и умножения -- $ (\mathbb{R}, +, \cdot, 0, 1)$. Действительно, по сложению имеем абелеву группу, тогда как по умножению -- лишь моноид (обратный к нулю элемент не определён).
  • кольцо квадратных матриц степени $ n$ -- $ (M_n, +, \cdot, 0, E)$, где 0 и $ E$ -- соответственно нулевая и единичная матрица. Также только моноид по умножению, потому что обратная матрица существует не для каждой квадратной матрицы.

В некоторых кольцах существуют делители нуля, т.е. такие элементы $ a, b \neq 0$, что $ a \cdot b = 0$. Для обычной арифметики это кажется удивительным и не выполняется, тогда как для приведённого выше примера кольца матриц можно найти делители нуля:

\begin{displaymath}\left(\begin{array}{cc}1 & 0 \\0 & 0 \\\end{array}\r......ft(\begin{array}{cc}0 & 0 \\0 & 0 \\\end{array}\right)\end{displaymath}

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

Кольца рациональных, действительных и комплексных чисел с операциями арифметического сложения и умножения являются полями.

Задания для самоподготовки. Задана алгебра $ (X, +, *)$ с двумя бинарными операциями. Проверить свойства этой операции и указать, к какому типу эта алгебра относится.
  • $ X = M_n^d$ -- множество диагональных матриц степени $ n$;
  • $ X = 2^A$, $ +$ -- $ \bigtriangleup$, симметрическая разность множеств, а $ *$ -- $ \cap$, пересечение множеств;
  • $ X = \mathbb{R}[x]$ -- множество многочленов от переменной $ x$ с действительными коэффициентами.

Кольцо вычетов

Важным примером кольца является кольцо вычетов по модулю $ k$: $ \mathbb{Z}_k(\{0, 1,\dots, k - 1\}, \oplus_k, \odot_k, 0, 1)$. Для разных $ k$ это кольцо может обладать разными свойствами. Рассмотрим два случая: $ k = 4$ и $ k = 5$.

При $ k = 4$ имеем следующие таблицы сложения и умножения по модулю 4:

$ \oplus_4$ 0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 2
$ \odot_4$ 0 1 2 3
0 0 0 0 0
1 0 1 2 3
2 0 2 0 2
3 0 3 2 1

Видно, что элемент 2 является делителем нуля: $ 2 \odot_4 2 = 0$.

При $ k = 5$ имеем следующие таблицы сложения и умножения по модулю 5:

$ \oplus_5$ 0 1 2 3 4
0 0 1 2 3 4
1 1 2 3 4 0
2 2 3 4 0 1
3 3 4 0 1 2
4 4 0 1 2 3
$ \odot_5$ 0 1 2 3 4
0 0 0 0 0 0
1 0 1 2 3 4
2 0 2 4 1 3
3 0 3 1 4 2
4 0 4 3 2 1

Здесь делителей нуля нет, а для каждого ненулевого элемента можно найти обратный по умножению: $ 1^{-1} = 1, 2^{-1} = 3, 3^{-1} = 2, 4^{-1} = 4$. Т.е. данное кольцо вычетов является полем.

Можно доказать, что кольцо вычетов является полем тогда и только тогда, когда $ k$ -- простое число.

В кольцах вычетов можно решать уравнения и системы уравнений. Например решим данные уравнения в кольце $ \mathbb{Z}_7$, для простоты умножение и сложение по модулю 7 будем обозначать стандартными знаками полюса и умножения:

$\displaystyle \left\{\begin{array}{ll}2 x + 3 y = 1,\\3 x - y = 2\end{array......ht.\left\{\begin{array}{ll}y = 3 x - 2,\\4 x = 0, x = 0\end{array}\right.$

$\displaystyle \left\{\begin{array}{ll}x = 0,\\y = 5\end{array}\right.$

или в кольце вычетов $ \mathbb{Z}_5$:

\begin{displaymath}\begin{array}{c}x^3 + x^2 + 4 x - 1 = 0\\x^3 + x^2 + 4 ......1)(x^2 + 4) = 0\\x_1 = 4,\\x_2^2 = 1, x_2 = 1\end{array}\end{displaymath}

Задания для самоподготовки. Решить систему уравнений или алгебраическое уравнение в полях $ \mathbb{Z}_5$ и $ \mathbb{Z}_7$:
  • $ \left\{\begin{array}{ll}-4 x + 3 y = 1,\\x + 2 y = 3\end{array}\right.$
  • $ \left\{\begin{array}{ll}-x + 3 y = 1,\\3 x + y = 2\end{array}\right.$
  • $ x^3 - x + 1 = 0$.

Подалгебры

Пусть дана алгебра $ \mathcal{A}(A, \Omega)$ и множество $ B \subset A$, такое, что $ \mathcal{B}(B, \Omega)$ -- тоже алгебра с теми же операциями. Тогда $ \mathcal{B}$ -- подалгебра $ \mathcal{A}$.

В качестве примеров подалгебр можно привести:

  • группу $ (\mathbb{Q}, +, 0)$ и её подгруппу $ (\mathbb{Z}, +, 0)$;
  • кольцо $ (\mathbb{R}, +, \cdot, 0, 1)$ и его подкольцо $ (\mathbb{Z}, +, \cdot, 0, 1)$.

А вот алгебра $ (\mathbb{N}_0, +, 0)$ не является подгруппой $ (\mathbb{Z}, +, 0)$, так как не обладает свойствами группы (является лишь моноидом и соответственно подмоноидом $ (\mathbb{Z}, +, 0)$).

Задания для самоподготовки. Для данной группы (кольца) $ M$ поверить, является ли $ H$ её подгруппой (подкольцом):
  • $ M = (\mathbb{C} \setminus \{ 0 \}, \cdot), H = \{ x \in \mathbb{R}, x > 0 \}$;
  • $ M = (C[a, b], +, \cdot)$, $ C$ -- класс функций, непрерывных на отрезке, $ H = \{f \in C[a, b]: f(a) + f(b) = 0 \}$;
  • $ M = (V_3, +), H = \{ \vec{a} \in V_3; (\vec{a}, \vec{n}) = 0 \}$ ($ \vec{n}$ -- заданный вектор).

Полукольца

Определение полукольца аналогично определению полугруппы -- снимается требование существования обратного элемента по сложению (из двух полуколец можно получить кольцо, как и в случае группы):

  • $ a + (b + c) = (a + b) + c$;
  • $ a + b = b + a$;
  • $ a + 0 = a$;
  • $ a \cdot (b \cdot c) = (a \cdot b) \cdot c$;
  • $ a \cdot 1 = 1 \cdot a = a$;
  • $ a \cdot (b + c) = a \cdot b + a \cdot c$ и $ (a + b) \cdot c = a \cdot c + b \cdot c$;
  • $ a \cdot 0 = 0 \cdota = 0$;

Если операция сложения в полукольце идемпотентна: $ x + x = x$, то такое полукольцо называют идемпотентным полукольцом, иногда их называют просто полукольцами. Пример такого полукольца:

$\displaystyle (\mathbb{R}^+ \cup \{ +\infty \}, \min, +, +\infty, 0)$

.

Действительно, операция взятия минимума идемпотентна и $ +\infty$ является по ней нейтральным элементом.

Если операция умножения обладает также свойствами идемпотентности и коммутативности, то такое полукольцо называют симметричным.

Пример симметричного полукольца: алгебра подмножеств множества $ A$: $ (2^A, \cup, \cap,\varnothing, A)$.

Булевы алгебры

Симметричное полукольцо, в котором для каждого элемента $ x$ существует дополнение $ \overline{x}$ такое, что $ x + \overline{x} = 1$ и $ x \cdot \overline{x} = 0$, называется булевой алгеброй.

Самый распространённым примером булевой алгебры является двухэлементная булева алгебра: $ \mathcal{B} (\{0, 1\}, \vee, \wedge, 0, 1)$. Интересно, что приведённое выше симметричное полукольцо подмножеств множества $ A$ также является булевой алгеброй, в которой дополнение определяется как $ \overline{X} = A \setminus X$.

Также представляет интерес $ n$-компонентная булева алгебра:

$\displaystyle \mathcal{B} (\{0, 1\}^n, \vee, \wedge, \mathbf{0}, \mathbf{1}),$

где операции $ \vee$ и $ \wedge$ определены на булевых векторах из $ n$ элементов, а $ \mathbf{0}$ и $ \mathbf{1}$ -- соответственно нулевой и единичный вектор. Нетрудно показать, что это также булева алгебра.

В $ n$-элементной булевой алгебре определяется стандартное отношение порядка (покомпонентное сравнение): $ \overline{\alpha} = \overline{\beta} \Leftrightarrow \alpha_i \leqslant \beta_i, i =\overline{1, n}$. Диаграммы Хассе для этого отношения булевой алгебры первого, второго и третьего порядка показаны на рисунке 1.

Рис. 1: Диаграмма Хассе для стандартного отношения порядка булевой алгебры
\includegraphics[width=10cm]{hass_bool.eps}

Булевы функции

Булева функция -- это отображение вида $ f: \{0, 1\}^n \rightarrow {0, 1}$, где $ n$ -- число булевых переменных. В общем случае это скалярная функция векторного переменного.

Важное свойство булевых функции -- их число конечно для заданного $ n$ и равно $ 2^{2^n}$. То есть, каждая функция может быть задана своей таблицей истинности или просто пронумерована.

При $ n = 0$ существует только две функции-константы: 0 и 1.

Рассмотрим все функции для $ n = 1$:

$ x$ $ f_1$ $ f_2$ $ f_3$ $ f_4$
0 0 0 1 1
1 0 1 0 1

$ f_1(x) = 0, f_4(x) = 1$ -- константы, $ f_2(x) = x$ -- тождественная функция, $ f_3(x) =\overline{x}$ -- дополнение.

Рассмотрим все функции для $ n = 2$:

$ x_1$ $ x_2$ $ f_1$ $ f_2$ $ f_3$ $ f_4$ $ f_5$ $ f_6$ $ f_7$ $ f_8$ $ f_9$ $ f_{10}$ $ f_{11}$ $ f_{12}$ $ f_{13}$ $ f_{14}$ $ f_{15}$ $ f_{16}$
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

$ f_1(x_1, x_2) = 0, f_{16}(x_1, x_2) = 1$ -- константы, $ f_2(x_1, x_2) =x_1~\wedge~x_2$ -- коньюнкция, $ f_7(x_1, x_2) = x_1~\oplus~x_2$ -- исключающее или, $ f_8(x_1, x_2) = x_1~\vee~x_2$ -- дизъюнкция, $ f_9(x_1, x_2) = x_1~\downarrow~x_2$ -- стрелка Пирса, $ f_{10}(x_1, x_2) = x_1~\sim~x_2$ -- эквивалентность, $ f_{14}(x_1, x_2) =x_1~\rightarrow~x_2$ -- импликация, $ f_{15}(x_1, x_2) = x_1~\vert~x_2$ -- штрих Шефера.

Таким образом, каждая булева функция может быть представлена в виде таблицы истинности, так и в виде формулы.

ДНФ

Элементарная коньюнкция -- формула вида $ x_i^{\alpha_i} \wedge x_j^{\alpha_j} \wedge \dotsx_k^{\alpha_k}$, где при $ \alpha_i = 0$ используется дополнение переменной, а при $ \alpha_i= 1$ -- сама переменная. Пример элементарной коньюнкции: $ x_1 \overline{x_3} x_4 $.

Дизъюнктивная нормальная форма -- это формула вида $ K_1 \vee K_2 \vee \dots K_m$, где $ K_i$ -- элементарная коньюнкция.

Можно доказать, что любая функция может быть представлена в виде ДНФ.

Карта Карно

Для иллюстрации значения булевой функции, а также для получения её ДНФ используются карты Карно -- форма изображения булевой функции в виде таблицы, строки и столбцы которой обозначают отдельные переменные.

Например, карта Карно для функции от трёх переменных $ f = (0 0 1 0 1 1 1 0)$ будет иметь вид:

  $ x_2$ $ x_3$ 0 0 0 1 1 1 1 0
$ x_1$          
0   0 0 0 1
1   1 1 0 1

Отметим, что значение переменных в соседних столбцах и строках карты Карно должны быть сравнимы.

Для каждой единицы в карте Карно можно выписать элементарную коньнкцию, с помощью которой она получается -- например, единица при $ x_1 = 0$ и $ x_2 x_3 = 1 0$ может быть представлена в виде коньюнкции $ \overline{x_1} x_2 \overline{x_3}$. Дизъюнкция всех таких коньюнкций, соответвтующих единицам, даст нам ДНФ данной функции.

Минимизация ДНФ

Минимальной булевой функцией называется функция, ДНФ которой содержит минимальное число элементарных коньюнкций (а если число коньюнкций равно, то число переменных в коньюнкциях меньше).

Алгоритм минимизации булевой функции состоит из следующих этапов:

  1. Построение карты Карно для заданной функции.
  2. Выделение склеек. Склейка -- область, покрывающая только единицы на карте Карно, размер которой равен степени двух. Такая область может быть представлена в виде элементарной коньюнкции. При этом необходимо выделять склейки макимально большого размера. Дизъюнкция всех коньюнкций склеек даёт сокращённую ДНФ.
  3. Определение ядра. Ядро -- набор склеек, каждая из которых покывает единицы, не покрываемые ни одной другой склейкой. Такие склейки нахзывают ядровыми. Если в ядро входят все склейки, то минимальная ДНФ равна сокращённой, конец алгоритма.
  4. Если существуют склейки, целиком попадающие в ядро, их можно выбросить. В результате получится ДНФ Квайна.
    1. Если ядро покрывает все единицы, то минимизация закончена.
    2. Если есть единицы, не покрываемые ядерными склейками, то строится функция Патрика: для каждой из таких единиц строится дизъюнкция вида $ K_1 \vee K_2 \vee \dots K_m$, где $ K_i$ -- коньюнкция склейки, покрывающецй данную единицу. Такие дизъюнкции объединяются в общую коньюнкцию, которая и носит название функции Патрика. После раскрытия скобок и сокращения получется дизънкция нескольких наборов коньюнкций, каждый из таких наборов представляет собой отдельную альтернативу, покрывающую все единицы, не попавшие в ядро. Каждая такая альтернатива, объединённая с ядром, даёт одну из возможных минимальных ДНФ, или одну из тупиковых ДНФ.

Рассмотрим пример минимизации булевой функции $ f = (0 0 1 0 1 1 1 0)$. На рисунке 2 показана карта Карно для этой функции.

Рис. 2: Пример минимизации ДНФ с помощью карты Карно
\includegraphics[width=10cm]{karno_1.eps}

Всего можно выделить три склейки: $ K_1$, $ K_2$ и $ K_3$. В ядро входят $ K_1$ и $ K_3$, тогда как $ K_2$ может быть выброшена. В данном случае ДНФ квайна и минимальная ДНФ совпадают: $ f = K_1 \vee K_3 = x_2 \overline{x_3} \vee x1 \overline{x_2}$.

На рисунке 3 показана карта Карно похожей функции. В этом случае ядро $ K_1$ и $ K_4$ не покрывает все единицы функции.

Рис. 3: Пример минимизации ДНФ с помощью карты Карно
\includegraphics[width=10cm]{karno_2.eps}

Для единицы на пересечении $ K_2$ и $ K_3$ функция Патрика будет иметь вид: $ K_2 \veeK_3$. Дальнейшее упрощение не возможно, имеем две альтернативы. Значит, тупиковые ДНФ можно записать в виде:

\begin{displaymath}f = K_1 \vee K_4 \vee \left\{\begin{array}{l}K_2\\K_3......eft\{\begin{array}{l}x_1 x_3\\x_1 x_2\end{array}\right.\end{displaymath}

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

Рис. 4: Пример минимизации ДНФ с помощью карты Карно
\includegraphics[width=10cm]{karno_3.eps}

В этом случае функция Патрика будет иметь шесть сомножителей -- по одному на единицу: Ф.П. = $ (K_1 \vee K_2) (K_2 \vee K_3) (K_3 \vee K_4) (K_4 \vee K_5) (K_5 \vee K_6)(K_6 \vee K_1)$ = $ (K_1 K_2 \vee K_2 \vee K_2 K_3 \vee K_1 K_3) (K_3 K_4 \vee K_4 \vee K_3K_5 \vee K_4 K_5) (K_5 \vee K_6)$ = $ (K_2 \vee K_1 K_3) (K_4 \vee K_3 K_5) (K_5 \vee K_6)$ = $ (K_2 K_4 \vee K_1 K_3 K_4 \vee K_1 K_3 K_5 \vee K_2 K_3 K_5) (K_5 \vee K_6)$ = $ K_2 K_4 K_6 \vee K_1 K_3 K_5 $.

В результате имеем две альтернативы, две тупиковые ДНФ:

\begin{displaymath}f = \left\{\begin{array}{l}K_1 \vee K_3 \vee K_5\\K_2 ...... x_1 x_2 \vee \overline{x_1} \overline{x_3}\end{array}\right.\end{displaymath}

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