On a quasi-ordering on Boolean functions
It was proved few years ago that classes of Boolean functions definable by means of functional equations [O. Ekin, S. Foldes, P.L. Hammer, L. Hellerstein, Equational characterizations of boolean functions classes, Discrete Mathematics 211 (2000) 27-51], or equivalently, by means of relational constraints [N. Pippenger. Galois theory for minors of finite functions, Discrete Mathematics 254 (2002) 405-419], coincide with initial segments of the quasi-ordered set (Omega,  , subset of) also embeds ([omega](<omega), subset of). From this result, we deduce that the dual space of the distributive lattice made of finitely definable classes is uncountable. Looking at examples of finitely definable classes, we show that the classes of Boolean functions with a bounded number of essential variables are finitely definable. We provide a concrete equational characterization for each of these classes, and for the subclasses made of linear functions. We describe the classes of functions with bounded polynomial degree in terms of minimal obstructions. (C) 2008 Elsevier B.V. All rights reserved.
quasi-orders boolean functions functional equations relational constraints minors initial segments essential variables linear functions qosets partial-orders posets antichains order-embeddings equational classes