8. Комплекс кубов. Несостоятельность графических методов при большом числе переменных компенсируется различными аналитическими методами представления булевых функций. Одним из таких представлений является комплекс кубов, использующий терминологию многомерного логического пространства в сочетании со специально разработанной символикой.
Комплекс кубов K(у) функции у = f(х1, х2, ..., хn) определяется как объединение множеств Ks(у) всех ее s-кубов (s = 0, 1, .... n),
- 544 -
т. е. 
, причем некоторые из Ks(у) могут быть пустыми. Для записи s-кубов и минитермов функции от n переменных используются слова длины n, буквы которых соответствуют всем n переменным. Входящие в минитерм переменные называются связанными и представляются значениями, при которых минитерм равен единице (1 для xi и 0 для x̅i). Не входящие в минитерм переменные являются свободными и обозначаются через х. Например, 2-куб функции пяти переменных, соответствующий минитерму x2x̅3x5 , запишется как (x10x1). 0-кубы, соответствующие конституентам единицы, представляются наборами значений переменных, на которых функция равна единице.
|
|
Рис. 219. Комплекс кубов функци трех переменных (а) и его символическое представление (б).
Очевидно, в записи s-куба всегда имеется s свободных переменных. Если все n переменных свободны, что соответствует n-кубу, то это означает тождественность единице рассматриваемой функции. Таким образом, для функций, не равных тождественно единице, Kn(y) = ∅.
Множество всех s-кубов К(у) записывается как совокупность слов, соответствующих каждому s-кубу. Для удобства будем располагать слова s-кубов в столбцы, а их совокупность заключать в фигурные скобки. Например, комплекс кубов, соответствующий представлению функции на трехмерном кубе (рис. 219, а), выражается как K(y) = K0∪K1∪K2, где
; 
; 
Для сравнения на рис. 219, б изображен комплекс кубов в принятых обозначениях.
Комплекс кубов образует максимальное покрытие функции. Исключая из него все те s-кубы, которые покрываются кубами высшей размерности, получаем покрытия, соответствующие тупиковым
- 545 -
формам. Так, для рассматриваемого примера имеем тупиковое покрытие
которое соответствует y = x̅2x3 ∨ x2x̅3 ∨ x̅1. В данном случае это покрытие являетcя и минимальным.
Для двух булевых функций операция дизъюнкции соответствует объединению их комплексов кубов K(y1 ∨ y2) = K(y1) ∪ K(y2), а операция конъюнкции - пересечению комплексов кубов K(y1y2) = K(y1) ∩ K(y2).Отрицанию функции соответствует дополнение комплекса кубов, т. е. K(y̅) = K̅(y), причем K̅(y) определяется всеми вершинами, на которых функция принимает значение 0. Таким образом, имеет место взаимно-однозначное соответствие (изоморфизм) между алгеброй булевых функций и алгеброй множеств, представляющих комплексы кубов.
Представление функций в виде комплексов кубов менее наглядно, однако его важнейшие достоинства состоят в том, что снимаются ограничения по числу переменных и облегчается кодирование информации при использовании вычислительных машин.
9. Реализация в различных формах. Реализация функции в дизъюнктивной нормальной форме представляет собой логическую схему И-ИЛИ. Например, функция y = x̅1x2 ∨ x1x̅2 ∨ x2x3 реализуется логической схемой. Более экономичная реализация получается, если общий множитель вынести за скобки: y = x2(x̅1 ∨ x3) ∨ x1x̅2. При использовании элементов со многими входами получаем двухуровневую логическую схему И—ИЛИ.
В соответствии с принципом двойственности (2.1), заменяя в дизъюнктивной нормальной форме операции конъюнкции на дизъюнкции, операции дизъюнкции на конъюнкции и беря отрицание
- 546 -
каждой переменной, получаем конъюнктивную нормальную форму, которая выражает функцию y̅, обратную к у. Ее реализация с помощью многовходовых элементов представляет собой двухуровневую логическую схему ИЛИ—И. Для рассматриваемой функции y̅ = (x1 ∨ x̅2)(x̅1 ∨ x2)(x̅2 ∨ x̅3) соответствующая реализация показана на рис. 26, г. Если требуется получить схему для данной функции у, то используется инвертор или элемент, реализующей операцию НЕ—И.