Минимизация булевых функций

Ясно, что при разработке логических схем, немаловажной является задача минимизации количества используемых элементов (другими словами, логических операций).

В связи с этим, возникает задача минимизации логических функций в некотором классе формул. В частности, в классах ДНФ и КНФ.

Минимальная ДНФ

Такая ДНФ, которая содержит наименьшее общее число вхождений переменных по сравнению со всеми равносильными ей ДНФ.

Минимальная КНФ

Такая КНФ, которая содержит наименьшее общее число вхождений переменных по сравнению со всеми равносильными ей КНФ.

Процесс нахождения минимальных форм, собственно, и называется минимизацией. В простых случаях, для минимизации достаточно тождественных преобразований. В более сложных – используются специальные алгоритмы.

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

\[ \;\overline{x_1}\;x_2x_3x_4 \vee \;\overline{x_1}\;x_2\;\overline{x_3}\;x_4 = \;\overline{x_1}\;x_2x_4 (x_3 \vee\;\overline{x_3}\;) = \;\overline{x_1}\;x_2x_4 \mathbin{\&}1 = \;\overline{x_1}\;x_2x_4. \]

Аналогично для КНФ:

\[ (\;\overline{x_1}\;\vee x_2\vee x_3\vee x_4) (\;\overline{x_1}\;\vee x_2\vee\;\overline{x_3}\;\vee x_4) = \;\overline{x_1}\;\vee x_2\vee x_4\vee x_3\;\overline{x_3}\; = \;\overline{x_1}\;\vee x_2\vee x_4\vee 0 = \;\overline{x_1}\;\vee x_2\vee x_4. \]

Возможность поглощения следует из очевидных равенств

\[ A \vee\;\overline{A}\; = 1 \]\[ A\;\overline{A}\; = 0. \]

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

Минимизирующие карты Карно

Карта Карно

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

Карты Карно можно рассматривать как определенную плоскую развертку n-мерного булева куба.

Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы.

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

Булевы функции \(N\) переменных, представленные в виде СДНФ или СКНФ, могут иметь в своём составе \(2^N\) различных элементарных членов.

Элементарные члены СДНФ или СКНФ образуют структуру, топологически эквивалентную \(N\)-мерному кубу. Действительно, если рассматривать набор значений функции \(x_1,\,\ldots,\,x_N\) как \(N\)-мерный вектор \(\{x_1,\,\ldots,\,x_N\}\), мы получим набор точек, лежащих на ортах \(N\)-мерной системы координат, и удаленных друг от друга на \(1\). Другими словами, мы получим \(N\)-мерный гиперкуб с ребром \(1\).

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

можно построить эквивалентный ей квадрат:

Или, если обозначить вершины соответствующими элементарными конъюнкциями и выделить вершины, конъюнкции которых входят в СДНФ:

Или СКНФ:

Можно заметить, что члены, находящиеся на одной стороне квадрата, могут быть склеены. Соответственно, если составляется ДНФ, то операции производятся только над вершинами, в которых функция имеет значение \(1\) (по правилам построения СДНФ). Если же составляется КНФ, то над вершинами, в которых функция имеет значение \(0\) (по правилам построения СКНФ).

При этом, сохраняются переменные, значение которых на стороне постоянно.

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

Как видно из рисунка, для трёхмерного случая возможны более сложные конфигурации. Например, четыре члена, принадлежащие одной грани куба, объединяются в один с поглощением двух переменных:

\[ \;\overline{x_1}\;\;\overline{x_2}\;\;\overline{x_3}\; \vee x_1\;\overline{x_2}\;\;\overline{x_3}\; \vee \;\overline{x_1}\;\;\overline{x_2}\;x_3 \vee x_1\;\overline{x_2}\;x_3 =\]

\[ = \;\overline{x_2}\; (\;\overline{x_1}\;\;\overline{x_3}\; \vee\;\overline{x_1}\;x_3 \vee x_1\;\overline{x_3}\; \vee x_1x_3) = \;\overline{x_2}\; (\;\overline{x_1}\; \vee x_1)(\;\overline{x_3}\; \vee x_3) = \;\overline{x_2}\; \]

В общем случае можно сказать, что \(2^K\) членов, принадлежащие одной \(K\)–мерной грани гиперкуба, склеиваются в один член, при этом поглощаются \(K\) переменных.

Карта Карно представляет собой развертку гиперкуба на плоскость. Например, трехмерный куб из предыдущего примера можно развернуть следующим образом:

Карта Карно является представлением такой двумерной развертки в виде таблицы.

В этой карте самые левые ячейки смежны самым правым.

Ясно, что на одной \(K\)-мерной грани могут лежать \(2^K\) вершин. Следовательно, в карте Карно выбираются группы по \(2^K\) смежных ячеек, и в результирующую ДНФ или КНФ входят только те переменные, которые неизменны в рамках данной группы. Общее число членов соответствует числу групп в карте Карно, а число неизменных переменных обратным образом зависит от количества элементов в группе. Как следствие, группы необходимо выбирать как можно более большими. Следует отметить, что одна комбинация переменных может входить в несколько групп.

Для функций четырех переменных, требуется развертка 4-мерного гиперкуба. Карта Карно в таком случае имеет вид:

В данном случае, все крайние ячейки смежны друг другу. Это можно себе представить, натянув эту развертку на тор (“бублик”):

Возможно так же построение карт Карно для функций 5 и 6 переменных, однако работа с ними значительно затрудена. Для числа переменных, большего 6, использование карт Карно попросту непрактично.

Пример

Рассмотрим функцию, имеющую следующую таблицу истинности:

Перепишем эту таблицу в виде карты Карно:

Легко выделяются три группы. Исходя из этого, записывается ДНФ:

\(\;\overline{x_1}\;\;\overline{x_2}\;\;\overline{x_3}\;\)\(\vee\)\(\;\overline{x_1}\;\;\overline{x_4}\;\)\(\vee\)\({x_2}{x_3}\)

Метод Куайна-МакКласки

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

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

Склейка

Сначала элементарные члены совершенной формы записываются в двоичной форме в таблицу, где группируются по количеству единиц.

Затем, члены, которые отличаются одной переменной (одним битом), могут быть склеены. В таком случае единица заменяется на “-”. Очевидно, что склеены могут быть только члены из соседних групп

Члены, которые нельзя склеить, обозначаются звездочкой "*".

Полученные склеенные члены могут, в свою очередь, так же быть склеены. При этом “-” трактуется как “третье” значение.

Когда никакие члены больше не могут быть склеены, из членов, отмеченных “*”, составляется сокращенная форма, которая не обязательно минимальна. После этого производится редукция.

Редукция

Для редукции, составляется таблица, в строки которой включаются члены сокращенной формы, а в столбцы – члены совершенной.

В ячейках ставится отметка (например, крестик “×”), если соответствующий член сокращенной формы поглощает соответствующий член совершенной формы (т.е. если заголовок строки является частью заголовка столбца).

Выбираются столбцы, содержащие только один “×”. Соответсвтующие им члены сокращенной формы составляют ядро, и должны войти в минимальную форму.

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

Пример

Найдем минимальную форму функции

Члены СДНФ в двоичной нотации:

• 0000 = 0
• 0001 = 1
• 0010 = 2
• 0011 = 3
• 0101 = 5
• 0111 = 7
• 1000 = 8
• 1010 = 10
• 1100 = 12
• 1101 = 13
• 1111 = 15

Группировка:

0

• 0000 = 0

1

• 0001 = 1
• 0010 = 2
• 1000 = 8

2

• 0011 = 3
• 0101 = 5
• 1010 = 10
• 1100 = 12

3

• 0111 = 7
• 1101 = 13

4

• 1111 = 15

Склейка 1:

• 0, 1 = 000-
• 0, 2 = 00-0
• 0, 8 = -000
• 1, 3 = 00-1
• 1, 5 = 0-01
• 2, 3 = 001-
• 2,10 = -010
• 8,10 = 10-0
• 8,12 = 1-00
• 3,7 = 0-11
• 5,7 = 01-1
• 5,13 = -101
• 12,13 = 110-
• 7,15 = -111
• 13,15 = 11-1

Группировка 2:

• 0, 1 = 000-
• 2, 3 = 001-
• *12,13 = 110-

• 0, 2 = 00-0
• 1, 3 = 00-1
• 8,10 = 10-0
• 5,7 = 01-1
• 13,15 = 11-1

• 1, 5 = 0-01
• *8,12 = 1-00
• 3,7 = 0-11

• 0, 8 = -000
• 2,10 = -010
• 5,13 = -101
• 7,15 = -111

Склейка 2:

• *0,1,2,3 = 00–
• *0,2,8,10 = -0-0
• *5,7,13,15 = -1-1
• *1,3,5,7 = 0–1

Итого, члены сокращенной формы:

• 12,13 = 110-
• 8,12 = 1-00
• 0,1,2,3 = 00–
• 0,2,8,10 = -0-0
• 5,7,13,15 = -1-1
• 1,3,5,7 = 0–1

Редукция:

Кружком обведены члены ядра.

Ядро, таким образом, включает члены -0-0 и -1-1. Для получения минимальной формы, нам нужно перекрыть дополнительно столбцы 1, 3, 12. Для этого можно взять, например, 0,1,2,3 = 00– и 12,13 = 110-:

\[ f = \;\overline{x_2}\;\;\overline{x_4}\; \vee {x_2}{x_4} \vee \;\overline{x_1}\;\;\overline{x_2}\; \vee {x_1}{x_2}\;\overline{x_3}\; \]

Карта Карно: