Среди тупиковых форм находится и минимальная дизъюнктивная форма, причем она может быть неединственной. Чтобы убедиться в том, что данная тупиковая форма является минимальной, необходимо найти все тупиковые формы и сравнить их по числу входящих в них букв.
Пусть, например, функция задана в совершенной нормальной дизъюнктивной форме: y = x̅1x2x̅3 ∨ x̅1x2x3 ∨ x1x̅2x̅3 ∨ x1x̅2x3 ∨ x1x2x3. Группируя члены и применяя операцию склеивания, имеем y = (x̅1x2x̅3 ∨ x̅1x2x3) ∨ (x1x̅2x̅3 ∨ x1x̅2x3) ∨ x1x2x3. При другом способе группировки y = x̅1x2x̅3 ∨ (x̅1x2x3 ∨ x1x̅2x̅3) ∨ (x1x̅2x3 ∨ x1x2x3). Обе тупиковые формы не являются минимальными. Чтобы получить минимальную форму, нужно догадаться повторить в исходной формуле один член (это всегда можно сделать, так как x ∨ x = x). В первом случае таким членом может быть x̅1x2x3. Тогда y = x̅1x2 ∨ x1x̅2 ∨ (x1x2x3 ∨ x̅1x2x3) = x̅1x2 ∨ x1x̅2 ∨ x2x3. Добавив член x1x̅2x3, получим: y = x̅1x2 ∨ x1x̅2 ∨ (x1x2x3 ∨ x1x̅2x3) = x̅1x2 ∨ x1x̅2 ∨ x2x3. Перебрав все возможные варианты, можно убедиться, что две последние формы являются минимальными.
Работа с формулами на таком уровне подобна блужданию в потемках. Процесс поиска минимальных форм становится более наглядным и целеустремленным, если использовать некоторые графические и аналитические представления и специально разработанную для этой цели символику.
6. Многомерный куб. Каждой вершине n-мерного куба (1. 9), можно поставить в соответствие конституенту единицы (2, 5). Следовательно, подмножество отмеченных вершин является отображением на n-мерном кубе булевой функции от n переменных в совершенной дизъюнктивной нормальной форме. На рис. 21 показано такое отображение для функции из (5).
Для отображения функции от n переменных, представленной в любой дизъюнктивной нормальной форме, необходимо установить соответствие между ее минитермами (2. 2) и элементами n-мерного куба.
Минитерм (n - 1)-го ранга φn-1 можно рассматривать как результат склеивания двух минитермовn-го ранга (конституент единицы), т. е. φn-1 = φn-1x1 ∨ φn-1x̅1.На n-мерном кубе это соответствует замене двух вершин, которые отличаются только значениями координаты xi, соединяющим эти вершины ребром (говорят, что ребро покрывает инцидентные ему вершины). Таким образом,
- 540 -
минитермам (n - 1)-го порядка соответствуют ребра n-мерного куба. Аналогично устанавливается соответствие минитермов (n - 2)-го порядка граням n-мерного куба, каждая из которых покрывает четыре вершины (и четыре ребра).
Рис. 212. Отображение на терхмерном кубе функции, представленной в совершенной дизъюктивной нормальной форме. |
Рис. 213. Покрытие функции y = x̅1x2 ∨ x1x̅2 ∨ x3 совокупностью s-кубов. |
Элементы n-мерного куба, характеризующиеся s измерениями, называют s-кубами. Так, вершины являются 0-кубами, ребра - 1-кубами, грани - 2-кубами и т. д. Обобщая приведенные рассуждения, можно считать, что Минитерм (n - s)-го ранга в дизъюнктивной нормальной форме для функции n переменных отображается s-кубом, причем каждый s-куб покрывает все те s-кубы низшей размерности, которые связаны только с его вершинами. В качестве
примера на рис. 22 дано отображение функции трех переменных y = x̅1x2 ∨ x1x̅2 ∨ x3. Здесь минитермы x̅1x2 и x1x̅2 соответствуют 1-кубам (s = 3 – 2 = 1), а минитерм x3 отображается 2-кубом (s = 3 - 1 = 2).
Итак, любая дизъюнктивная нормальная форма отображается на n-мерном кубе совокупностью s-кубов, которые покрывают все вершины, соответствующие конституентам единицы (0-кубы). Справедливо и обратное утверждение: если некоторая совокупность s-кубов покрывает множество всех вершин, соответствующих единичным значениям функции, то дизъюнкция соответствующих этим s-кубам минитермов является выражением данной функции в дизъюнктивной нормальной форме. Говорят, что такая совокупность s-кубов (или соответствующих им минитермов) образует покрытие функции.