Математический аппарат инженера

Каноническая задача синтеза логических схем в булевом базисе сводится к минимизации булевых функций, т.е. к представлению их в дизъюнктивной нормальной форме, которая содержит наименьшее число букв (переменных и их отрицаний). Такие формы называют минимальными. При каноническом синтезе предполагается, что на входы схемы подаются как сигналы х_i, так и их инверсии x̅_i. Формула, представленная в дизъюнктивной нормальной форме, упрощается многократным применением операции склеивания ab ∨ ab̅ = a и операций поглощения a ∨ ab = a; и a ∨ ab̅ = a ∨ b (дуальные тождества для конъюнктивной нормальной формы имеют

- 539 -

вид: (a ∨ b)(a ∨ b̅) = a; a(a ∨ b)= a; a(a̅ ∨ b) = ab ). Здесь под a и b можно понимать любую формулу булевой алгебры. В результате приходим к такому аналитическому выражению, когда дальнейшие преобразования оказываются уже невозможными, т. е. получаем тупиковую форму.

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

Пусть, например, функция задана в совершенной нормальной дизъюнктивной форме: y = x̅₁x₂x̅₃ ∨ x̅₁x₂x₃ ∨ x₁x̅₂x̅₃ ∨ x₁x̅₂x₃ ∨ x₁x₂x₃. Группируя члены и применяя операцию склеивания, имеем y = (x̅₁x₂x̅

₃ ∨ x̅₁x₂x₃) ∨ (x₁x̅₂x̅₃ ∨ x₁x̅₂x₃) ∨ x₁x₂x₃. При другом способе группировки y = x̅₁x₂x̅₃ ∨ (x̅₁x₂x₃ ∨ x₁x̅₂x̅₃) ∨ (x₁x̅₂x₃ ∨ x₁x₂x₃). Обе тупиковые формы не являются минимальными. Чтобы получить минимальную форму, нужно догадаться повторить в исходной формуле один член (это всегда можно сделать, так как x ∨ x = x). В первом случае таким членом может быть x̅₁x₂x₃

. Тогда y = x̅₁x₂ ∨ x₁x̅₂ ∨ (x₁x₂x₃ ∨ x̅₁x₂x₃) = x̅₁x₂ ∨ x₁x̅₂ ∨ x₂x₃. Добавив член x₁x̅₂x₃, получим: y = x̅₁x₂ ∨ x₁x̅₂ ∨ (x₁x₂x₃ ∨ x₁x̅₂x₃) = x̅₁x

₂ ∨ x₁x̅₂ ∨ x₂x₃. Перебрав все возможные варианты, можно убедиться, что две последние формы являются минимальными.

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

6. Многомерный куб. Каждой вершине n-мерного куба (1. 9), можно поставить в соответствие конституенту единицы (2, 5). Следовательно, подмножество отмеченных вершин является отображением на n-мерном кубе булевой функции от n переменных в совершенной дизъюнктивной нормальной форме. На рис. 21 показано такое отображение для функции из (5).

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

Минитерм (n - 1)-го ранга φ_n-1 можно рассматривать как результат склеивания двух минитермовn-го ранга (конституент единицы), т. е. φ_n-1 = φ_n-1x₁ ∨ φ_n-1x̅₁.На n-мерном кубе это соответствует замене двух вершин, которые отличаются только значениями координаты x_i, соединяющим эти вершины ребром (говорят, что ребро покрывает инцидентные ему вершины). Таким образом,

- 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̅₁x₂ ∨ x₁x̅₂ ∨ x₃. Здесь минитермы x̅₁x₂ и x₁x̅₂ соответствуют 1-кубам (s = 3 – 2 = 1), а минитерм x₃ отображается 2-кубом (s = 3 - 1 = 2).