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

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

" При проэктировании  цифровых автоматов широко используются  методы минимизации булевых функций,  позволяющие получать рекомендации  для построения экономичных схем  цифровых автоматов. Общая задача  минммизации булевых функций  может быть сформулирована следующим образом: найти аналитическое выражение заданой булевой функции в форме, содержащей минимально возможное число букв. Следует отметить, что в общей постановке данная задача пока не решена, однако достаточно хорошо исследована в классе дизъюнктивно - конъюнктивных форм.

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

 

Определение. 
Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция элементарных конъюкций.

 

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

 

Определение. 
Булева функция g(x₁,...,x_n) называется импликантой булевой функции f(x₁,...,x_n), если для любого набора переменных, на котором g=1, справедливо f=1.

 

Таблица 4.1
x3x2x1	f	g1	g2	g3	g4	g5	g6	g7
000  001  010  011  100  101  110  111	0  0  0  1  0  0  1  1	0  0  0  0  0  0  0  1	0  0  0  0  0  0  1  0	0  0  0  0  0  0  1  1	0  0  0  1  0  0  0  0	0  0  0  1  0  0  0  1	0  0  0  1  0  0  1  0	0  0  0  1  0  0  1  1

 
f = /x₁x₂x₃ v x₁x₂/x₃ v x₁x₂x₃ = g₇; 
g₁ = x₁x₂x₃; 
g₂ = x₁x₂/x₃; 
g₃ = x₁x₂x₃ v x₁x₂/x₃ = x₁x₂ (x₃ v x₃) = x₁x₂; 
g₄ = /x₁x₂x₃; 
g₅ = /x₁x₂x₃ v x₁x₂x₃ = x₂x₃; 
g₆ = /x₁x₂x₃ v x₁x₂/x₃;

Определение. 
Импликанта g булевой функции f, являющаяся элементарной конъюнкцией, называется простой, если никакая часть импликанты g не является импликантой функции f.

 
Из примера видно, что импликанты g₃ = x₁x₂ и g₅ = x₂x₃ являются простыми импликантами функции f. Импликанты g₁, g₂, g₄, g₆ не являются простыми, так как их части являются импликантами функции f, например g₃ является частью g₁. Приведем без доказательства два утверждения, полезные при получении минимальной ДНФ.

1. Дизъюнкция любого числа импликант булевой функции f также является импликантой этой функции.
2. Любая булева функция f эквивалентна дизъюнкции всех своих простых импликант. Такая форма представления булевой функции называется сокращенной ДНФ.

Перебор всех возможных  импликант для булевой функции f из рассмотренного примера дает возможность убедиться, что простых импликант всего две: g₃ и g₅. Следовательно, сокращенная ДНФ функции f имеет вид

f = g₃ v g₅ = x₁x₂ v x₂x₃.

 
Как видно из табл. 4.1, импликанты g₃, g₅ в совокупности покрывают своими единицами все единицы функции f. Получение сокращенных ДНФ является первым этапом отыскания минимальных форм булевых функций. Как уже отмечалось, в сокращенную ДНФ входят все простые импликанты булевой функции. Иногда из сокращенной ДНФ можно убрать одну или несколько простых импликант, не нарушая эквивалентности исходной функции. Такие простые импликанты назовем лишними. Исключение лишних простых импликант из сокращенных ДНФ - второй этап минимизации.

Определение. 
Сокращенная ДНФ булевой функции называется тупиковой, если в ней отсутствуют лишние простые импликанты.

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

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

 
Рассмотрим несколько методов  минимизации. Все они практически  различаются лишь на первом этапе - этапе получения сокращенной  ДНФ. Следует отметить, что, к сожалению, поиск минимальной ДНФ всегда связан с некоторым перебором решений. Существуют методы уменьшения этого перебора, однако он всегда остается."

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

"Метод Квайна  основывается на применении двух  основных соотношений.

1. Соотношение склеивания

Ах V А/х = Ах V А/х V А,

где А - любое  элементарное произведение.

2. Соотношение поглощения

А~х V А = А,   ~х E {х; /x}.

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

A = A (x v /x) = Ax v A/x

по всем недостающим  переменным x_i^(k+l), ..., X_i^n исходной функции f, получаем совокупность S конституент единицы. При склеивании всех конституент из S получим импликанту р. Последнее очевидно, поскольку операция склеивания обратна операции развертывания. Множество S конституент обязательно присутствует в совершенной ДНФ функции f поскольку р - ее импликанта.

Таблица 4.1.1
x4x3x2x1	f
0000  0001  0010  0011  0100  0101  0110  0111  1000  1001  1010  1011  1100  1101  1110  1111	0  1  0  1  0  1  0  1  0  0  0  0  0  0  1  1

 
Пример. Пусть имеется булева функция, заданная таблицей истинности (табл. 9.1.1). Ее СДНФ имеет вид

f = /x₁/x₂/x₃x₄ v /x₁/x₂x₃x₄ v /x₁x₂/x₃x₄ v /x₁x₂x₃x₄ v x₁x₂x₃/x₄ v x₁x₂x₃x₄.

 
Для удобства изложения пометим  каждую конституенту единицы из СДНФ функции f каким-либо десятичным номером (произвольно). Выполняем склеивания. Конституента 1 склеивается только с конституентой 2 (по переменной x₃) и с конституентой 3 (по переменной х₂), конституента 2 с конституентой 4 и т. д. В результате получаем

1 - 2: /x₁/x₂x₄; 
1 - 3: /x₁/x₃x₄; 
2 - 4: /x₁x₃x₄; 
3 - 4: /x₁x₂x₄; 
4 - 6: x₂x₃x₄; 
5 - 6: x₁x₂x₃.

 
Заметим, что результатом склеивания является всегда элементарное произведение, представляющее собой общую часть  склеиваемых конституент Далее  производим склеивания получаемых элементарных произведений. 
Склеиваются только те произведения, которые содержат одинаковые переменные. Имеет место два случая склеивания:

/x₁/x₂x₄ v /x₁x₂x₄ = /x₁/x₂x₄ v /x₁x₂x₄ v /x₁x₄; 
/x₁/x₃x₄ v /x₁x₃x₄ = /x₁/x₃x₄ v /x₁x₃x₄ v /x₁x₄,

 
с появлением одного и того же элементарного  произведения /x₁x₄. Дальнейшие склеивания невозможны. Произведя поглощения (из полученной ДНФ вычеркиваем все поглощаемые элементарные произведения), получим сокращенную ДНФ:

x₂x₃x₄ v x₁x₂x₃ v /x₁x₄.

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

Таблица 4.1.2
Простые  импликанты	Конституенты  единицы
	/x1/x2/x3x4	/x1/x2x3x4	/x1x2/x3x4	/x1x2x3x4	x1x2x3/x4	x1x2x3x4
/x1x4	X	X	X	X
x2x3x4				X		X
x1x2x3					Х	Х

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

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

Пример (продолжение). Ядром нашей функции являются импликанты x₁x₂x₃; /x₁x₄. Импликанта x₂x₃x₄ - лишняя, так как ядро накрывает все столбцы импликантной матрицы. Поэтому функция имеет единственную тупиковую и минимальную ДНФ:

f = x₁x₂x₃ v /x₁x₄

 
Следует отметить, что число N крестиков  в одной строке всегда является степенью 2. Более того, читатель может легко  убедиться в том, что

N = 2^n-k

 
где k - число букв, содержащихся в  простой импликанте. 
Заметим также, что используя различные соотношения, можно расширить область применения метода Квайна за пределы совершенной ДНФ."

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

"Метод представляет  собой формализованный на этапе  нахождения простых импликант  метод Квайна. Формализация производится следующим образом:

1. Все конституанты единицы из СДНФ булевой функции f записываются их двоичными номерами.
2. Все номера разбиваются на непересекающиеся группы. Признак образования i-й группы: i единиц в каждом двоичном номере конституенты единицы.
3. Склеивание производят только между номерами соседних групп. Склеиваемые номера отмечаются каким-либо знаком (зачеркиванием).
4. Склеивания производят всевозможные, как и в методе Квайна. Неотмеченные после склеивания номера являются простыми импликантами.

Метод Блейка - Порецкого.

" Метод позволяет  получать сокращенную ДНФ булевой  функции f из ее произвольной  ДНФ. Базируется на применении  формулы обобщенного склеивания:

Ax v B/x = Ax v B/x v AB,

справедливость  которой легко доказать. Действительно,

Ax = Ax v ABx;     B/x = B/x v AB/x.

Следовательно,

Ах v В/х = Ах v АВх v В/х v АВ/х = Ах V В/х V АВ.

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

Метод диаграмм Вейча.

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

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