Post classes characterized by functional terms Original Research Article

The classes of Boolean functions closed under classical compositions form an algebraic lattice which was completely described in 1941 in a pioneering work of Post (Ann. Math. Stud. (5) (1941)). These classes and the lattice are often referred to as the Post Classes and the Post Lattice, respectively. There are several approaches to present a Post class. Being a set of functions it can be characterized by a traditional set-theoretic description of its members. Since the Post classes are closed under certain operations, they are also often presented by sets of generators. A remarkable approach, which has been widely used in Universal Algebra is a characterization of classes by means of preservation of polyrelations (Kibernetika (3)(Pt1) (1969) 1, (5)(PtII) (1969) 1). Recently, there appeared several new methods for the characterization of classes of logic functions. These methods are based on special formal expression, which in general define a much larger variety of classes particularly including all Post classes. One such result is by Ekin et al. (Discrete Math. 211 (2000) 27), which presents the characterization of classes by a set (possibly infinite) of certain equational identities. The approach developed in [Ekin et al. (2000)] was soon extended to several directions. Pippenger (Discrete Math. 254 (2002) 405) presented the classes through pairs of relations (constrains) in the setting of a Galois Theory. Pogosyan (Multiple Valued Logic, Gordon and Breach, London, 2001, pp. 417–448, Vol. 7) has defined each such class by one functional term (possibly of infinite length), and has introduced the notion of rank for a term as well as for a class. In (Algebra Universalis 44 (2000) 309) established a connection with the Birkhoff-Tarski HSP Theorem. This paper presents a complete characterization of the Post Classes by means of functional terms (as in [Pogosyan, 2001]). We also give a constructive criterion which establishes the minimal ranks for all Post classes.