On the lattice of equational classes of Boolean functions and its closed intervals
Couceiro, Miguel (2008), On the lattice of equational classes of Boolean functions and its closed intervals, Journal of Multiple-Valued Logic and Soft Computing, 14, 1-2, p. 81-104
TypeArticle accepté pour publication ou publié
External document linkhttp://arxiv.org/abs/1105.3452
Journal nameJournal of Multiple-Valued Logic and Soft Computing
Old City Publishing
MetadataShow full item record
Abstract (EN)Let A be a finite set with | A |&Mac179;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.
Subjects / KeywordsPost Lattice; Boolean functions; closed intervals; lattice of equational classes,; equational classes; functional equations; idempotent classes; partially ordered monoids; variable substitutions; class composition; Classes of operations
Showing items related by title and author.
A Solution to a Problem of D. Lau: Complete Classification of Intervals in the Lattice of Partial Boolean Clones Couceiro, Miguel; Haddad, Lucien; Schölzel, Karsten; Waldhauser, Tamás (2017) Article accepté pour publication ou publié
A Solution to a Problem of D. Lau: Complete Classification of Intervals in the Lattice of Partial Boolean Clones Couceiro, Miguel; Haddad, Lucien; Schölzel, Karsten; Waldhauser, Tamás (2013) Communication / Conférence