Classification of minimal clones in multiple-valued logic and finite fields

对于集合A，A上的克隆是A上包含所有投影且在合成下闭的多元函数的集合。A上所有克隆的集合形成了一个格，称为A上的克隆格，记为L_A。L_A的结构非常复杂，到目前为止，人们还很少知道它的结构。所有投影中的克隆J_A显然是L_A格的最小元素。集合L_A-JA的一个极小元素称为极小克隆。将有限域GF(|A|)的结构引入到有限基集A中，并将集合A上的极小函数看作是定义在GF(|A|)上的多项式，从而得到一个新的研究方法。通过这种方法，我们试图将极小函数的性质理解为有限域上多项式的性质。从B.Csakany给出了三元集合上所有极小克隆的结果出发，我们首先将Csakany的极小函数表示为GF(3)上的多项式，并将其中的一些推广到任意有限域GF(K)上的多项式，其中k是任意素数幂.更具体地说，我们考虑了极小函数是(1)二元幂等函数和(2)三元多数函数的情况.其中，我们得到了二元线性极小多项式和二元极小单项式的完全刻画。此外，我们还得到了多项式对任意素数次方k在GF(K)上生成极小克隆的例子。

For a set A, a clone on A is a set of multi-variable functions on A which contains all projections and is closed under composition The set of all clones on A forms a lattice which is called the clone lattice over A and is denoted by L_A. The structure of L_A is extremely complex and , up to now, largely unknown.The clone J_A of all projections is clearly the least element of the lattice L_A. A minimal element of the set L_A-J A is called a minimal clone. A minimal clone is generated by a single function, which is called a minimal function..In this research, we employed a new method of research by introducing the structure of a finite field GF(|A|) into the finite base set A and treating minimal functions over the set A as polynomials defined over GF(|A|). In this way we tried to grasp the properties of minimal functions as the properties of polynomials over a finite field. Starting from the result of B. Csakany who presented all minimal clones over a three-element set, we first expressed Csakany's minimal functions as polynomials over GF(3) and generalized some of them to polynomials over arbitrary finite field GF(k) where k is any prime power.More specifically, we considered the cases where minimal functions are (1) binary idempotent functions and (2) ternary majority functions. We obtained, among others, the complete characterization of binary linear minimal polynomials as well as binary minimal monomials. Furthermore, we have obtained many examples of polynomials generating minimal clones over GF(k) for any prime power k.