Об усовершенствовании метода выделения переменных при решении логических уравнений

Для решения логических уравнений вида $F({{x}_{1}}, {{x}_{2}}, \ldots, {{x}_{{{k}_{0}}}})=1$ был предложен метод выделения переменных. Данная работа направлена на повышение эффективности указанного метода, что связано с уменьшением наибольшего объёма промежуточных форм, которые получаются в процессе выделении переменных. Такой результат достигается за счёт: 1) объединения некоторых элементов дизъюнктивных форм функций исходной суперпозиции $F$ перед их логическим перемножением и 2) отказа от подстановки или упрощением вида подставляемых дизъюнктивных форм функций, которые не влияют на образование нуль-конъюнкций $x_{u}\bar{x}_{u}$ при получении ДНФ функции $F$. Показано, что объём памяти, необходимый для размещения конечной ДНФ, можно уменьшить, если формировать одну или часть её членов из скобочной формы функции $F$, полученной после выделения всех переменных, образующих при преобразовании исходной совокупности функций в ДНФ хотя бы одну нуль-конъюнкцию $x_{u}\bar{x}_{u}$ $(u\in\{1,2,\ldots,k_{0}\})$. Введен более эффективный по сравнению с представленным в работе {[ Пошерстник М. С. Решение логических уравнений методом выделения переменных // Автоматика и телемеханика. – 1979. – T. 2. – C. 132—140.]} критерий отбора переменных выделения, определяющих очередной этап декомпозиции исходной задачи.

Ключевые слова: логические уравнения, выделение переменных, декомпозиция задачи.