Optimal Expansion and Characterization of Logic Functions and Classes

函数和类的以下优化和特征化问题是焦点：（1）布尔和多值逻辑函数的最优扩展：有效不可约基的概念（由首席研究员早些时候介绍）用于选择一组生成元用于逻辑函数的最优扩展。针对布尔函数及其生成基AND、XOR NOT，设计并实现了一种基于文字数的最短生成算法ESOP（Exclusive Sum of Products）。(2)用于描述逻辑函数类的函数项：引入了一个称为“函数项”的形式表达式，并用于简洁地描述函数类。获得了这种表征的各种性质和标准。将该方法应用于布尔函数的闭类，实现了波斯特格的完全描述。(3)克隆和泛代数：克隆（有限值逻辑函数的特殊封闭类）形成了一个代数格，对于非布尔情况仍然是未知的。研究了在格操作（连接和/或相遇）方面不可约的克隆。结果表明，格可以完全生成的连接和满足不可约克隆。这种不可约克隆的一些特殊链被描述（与I.G.Rosenberg的联合工作）。

The following optimization and characterization problems for functions and classes were in focus :(1) Optimal Expansion of Boolean and Multiple-Valued Logic Functions : The notion of efficiently irreducible bases (introduced earlier by the head researcher) was used to choose a set of generators for an optimal expansion of logic functions. For Boolean functions and one such generator base, namely AND, XOR NOT, an algorithm for building a shortest, in terms of the number of literals, ESOP (Exclusive Sum of Products) was designed and implemented.(2) Functional Terms for Characterizing Classes of Logic Functions : A formal expression called ‘functional term' was introduced and used to neatly characterize functional classes. Various properties and criteria for such characterization were obtained. The method was applied to the closed classes of Boolean functions achieving complete description of the Post's lattice in such terms.(3) Clones and Universal Algebra : Clones (special closed classes of finite-valued logic functions) form an algebraic lattice which is still widely unknown for non-boolean cases. The clones which are irreducible in terms of lattice operations (join and/or meet) were studied. It was shown that the lattice can be fully generated by both join- and meet-irreducible clones. Some special chains of such irreducible clones were described (a joint work with I.G.Rosenberg).