Геометрическая интерпретация. Минимизация Б Ф

Число различных ДНФ, составленных из переменных , равно .

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

Рангом элементарной конъюнкции назыв число переменных входящих в нее.

Рассмотрим геометрическую интерпретацию задачи минимизации булевых функций.

Обозначим через множество всех вершин единичного n-мерного куба.

Свойства:

1) булевой функции соответствует подмножество ;

2) булевой функции соответствует подмножество ;

3) булевой функции соответствует подмножество .

Пусть Б Ф задана ДНФ К1 \/ К2\/ … \/Кi Кi – элементарные кон-ии.

Множество Ni называется интервалами этого ранга если оно соответствует некоторой элементарной конъюнкции этого ранга, тогда Nf есть объединения всех интервалов которые соответствуют конъюнкциям входящим в ДНФ.

Множество всех таких интервалов называется покрытием функции, т е для функции f = K1\/K2\/…\/Ki покрытие будет состоять из интервалов N1, N2,…,Ni. Таким образом если каждый интервал имеет свой ранг, то задача минимизации бул ф в интерпретации сводится к построению покрытия интервалами сумм рангов которых наименьшая.

Интервалами Nk назыв макс если он не содержится ни в каком др интервале. Таким образом выбрав все макс интервалы из множества Nf и объединив их получим покрытие которое будет соответствовать сокр ДНФ

Теорема 1 Если в произвольной ДНФ булевой функции f произвести все возможные обобщения склеивания и устранить затем все элементарные поглощения, то в результате получится сокращенная ДНФ функции f.

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

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

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

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

Теорема 5 Всякая минимальная ДНФ является тупиковой.

1 Выделяются все максимальные интервалы, и строится сокращенная ДНФ.

2 Строятся все тупиковые ДНФ.

3 Среди всех тупиковых ДНФ выделяются все минимальные ДНФ.

 

Метод Блейка

Метод Блейка для построения сокращенной ДНФ из произвольной ДНФ состоит в применении правил обобщенного склеивания и поглощения. Подразумевается, что правила применяются слева направо. На первом этапе производится операция обобщенного склеивания до тех пор, пока это возможно. На втором производится операция поглощения.

1. Метод Блейка состоит в применении двух правил:

а) обобщенное склеивание – первое правило. С помощью формулы производим операцию обобщенного склеивания в Д.Н.Ф. пока это возможно. Для этого в Д.Н.Ф. отыскиваем подформулы вида и добавляем к ним . На этом этапе формула усложняется.

б) поглощение – второе правило. Оно основано на равенстве

.

Находим в Д.Н.Ф. конъюнкции с минимальным числом сомножителей и все конъюнкции, их содержащие, вычеркиваем.

Пример: .

Разумно в Д.Н.Ф. сначала применить метод группировки (как более простой), а затем метод Блейка.

Построение минимального ДНФ

ДНФ назыв минимальной, если она включает минимальное число символов по сравнению со всеми другими эквивалентами ей ДНФ

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

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

В сокращенной ДНФ

элементарная конъюнкция поглощается дизъюнкцией остальных элементарных конъюнкций, т.е. .

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

Теорема 5 Всякая минимальная ДНФ является тупиковой.

1 Выделяются все максимальные интервалы, и строится сокращенная ДНФ.

2 Строятся все тупиковые ДНФ.

3 Среди всех тупиковых ДНФ выделяются все минимальные ДНФ.

Дальнейший алгоритм удобно реализовать методом импликантных матриц.

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

Для каждой находим набор такой, что .

Клетку импликантной матрицы, образованную пересечением i -строки и j -столбца отметим крестиком.

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