Полные системы булевых функций (стр. 4 из 6)
Напомним [1], что для любой булевой функции существует ее представление в СДНФ. Причём в алгоритме построения СДНФ используется только те наборы значений, при которых функция равна единице [3]. Это позволяет проинтерпретировать геометрическое представление функции следующим образом. Рассмотрим трёхмерный куб и занумеруем вершины так, как показано на рис. 4.
 |  |
 |  |
 |  |
Ребрами данного куба ( одномерными подкубами) будут, например,
, и т.д.Пример 9. Построить модель куба, соответствующего функции:
.Решение. Первому слагаемому соответствует вершина 2, второму – вершина 6, третьему – вершина 3, четвертому – вершина 8, пятому – вершина 4 (рис. 5).
Пример 10. Дана модель куба с помеченными вершинами (рис. 6). Составить СДНФ для данной булевой функции
Решение. Вершине 1 соответствует конъюнкция
, вершинам 3 и 4 конъюнкция 
и 
соответственно; вершинам 5 и 6 - конъюнкции 
и 
. Следовательно, искомая СДНФ имеет вид
.Заметим, что для функций, зависящих от четырёх и более переменных, геометрическое представление применяется очень редко, т.к. трудно построить наглядную модель n-мерного куба при n > 3. Поэтому в этом и следующих параграфах мы будем рассматривать только булевы функции трех аргументов, хотя все изложенное справедливо для других функций, зависящих от большого числа аргументов.
Перейдем теперь к геометрической постановке задачи минимизации булевых функций.
5. Геометрический метод минимизации булевой функции
Рассмотрим элементарную конъюнкцию ранга r (т.е. содержащую r пропозициональных переменных)
где ε = 0,1;
. Очевидно, что множество Nk, соответствующее конъюнкции К, есть (3 – r)-мерная грань. Число r называется рангом этой грани.Пример 11. Конъюнкциям
, 
, 
соответствуют грани (рис. 7 а, б, в) , Nk1={7,8}, Nk2={8,6}, Nk3={6,2,4,8}, имеющие ранги 2, 2, и 1. Первые две грани являются одномерной гранью (ребром), а третья - двумерной гранью.
Отметим очевидные свойства введенного соответствия между булевой функцией f и подмножеством Nf.
Если
, то 
.В частности, если f(X1, Χ2, X3) обладает ДНФ, т. е.
, то 
и 
т.е. ДНФ функции f соответствует покрытие множества Ν, гранями 
.Пример 12. Рассмотрим представленную в СДНФ функцию
.модель куба, для которой построена на рис. 3. С помощью таблицы истинности может быть показано, что данная функция представима также ДНФ
.Этим ДНФ соответствуют два покрытия множества Nf :
, 
,где Nk1={2}, Nk2={6}, Nk3={3}, Nk4={8}, Nk5={4}, Nk10={2,6,8,4}, Nk20={4,3}. Одно из этих покрытий - точечное, второе состоит из ребра и двумерной грани.
Пусть ri - ранг гpани Νki (он равен рангу конъюнкции ki). Число r, определенное формулой
,называется рангом покрытия. Тoгда задача о минимизации булевой функции принимает следующую геометрическую постановку: для данного множества Nf, найти такое покрытие гранями, принадлежащими Nf,
, чтобы его ранг был наименьшим.Приведем также определения сокращенной и тупиковой ДНФ c геометрической точки зрения.
Грань Nk, содержащаяся в Nf, называется максимальной относительно Nf, если не существует грани
, такой, что1)
2) размерность грани
больше размерности грани Nk.Пример 13. Пусть f(X1, Х2, X3) – функция, заданная табл. 4 и
Тогда грани Νk1 и Nk3 являются максимальными, a Nk2 не максимальна для Nf, т. к. 
и размерность Nk3 больше размерности Nk2.Конъюнкция К, соответствующая максимальной грани Nk, называется простой импликантой функции f.
ДНФ, являющаяся дизъюнкцией всех простых импликант функции f, называется сокращенной ДНФ.
Покрытие множества Nf, состоящее из максимальных относительно Nf граней, называется неприводимым, если совокупность граней, получающаяся из исходной путем выбрасывания любой грани, не будет покрытием Nf.
ДНФ, соответствующая неприводимому покрытию множества Nf называется тупиковой в геометрическом смысле.
Теорема. Понятия тупиковой ДНФ и тупиковой ДНФ в геометрическом смысле эквивалентны.
Алгоритм минимизации функций, зависящих от трех переменных, состоит в следующих четырех шагах:
1. Нанести множество Nf, на трехмерный куб. Использовать или табличное задание функции, отметив вершины, в которых f(X1, Χ2, Χ3) = 1, или СДНФ функции и тогда каждому слагаемому СДНФ поставить в соответствие вершину (см. раздел 5).
2. Если отмеченными окажутся все вершины куба, то данная функция тождественно истинна
3. Если отмечены все вершины какой-либо грани, то для построения минимальной формы заменить все четыре вершины одной переменной – названием грани.
4. Если отмечены вершины какого-либо ребра, то в минимизированной форме им соответствует конъюнкция – название ребра.
Чтобы получить минимизированную форму, надо выбирать ребра, покрывающие вершины, так, чтобы меньшим числом ребер покрыть все отмеченные вершины.
Пример 14. Минимизировать функцию f(X1, X2, Х3), заданную табл. 4.
Решение. Множество Nf для указанной функции изображено на рис. 3. Так как вершины 2, 4, 6, 8 принадлежат одной грани Χ1, вершины 7 и 8 принадлежат ребру
, то минимизированная форма функции f имеет вид 
.Пример 15. Минимизировать записанную в СДНФ функцию