On $m$-junctive predicates on a finite set

We consider predicates on finite sets. The predicates invariant under some $(m+1)$-ary near-unanimity function are called $m$-junctive. We propose to represent the predicates on a finite set in generalized conjunctive normal forms (GCNFs). The properties for GCNFs of $m$-junctive predicates are obtained. We prove that each $m$-junctive predicate can be represented by a strongly consistent GCNF in which every conjunct contains at most $m$ variables. This representation of an $m$-junctive predicate is called reduced. Some fast algorithm is proposed for finding a reduced representation for an $m$-junctive predicate. It is shown how the obtained properties of GCNFs of $m$-junctive predicates can be applied for constructing a fast algorithm for the generalized $S$-satisfiability problem in the case that $S$ contains only the predicates invariant under a common near unanimity function. Bibliogr. 15.