Рассмотрим графическое представление функции в виде многомерного куба. Каждой вершине n -мерного куба можно поставить в соответствие конституенту единицы.
Подмножество отмеченных вершин является отображением на n -мерном кубе булевой функции от n переменных в СДНФ.
Для отображения функции от n переменных, представленной в любой ДНФ, необходимо установить соответствие между ее минитермами и элементами n -мерного куба.
Минитерм (n-1)-го ранга можно рассматривать как результат склеивания двух минитермов n -го ранга, т.е.
=
На n -мерном кубе это соответствует замене двух вершин, которые отличаются только значениями координат хi, соединяющих эти вершины ребром (говорят, что ребро покрывает инцидентные ему вершины).
Таким образом, минитермам (n -1)-го порядка соответствуют ребра n-мерного куба.
Аналогично устанавливается соответствие минитермов (n -2)-го порядка граням n -мерного куба, каждая из которых покрывает четыре вершины (и четыре ребра).
Элементы n -мерного куба, характеризующиеся S измерениями, называются S -кубами.
|
|
Так вершины являются 0-кубами, ребра 1-кубами, грани 2-кубами и т.д.
Обобщая, можно сказать, что минитерм (n-S) ранга в ДНФ для функции n переменных отображается S -кубом, причем каждый S -куб покрывает все те кубы низшей размерности, которые связаны только с его вершинами.
Пример. На рис. дано отображение
Здесь минитермы и соответствуют 1-кубам (S =3-2=1), а минитерм х3 отображается 2-кубам (S =3-1=2).
Итак, любая ДНФ отображается на n -мерном кубе совокупностью S -кубов, которые покрывают все вершины, соответствующие конституентам единицам (0-куба).
Конституенты. Для переменных х1, х2,… хn выражение называют конституентой единицы, а — конституентой нуля ( означает либо , либо ).
Данная конституента единицы (нуля) обращается в единицу (нуль) только при одном соответствующем ей наборе значений переменных, который получается, если все переменные принять равными единице (нулю), а их отрицания — нулю (единице).
Например: конституенте единице соответствует набор (1011), а конституенте нуля — набор (1001).
Так как СД(К)НФ является дизъюнкцией (конъюнкцией) конституент единицы (нуля), то можно утверждать, что представляемая ею булева функция f (x1,x2,…,xn) обращается в единицу (нуль) только при наборах значений переменных x1,x2,…,xn, соответствующих этим копституантам. На остальных наборах эта функция обращается в 0 (единицу).
Справедливо и обратное утверждение, на котором основан способ представления в виде формулы любой булевой функции, заданной таблицей.
Для этого необходимо записать дизъюнкции (конъюнкции) конституент единицы (нуля), соответствующих наборам значений переменных, на которых функция принимает значение, равное единице (нулю).
|
|
Например, функции, заданной таблицей
соответствуют
Полученные выражения можно преобразовать к другому виду на основании свойств алгебры логики.
Справедливо и обратное утверждение: если некоторая совокупность S -кубов покрывает множество всех вершин, соответствующих единичным значениям функции, то дизъюнкция соответствующих этим S -кубам минитермов является выражением данной функции в ДНФ.
Говорят, что такая совокупность S -кубов (или соответствующих им минитермов) образует покрытие функции. Стремление к минимальной форме интуитивно понимается как поиск такого покрытия, число S -кубов которого было бы поменьше, а их размерность S — побольше. Покрытие, соответствующее минимальной форме, называют минимальным покрытием.
Например, для функции у = покрытие соответствует неминимальной форме:
рис a) у = ,
а покрытия на рис б) у = , рис в) у = минимальные.
Рис. Покрытие функции у = :
а) неминимальное; б), в) минимальное.
Отображение функции на n -мерном наглядно и просто при n £3. Четырехмерный куб можно изобразить, как показано на рис., где отображены функции четырех переменных и ее минимальное покрытие, соответствующее выражению у =
Использование этого метода при n >4 требует настолько сложных построений, что теряет все его преимущества.