Maximal and Minimal Closed Classes in Multiple-Valued Logic

We consider classes of operations in multiple-valued logic that are closed under composition as well as under permutation of variables, identification of variables (diagonalization) and introduction of inessential variables (cylindrification). Such closed classes on a given finite set form a complete lattice that includes the lattice of clones as the principal filter above the trivial clone. We determine all maximal closed classes, it turns out that there is only one family of closed classes besides Rosenberg's six families of maximal clones. For minimal closed classes we prove an analogon of Rosenberg's five-type classification of minimal clones and we describe explicitly the unary closed classes.

I. Introduction

Let be a nonempty finite set, and let be a class of finitary operations on . If is closed under composition of operations and contains the projections, then is called a clone on . There are countably infinitely many clones on a two-element base set, and all such clones were determined by Post [1]. For there exists a continuum of clones on (see [2]), and it is widely accepted that an explicit description of clones is an extremely difficult task even for . The set of all clones on is a complete lattice, and many authors have investigated different parts of these lattices of clones. Here we focus on two special classes of clones: maximal and minimal clones. Maximal clones (i.e., coatoms in the lattice of clones) have been determined by Rosenberg [3] on arbitrary finite sets. The description of minimal clones (i.e., atoms in the lattice of clones) seems to be a considerably harder problem; a full description is available only for (see [4]–[7]). However, Rosenberg classified minimal clones into five types, and for two of the types he found necessary and sufficient conditions for minimality over arbitrary finite sets [8].