
РЕШЕНИЕ ЗАДАЧИ ВЫПОЛНИМОСТИ НА ОСНОВЕ СКНФ
Author(s) -
Александр Игоревич Борисенко
Publication year - 2021
Publication title -
grail of science
Language(s) - Russian
Resource type - Journals
ISSN - 2710-3056
DOI - 10.36074/grail-of-science.19.11.2021.062
Subject(s) - computer science
В статье предлагается новый подход к решению задачи выполнимости, использующий преобразование конъюнктивной нормальной формы (КНФ) исходной булевой функции в ее совершенную конъюнктивную нормальную форму (СКНФ), что позволяет находить его более быстро по сравнению с методом перебора наборов значений переменных, как это происходит в имеющихся решениях данной задачи. Такой переход осуществляется через промежуточную форму по отношению к СКНФ (ПСКНФ). В ней в отличие от СКНФ может быть повторение конституент 0. Их исключение и является особенностью и главной трудностью решения задачи, требующего затрат времени.