pith. sign in

arxiv: 1105.3452 · v1 · pith:YXX4WAQOnew · submitted 2011-05-17 · 🧮 math.CO

On the lattice of equational classes of Boolean functions and its closed intervals

classification 🧮 math.CO
keywords classesequationallatticeclosedfunctionsintervalsoperationsboolean
0
0 comments X
read the original abstract

Let A be a finite set with at least two elements. The composition of two classes I and J of operations on A, is defined as the set of all compositions of functions in I with functions in J. This binary operation gives a monoid structure to the set E_A of all equational classes of operations on A. The set E_A 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 E_A. In the Boolean case |A|=2, the lattice E_A contains uncountably many 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 clones C_1 and C_2. For |A|=2, we give a complete classification of all such closed intervals in terms of their size, and provide a simple, necessary and sufficient condition characterizing the uncountable closed intervals of E_A.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.