Для любой булевой функции (БФ) Y(x1,…, xi,…,xm) существует «интегральная функция»,
с помощью которой можно за 2*m шагов получить одно из решений уравнения
Y(x1,…, xi,…,xm) = 1
и за один шаг определить, имеет ли данная БФ хоть одно ненулевое значение.
Данная БФ принадлежит к классу, для которого существует "приемлемо компактная" форма представления. Предполагается, что ее «интегральная функция» также имеет "приемлемо компактную" форму представления.
Для бесповторных БФ это уже доказано.
Для небесповторных БФ вопрос компактной формы «интегральной функции» следует искать в области упрощения символьных выражений (компьютерная алгебра), где утверждается, что не существует общего метода упрощения для всех классов символьных выражений.
http://www.diary.ru/~Organon/p68635357.htmЭто имеет какую-то научную ценность?
