Геометрический метод минимизации булевой функции

Рассмотрим элементарную конъюнкцию ранга r (т.е. содержащую r пропозициональных переменных).

K(X ,...,X_r)=X ... Х ,

где =0,1 ; Х = , . Очевидно, что множество N , соответствующее конъюнкции К, есть (3-r)- мерная грань. Число r называется рангом этой грани.

Пример.Конъюнкциям

K ( )=

К ( )=

К ( )= ,

соответствуют грани, имеющие ранги 2, 2, и 1. Первые две грани являются одномерной гранью (ребром), а третья - двумерной гранью.

Отметим очевидные свойства введенного соответствия между булевой функцией f и подмножеством .

Если f( ) = g( ) Ú h( ), то

1) , ;

2)N_f = N_g N_h.

В частности, если f( ) обладает ДНФ, т. е.

f( )= , то и , т.е. ДНФ функции f соответствует покрытие множества N гранями N_k , ., N_ks

Пусть r, - ранг грани N_ki (он равен рангу конъюнкции k ) Число r, определенное формулой

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

Приведем также определения сокращенной и тупиковой ДНФ сгеометрической точки зрения.

Грань , содержащаяс в , называется максимальной относительно , если не существует грани , такой, что

1) ;

2) размерность грани больше размерности грани N_{k .}

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

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

Покрытие множества , состоящее из максимальных относительно

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

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

Теорема 5.7.1.Понятия тупиковой ДНФ и тупиковой ДНФ в геометрическом смысле эквивалентны.

Алгоритм минимизации функций, зависящих от трех переменных, состоит в следующих четырех шагах:

1. Нанести множество N , на трехмерный куб. Использовать или табличное задание функции, отметив вершины, в которых f( ) = 1, или СДНФ функции и тогда каждому слагаемому СДНФ поставить в соответствие вершину.

2.Если отмеченными окажутся все вершины куба, то данная функция тождественно истинна.

3 . Если отмечены все вершины какой-либо грани, то для построения минимальной формы заменить все четыре вершины одной переменной - названием грани.

4 . Если отменены вершины какого-либо ребра то в минимизированной форме им соответствует конъюнкция - название ребра.

Чтобы получить минимизированную форму, надо выбирать ребра, покрывающие вершины так, чтобы меньшим числом ребер покрыть все отмеченные вершины.

5. Если существует вершина, которая не образует ребро ни с какой другой вершиной, то в минимизированной форме ей соответствует конъюнкция - название вершины.

Пример. Минимизировать булеву функцию f(0,1,1)=f(1,0,0)=f(1,0,1)=0 геометрическим методом.

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

f(0,0,0)=f(0,0,1)=f(0,1,0)=f(1,1,0)= f(1,1,1)=1.

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

; ; ;

.

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

Замечание. При n=3 геометрический метод минимизации булевых функций аналогичен минимизации с помощью прямоугольной таблицы, называемой минимизирующей картой (картой Карно) [4].