Equational characterizations of Boolean function classes

DOI10.1016/S0012-365X(99)00132-6MaRDI QIDQ1969777zbMATH OpenWikidataFDO

Authors Oya Ekin, Stephan Foldes, Peter L. Hammer, Lisa Hellerstein

Publication date 7 November 2000

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(99)00132-6

zbMATH Keywords

disjunctive normal forms functional equations Horn function truth functions

Mathematics Subject Classification ID

Equational classes, universal algebra in model theory (03C05) Boolean functions (06E30)

Review text

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\).

Recommendations

Cited in

(45)

This page was built for publication: Equational characterizations of Boolean function classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1969777)