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

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

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

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

,

,

соответствуют грани (рис. 7 а, б, в) , N_k1={7,8}, N_k2={8,6}, N_k3={6,2,4,8}, имеющие ранги 2, 2, и 1. Первые две грани являются одномерной гранью (ребром), а третья - двумерной гранью.

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

Если , то

.

В частности, если f(X₁, Χ₂, X₃) обладает ДНФ, т. е. , то  и  т.е. ДНФ функции f соответствует покрытие множества Ν, гранями .

Пример 12. Рассмотрим представленную в СДНФ функцию

.

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

    .

Этим ДНФ соответствуют два покрытия множества N_f :

,

,

где N_k1={2}, N_k2={6}, N_k3={3}, N_k4={8}, N_k5={4}, N_k10={2,6,8,4}, N_k20={4,3}. Одно из этих покрытий - точечное, второе состоит из ребра и двумерной грани.

Пусть r_i - ранг гpани Ν_ki (он равен рангу конъюнкции k_i). Число r, определенное формулой

,

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

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

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

1)

2) размерность грани  больше размерности грани N_k.

Пример 13. Пусть f(X₁, Х₂, X₃) – функция, заданная табл. 4 и  Тогда грани Ν_k1 и N_k3 являются максимальными, a N_k2 не максимальна для N_f, т. к. и размерность N_k3 больше размерности N_k2.

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

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

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

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

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

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

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

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

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

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

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

Пример 14. Минимизировать функцию f(X₁, X₂, Х₃), заданную табл. 4.

Решение. Множество N_f для указанной функции изображено на рис. 3. Так как вершины 2, 4, 6, 8 принадлежат одной грани Χ₁, вершины 7 и 8 принадлежат ребру , то минимизированная форма функции f имеет вид

.

Пример 15. Минимизировать записанную в СДНФ функцию

.

Решение. Отметим на модели куба элементарные конъюнкции: первой конъюнкции соответствует вершина 6, второй – вершина 5, третьей – вершина 8, четвертой – вершина 2 (рис 8). Таким образом, множество N_f –построено. Ни одна грань не отмечена полностью, поэтому переходим к шагу 4 алгоритма.

Рис. 8

Вершины 5 и 6 принадлежат одному ребру , вершины 6 и 8 – ребру , следовательно, минимизированная форма имеет вид:

.

Пример 16. Минимизировать функцию f(X₁,X₂,X₃), заданную табл. 5.

Таблица 5

Решение. Построим модель куба, соответствующего этой функции (рис.9).

Рис. 9

Грани (1, 2, 3, 4) соответствует X₂, грани (2, 4, 6, 8) – Х₁, следовательно, минимизированная форма имеет вид

.

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