Задача минимизации булевых функций

Выражения булевых функций являются математическими моделями, на основании которых строятся комбинационные схемы. Проектируемые схемы должны быть оптимальными в смысле минимума используемого оборудования при выполнении ограничений на быстродействие схемы, которое определяется временем распространения сигналов от входов схемы к ее выходам. Количество оборудования, используемого в схеме, принято характеризовать ценой схемы. Если в схеме используются элементы k типов с ценами s₁, s₂, ..., s_k, и в количестве п₁, п₂,…, п_k, то цена схемы определяется суммарной ценой элементов:

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

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

Обычно задача упрощения булевых функций решается в два этапа. На первом этапе упрощается ДНФ или КНФ функций путем решения задачи минимизации. Нормальные формы, получаемые при этом, называются минимальными. На втором этапе производится дальнейшее упрощение минимальных нормальных форм функций, путем преобразования их в скобочные формы (задача факторизации булевых функций). Окончательная форма функций используется для построения проектируемой схемы.

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