2015-07-21
364
В практических задачах при абстрактном и структурном синтезе конечных автоматов большое значение имеет задача нахождения минимальных форм функций алгебры логики. В общем виде она формулируется следующим образом.
Пусть задан базис 
, причем для каждой функции 
базиса сопоставляется некоторое число 
, 
называемое весом.
Пусть для заданной функции 
найдено выражение через функции базиса такое, что 
используется при его написании 
раз, 
. Тогда
.
будем называть весом данного выражения функции в заданном базисе.
Задача минимизации функции состоит в нахождении такого ее выражения через функции базиса 
, которое бы имело по возможности минимальный вес 
.
В такой общей постановке задача пока не решена. Обычно находят не абсолютно минимальную форму функции в данном базисе, а форму, минимальную среди некоторого класса выражений функции в этом базисе.
Одним из наиболее исследованных в этом смысле базисов является И-ИЛИ-НЕ.
