Метод бидекомпозиции частичных булевых функций
Задача бидекомпозиции (от англ. bi-decomposition) булевой функции заключается в представлении заданной булевой функции в виде некоторой заданной операции алгебры логики над двумя булевыми функциями и сводится таким образом к определению этих функций. Каждая из искомых функций должна обладать меньшим числом аргументов, чем заданная. Предлагается метод бидекомпозиции для не полностью определенных (частичных) булевых функций, который использует подход, применяемый в решении общей задачи их параллельной декомпозиции. Задание исходной функции должно иметь вид пары матриц. Одна из них, матрица аргументов, может быть троичной или булевой и представляет область определения заданной функции. Другая матрица, матрица значений, имеет вид одного булева вектора-столбца и показывает значения функции на интервалах или элементах булева пространства аргументов. Рассматриваются граф ортогональности строк матрицы аргументов и граф ортогональности одноэлементных строк матрицы значений. Задача бидекомпозиции сводится к задаче о двухблочном взвешенном покрытии множества ребер графа ортогональности строк матрицы значений полными двудольными подграфами (бикликами) графа ортогональности строк матрицы аргументов. Каждой биклике приписывается определенным образом дизъюнктивная нормальная форма (ДНФ), и весом биклики считается минимальный ранг элементарной конъюнкции в соответствующей ДНФ. По каждой из биклик полученного покрытия строится булева функция, аргументами которой служат переменные из элементарной конъюнкции минимального ранга соответствующей ДНФ, что является решением задачи бидекомпозиции.
