Многомерный куб

Рассмотрим графическое представление функции в виде многомерного куба. Каждой вершине 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), а минитерм х₃ отображается 2-кубам (S=3-1=2).

Итак, любая ДНФ отображается на n-мерном кубе совокупностью S-кубов, которые покрывают все вершины, соответствующие конституентам единицам (0-куба).

Конституенты. Для переменных х₁, х₂,… х_n выражение называют конституентой единицы, а — конституентой нуля ( означает либо , либо ).

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

Например: конституенте единице соответствует набор (1011), а конституенте нуля — набор (1001).

Так как СД(К)НФ является дизъюнкцией (конъюнкцией) конституент единицы (нуля), то можно утверждать, что представляемая ею булева функция f(x₁,x₂,…,x_n) обращается в единицу (нуль) только при наборах значений переменных x₁,x₂,…,x_n, соответствующих этим копституантам. На остальных наборах эта функция обращается в 0 (единицу).

Справедливо и обратное утверждение, на котором основан способ представления в виде формулы любой булевой функции, заданной таблицей.

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

Например, функции, заданной таблицей

соответствуют

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

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

Говорят, что такая совокупность S-кубов (или соответствующих им минитермов) образует покрытие функции. Стремление к минимальной форме интуитивно понимается как поиск такого покрытия, число S-кубов которого было бы поменьше, а их размерность S — побольше. Покрытие, соответствующее минимальной форме, называют минимальным покрытием.

Например, для функции у= покрытие соответствует неминимальной форме:

рис a) у= ,

а покрытия на рис б) у= , рис в) у= минимальные.

 

 

 

Рис. Покрытие функции у= :

а) неминимальное; б), в) минимальное.

 

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

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