{
  "id": "1105.3452",
  "version": "v1",
  "published": "2011-05-17T19:05:48.000Z",
  "updated": "2011-05-17T19:05:48.000Z",
  "title": "On the lattice of equational classes of Boolean functions and its closed intervals",
  "authors": [
    "Miguel Couceiro"
  ],
  "journal": "Journal of Multiple-Valued Logic and Soft Computing 18 (2008) 81--104",
  "categories": [
    "math.CO"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-05-17T19:05:48.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "equational classes",
      "closed intervals",
      "boolean functions",
      "monoid structure",
      "complete distributive lattice"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1105.3452C"
    }
  }
}