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

Булевой (или логической, двоичной) функцией называется функция, каждая переменная которой определена на множестве и принимающая значения из этого же множества.

-декартовое произведение

Булевой функцией от n переменных называется отображение .

Для любой булевой функции справедливо - совершенная ДНФ функции (дизъюнктивно нормальна форма).

Выражение вида , где называется элементарной конъюнкцией ранга S.

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

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

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

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

Рассмотрим - n-мерный бинарный куб.

Рассмотрим элементарную конъюнкцию ранга = S. Множество - множество, соответствующее элементарным конъюнкциям называется интервалом конъюнкции.

Утверждение: Размерность интервала -

Пусть . . - множество наборов, на которых функция превращается в 1.

Свойства :

1. ;
2. ;
3. .

Рассмотрим функцию . ->

Утверждение: .

Интервал называется допустимым для функции , а соответствующие этому интервалу конъюнкция называется импликантом.

Интервал называется максимальным для , если:

1. , - допустимый,
2. Никакой другой допустимый интервал не покрывает данный:

Конъюнкция, соответствующая максимальному интервалу функции , называется простой имликантой функции .

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

Утверждение: Минимизация ДНФ получается из путем возможного вычеркивания из последней некоторых простых импликант.

Методы построения :

1) Геометрический

1. Для функции строим множество и отмечаем его на кубе ;

2. Находим все максимальные интервалы, объединение всех интервалов и дает .

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

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

Применяем ее до тех пор, пока появляются новые элементарные конъюнкции. Затем применяется операция поглощения: .В итоге получим .

3) метод Нельсона

Строится для функции совершенную КНФ, затем операция поглощения, где возможно и получим

Покрытие множества максимальными интервалами называется неприводимым, если после удаления из него любого максимального интервала оно (покрытие) перестает покрывать (Покрытие множества - любое семейство подмножеств этого множества, объединение которого есть само это множество).

Тупиковой ДНФ функции называется ДНФ, соответствующая неприводимому покрытию множества .

Утверждение: Любая минимальная ДНФ является тупиковой.

Простая импликанта K называется ядровой для функции, если найдется такой набор из, что покрывается интервалом и для любой простой импликанты, не содержится в (). При этом называется ядровым интервалом.

Алгоритм нахождения минимальной ДНФ:

1) Находим сокращенную ДНФ, как все простые импликанты функции;

2) Определяем какие из простых импликант является ядровыми и из множества удаляем все вершины, покрываемые ядровыми импликантами;

3) Для оставшихся точек из множества строим все неприводимые покрытия;

4) Тупиковые ДНФ данной функции получаются с помощью объединения каждого неприводимого покрытия из пункта 3 со всеми ядровыми импликантами из пункта 2;

5) Из тупиковых ДНФ выбираем минимальные.

Пример. Пусть имеется булева функция . Ее СДНФ имеет вид

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

1 - 2: ; 1 - 3: ; 2 - 4: ; 3 - 4: ; 4 - 6: ; 5 - 6: .

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

Склеиваются только те произведения, которые содержат одинаковые переменные. Имеет место два случая склеивания:

; ,

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

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

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

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

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

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

Пример:

-ядровые импликанты, вычеркиваем точки, которые ими покрываются. Осталось 3 точки, выпишем их:

0100 1 1 0 0

1100 1 1 1 1

1101 0 0 1 1

покрываются.

Т.е. тупиковые ДНФ:

min =