×

Functional equations, constraints, definability of function classes, and functions of Boolean variables. (English) Zbl 1120.06011

Summary: The paper deals with classes of functions of several variables defined on an arbitrary set \(A\) and taking values in a possibly different set \(B\). Definability of function classes by functional equations is shown to be equivalent to definability by relational constraints, generalizing a fact established by Pippenger in the case \(A=B=\{0,1\}\). Conditions for a class of functions to be definable by constraints of a particular type are given in terms of stability under certain functional compositions. This leads to a correspondence between functional equations with particular algebraic syntax and relational constraints with certain invariance properties with respect to clones of operations on a given set. When \(A=\{0,1\}\) and \(B\) is a commutative ring, such \(B\)-valued functions of \(n\) variables are represented by multilinear polynomials in \(n\) indeterminates in \(B[X_1,\dots ,X_n]\). Functional equations are given to describe classes of field-valued functions of a specified bounded degree. Classes of Boolean and pseudo-Boolean functions are covered as particular cases.

MSC:

06E30 Boolean functions
08A40 Operations and polynomials in algebraic structures, primal algebras