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

Задача алгебраической декомпозиции булевой функции (в англоязычной литературе – bi-decomposition) заключается в представлении заданной булевой функции с помощью логической операции над двумя булевыми функциями. Предлагается для реализации систем не полностью определенных (частичных) булевых функций в базисе двухвходовых логических элементов использовать метод, основанный на алгебраической декомпозиции булевых функций. В качестве базиса могут быть следующие базисы элементов: ИЛИ-НЕ, И-НЕ или И, ИЛИ при доступной инверсии входных сигналов. Применяемый метод алгебраической декомпозиции сводится к поиску двухблочного взвешенного покрытия полными двудольными подграфами (бикликами) взвешенного двудольного графа, представляющего собой различия между строками булевых матриц, которые задают рассматриваемую систему функций. Исходная система частичных булевых функций задается двумя булевыми матрицами, одна из которых служит областью булева пространства аргументов, где значения функций определены, а другая – значениями функций на элементах указанной области. Каждой биклике из получаемого покрытия приписывается в качестве веса некоторое множество переменных, являющихся аргументами функций заданной системы. Каждая из этих биклик определяет булеву функцию, аргументы которой – приписанные к биклике переменные. Полученные таким образом функции составляют разложение исходной функции. Процесс синтеза комбинационной схемы заключается в последовательном применении алгебраической декомпозиции к этим функциям. Описан способ получения двухблочного взвешенного покрытия бикликами упомянутого двудольного графа.