 |
|
Геометрическая интерпретация куба
Если два 1-куба из комплекса К1 имеют общую независимую компоненту и различаются только по одной координате, до два 1-куба образуют 2-куб. В записи 2-куба используются общие компоненты единичных кубов. Компонента, принимающая различные значения в 1-кубах, обозначается в 2-кубе как независимая компонента X. Все множество 2-кубов, построенных из комплекса К1, образует комплекс К2.
Пример:
По индукции можно определить, что два куба, сдержавшие две одноименные независимые координаты и различающиеся только одной координате, могут объединяться в (r+1) куб. (r+1)-я независимая координата которого соответствует координате, по которой различаются r-кубы. Множество (r+1)-кубов, определенное на комплексе Kr, образуют комплекс Kr+1. В рассмотренном выше примере тройные Кубы отсутствуют, то есть комплекс K3 представлен пустым множеством. Объединение кубов комплексов K0, K1, Kn функцией f(x1, x2, xn) называется уличениям комплексом функции f. Для рассматриваемой функции комплекс Kf соответствует объединению кубов K0, K1, K2.
 |
Задача минимизации булевых функций
Булевы функции используются в качестве форм, по которым строятся логические схемы. При использовании многовходовых логических элементов и/или/не логическая схема может быть построена по ДНФ или по КНФ функции. При это минимальной логической схеме соответствует наименьшее число элементарных конъюнкций (дизъюнкций) в записи функции. Каждой букве, входящей в выражение для функции, соответствует один из входов схемы, и количество входов равно числу букв в выражении для функции. Нетрудно видеть, что минимальной можно считать логическую схему, построенную по ДНФ или КНФ функции, содержащей минимальное число букв. Следует отметить, что минимизация ДНФ или КНФ функции в соответствии с указанным критерием не во всех случаях приводит к определению минимальной логической схемы. Задача минимизации булевых функций по критерию минимальности числа букв, входящих в ДНФ функции, называется канонической задачей минимизации.