Об $m$-юнктивных предикатах на конечном множестве

Рассматриваются предикаты на конечных множествах. Предикаты, инвариантные относительно некоторой $(m+1)$-местной функции почти единогласия, названы $m$-юнктивными. Предлагается представление предикатов на конечном множестве в виде обобщённых конъюнктивных нормальных форм (ОКНФ). Получены свойства ОКНФ для $m$-юнктивных предикатов. Показано, что каждый $m$-юнктивный предикат может быть представлен полностью согласованной ОКНФ, в которой каждый конъюнкт содержит не более $m$ переменных. Такое представление $m$-юнктивного предиката названо приведённым. Предложен быстрый алгоритм нахождения приведённого представления $m$-юнктивного предиката. Показано, как полученные свойства ОКНФ для $m$-юнктивных предикатов можно применить для построения быстрого алгоритма задачи обобщённой $S$-выполнимости, в которой множество $S$ содержит только предикаты, инвариантные относительно одной и той же функции почти единогласия. Библиогр. 15.