Алгоритми логічного виведення поліноміальної складності

Abstract

Для логічного виведення в численні висловлювань і в численні предикатів першого порядку представлено математичний апарат булевої алгебри кубічних функцій. Клас булевої функції визначається на основі аналізу її кубічного покриття. Запропоновано алгоритми логічного виведення поліноміальної складності за допомогою операцій над кубами.

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

For logic deduction in classical propositional and first order predicate calculus the mathematical tools of Boolean algebra of cube functions is presented. The class of Boolean function is determined based on the analysis of its cube covering. The algorithms of logic deduction of polynomial complexity by operations with cubes is suggested.