Аннотация:В работе исследуется предикатная эквивалентность формул, вводимая
с помощью множества предикатов ${\cal P}$ и множества перестановок
$M$. Множества ${\cal P}$ и $M$ согласованы, если соответствующая
им предикатная эквивалентность совпадает с обычной
эквивалентностью формул. Доказывается критерий согласованности
множеств. Предложен алгоритм построения согласованных множеств
предикатов. Приводятся серии примеров взаимно согласованных
множеств ${\cal P}$ и $M$ с разными соотношениями сложностных
характеристик.
Predicate equivalence of Boolean algebra formulas is investigated
in the paper. Predicate equivalence is defined with help of a set
of predicates ${\cal P}$ and a set of permutations $M$. The sets
${\cal P}$ and $M$ are conformed if predicate equivalence
coincides with common equivalence of Boolean formulas. Criterion
of the sets conformity is proved. The algorithm of construction of
conformed sets is suggested. Examples of conformed sets ${\cal P}$
and $M$ are given.
