On m-Junctive Predicates on a Finite Set

Abstract

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.