Equational characterizations of Boolean function classes (Q1969777)

The functions dealt with in this paper are truth functions \(f:\{0,1\}^n\to\{0,1\}\), viewed as functions \(f:\{0,1\}^n\to\{0,1\}^n\) such that the values of \(f\) are confined to the maximum \(\mathbf{1}=(1,\dots,1)\) and the minimum \(\mathbf{0}=(0,\dots,0)\) of \(\{0,1\}^n\). Several important classes of functions, defined in terms of their disjunctive normal forms (DNFs), are characterized by functional equations. For instance, a Horn function \(f\) is defined by the exististence of a DNF \(f=c_1\vee\cdots\vee c_m\) with the property that each elementary conjunction \(c_i\) has at most one negated variable; it is proved that a function \(f\) is Horn if and only if it satisfies the identity \(f(\mathbf{xy})\leq f({\mathbf x})\vee f({\mathbf y})\), where \(\mathbf{xy}\) is defined componentwise. More generally, a necessary condition for a class \({\mathcal K}\) to be defined by a set of identities is that \({\mathcal K}\) be closed under permutations of variables and identifications of variables. This condition is also sufficient if the class \({\mathcal K}\) is closed under addition of inessential variables. In that case \({\mathcal K}\) is characterized by a finite set of identities if and only if it is characterized by a single identity. Finally the authors study classes of functions characterized by simple existential sentences \(\exists v\forall v_1\dots\forall v_n\) \(T=Q\).