On the Lattice of Equational Classes of Boolean Functions and Its Closed Intervals
Miguel Couceiro
Let A be a finite set with | A | ≥ 2. The composition of two classes I and J of operations on A, is defined as the set of all composites f (g1 …,gn) with f ∈ I and g1 …,gn ∈ J . This binary operation gives a monoid structure to the set EA of all equational classes of operations on A.
The set EA of equational classes of operations on A also constitutes a complete distributive lattice under intersection and union. Clones of operations, i.e. classes containing all projections and idempotent under class composition, also form a lattice which is strictly contained in EA. In the Boolean case | A |=2, the lattice EA contains uncountably many (2ℵ0) equational classes, but only countably many of them are clones.
The aim of this paper is to provide a better understanding of this uncountable lattice of equational classes of Boolean functions, by analyzing its “closed” intervals [C 1, C 2], for idempotent classes C 1 and C 2. For | A |=2, we give a complete classification of all closed intervals [C 1, C 2] in terms of their size, and provide a simple, necessary and sufficient condition characterizing the uncountable closed intervals of EA.