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

т. е. , причем некоторые из K^s(у) могут быть пустыми. Для записи s-кубов и минитермов функции от n переменных используются слова длины n, буквы которых соответствуют всем n переменным. Входящие в минитерм переменные называются связанными и представляются значениями, при которых минитерм равен единице (1 для x_i и 0 для x̅_i). Не входящие в минитерм переменные являются свободными и обозначаются через х. Например, 2-куб функции пяти переменных, соответствующий минитерму x₂x̅₃x₅ , запишется как (x10x1). 0-кубы, соответствующие конституентам единицы, представляются наборами значений переменных, на которых функция равна единице.

Рис. 219. Комплекс кубов функци трех переменных (а) и его символическое представление (б).

Очевидно, в записи s-куба всегда имеется s свободных переменных. Если все n переменных свободны, что соответствует n-кубу, то это означает тождественность единице рассматриваемой функции. Таким образом, для функций, не равных тождественно единице, Kⁿ(y) = ∅.

Множество всех s-кубов К(у) записывается как совокупность слов, соответствующих каждому s-кубу. Для удобства будем располагать слова s-кубов в столбцы, а их совокупность заключать в фигурные скобки. Например, комплекс кубов, соответствующий представлению функции на трехмерном кубе (рис. 219, а), выражается как K(y) = K⁰∪K¹∪K², где

; ;

Для сравнения на рис. 219, б изображен комплекс кубов в принятых обозначениях.

Комплекс кубов образует максимальное покрытие функции. Исключая из него все те s-кубы, которые покрываются кубами высшей размерности, получаем покрытия, соответствующие тупиковым

- 545 -

формам. Так, для рассматриваемого примера имеем тупиковое покрытие

которое соответствует y = x̅₂x₃ ∨ x₂x̅₃ ∨ x̅₁. В данном случае это покрытие являетcя и минимальным.

Для двух булевых функций операция дизъюнкции соответствует объединению их комплексов кубов K(y₁ ∨ y₂) = K(y₁) ∪ K(y₂), а операция конъюнкции - пересечению комплексов кубов K(y₁y₂) = K(y₁) ∩ K(y₂).Отрицанию функции соответствует дополнение комплекса кубов, т. е. K(y̅) = K̅(y), причем K̅(y) определяется всеми вершинами, на которых функция принимает значение 0. Таким образом, имеет место взаимно-однозначное соответствие (изоморфизм) между алгеброй булевых функций и алгеброй множеств, представляющих комплексы кубов.

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

9. Реализация в различных формах. Реализация функции в дизъюнктивной нормальной форме представляет собой логическую схему И-ИЛИ. Например, функция y = x̅₁x₂ ∨ x₁x̅

₂ ∨ x₂x₃ реализуется логической схемой. Более экономичная реализация получается, если общий множитель вынести за скобки: y = x₂(x̅₁ ∨ x₃) ∨ x₁x̅₂. При использовании элементов со многими входами получаем двухуровневую логическую схему И—ИЛИ.

В соответствии с принципом двойственности (2.1), заменяя в дизъюнктивной нормальной форме операции конъюнкции на дизъюнкции, операции дизъюнкции на конъюнкции и беря отрицание

- 546 -

каждой переменной, получаем конъюнктивную нормальную форму, которая выражает функцию y̅, обратную к у. Ее реализация с помощью многовходовых элементов представляет собой двухуровневую логическую схему ИЛИ—И. Для рассматриваемой функции y̅ = (x₁ ∨ x̅₂)(x̅₁ ∨ x₂)(x̅₂ ∨ x̅₃

) соответствующая реализация показана на рис. 26, г. Если требуется получить схему для данной функции у, то используется инвертор или элемент, реализующей операцию НЕ—И.

Конъюнктивную нормальную форму можно получить и другим путем. Для этого используются рассуждения и методы, дуальные рассмотренным по отношению к дизъюнктивным нормальным формам. На многомерном кубе ищется покрытие множества вершин для нулевых значений функции, а на карте Карно - покрытие нулевых клеток. Рассматриваемый пример иллюстрируется на рис. 221, а и б. Соответствующая конъюнктивная нормальная форма y = (x₁ ∨ x₂)(x̅₁ ∨ x̅₂ ∨ x₃) реализуется соответствующей схемой. Комплекс кубов этой функции и его дополнение имеют вид:

; ,

а их покрытия

; .

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

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

- 547 -

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