Optimal Expansion and Characterization of Logic Functions and Classes

逻辑函数和类的最佳扩展和表征

• 批准号: 13640136
• 负责人: POGOSYAN Grant R.
• 金额: $ 2.05万
• 依托单位: College of Liberal Arts, International Christian University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2004
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13640136/
• 关键词: boolean functions; optimal expansions; clones; multiple-valued logic; functional terms; logic functions; universal algebra

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).

以下函数和类的优化和表征问题是重点：（1）布尔和多值逻辑函数的优化扩展：有效不可约基的概念（由首席研究员之前引入）用于选择一组生成器以实现逻辑函数的优化扩展。对于布尔函数和这样的生成器基，即AND、XOR NOT，一种用于构建在文字数量方面最短的算法，设计并实现了ESOP（乘积异和）。（2）用于表征逻辑函数类的函数术语：引入了一种称为“函数术语”的形式表达式，并用于整齐地表征函数类。获得了这种表征的各种性质和标准。该方法被应用于布尔函数的封闭类，从而实现了对波斯特格的完整描述。(3)克隆和通用代数：克隆（有限值逻辑函数的特殊封闭类）形成了一个代数格，对于非布尔情况，它仍然是广泛未知的。研究了在晶格操作（连接和/或相遇）方面不可约的克隆。结果表明，连接不可约克隆和相遇不可约克隆都可以完全生成晶格。描述了此类不可还原克隆的一些特殊链（与 I.G.Rosenberg 合作）。

项目成果

Grant R.Pogosyan, Ivo G.Rosenberg: "An Algorithm for Optimal Representation of a Partial Boolean Function as a mod2 Sum of Products"Proceedings of 6th International Symposium on Representations and Methodology of Future Computing Technology. RM2003. 27-34

Grant R.Pogosyan、Ivo G.Rosenberg：“将部分布尔函数优化表示为 mod2 乘积和的算法”第六届未来计算技术表示与方法国际研讨会论文集。

Grant R.Pogosyan, Ivo G.Rosenberg: "Algebraic Properties of Totally Irreducible Elements of Clone Lattices"Proceedings of 34rd International Symposium on Multiple-Valued Logic. IEEE Press. (to appear in May). (2004)

Grant R.Pogosyan、Ivo G.Rosenberg：“克隆格子完全不可约元素的代数性质”第 34 届国际多值逻辑研讨会论文集。

高橋 正子: "プログラムの起源を探る"数学教育学会誌. 秋季臨時増刊号. 78-80 (2003)

Masako Takahashi：“探索程序的起源”数学教育学会秋季特刊78-80（2003）。

Grant R.Pogosyan: "Classes of Boolean Functions Defined by Functional Terms"Multiple Valued Logic, Gordon and Breach Publishers. Vol.7. 417-448 (2002)

Grant R.Pogosyan：“由函数术语定义的布尔函数类”多值逻辑，Gordon 和 Breach 出版商。

Masako Takahashi: "Lambda- representable functions over term algebras"International Journal of Foundations of Computer Science. 12. 3-29 (2001)

Masako Takahashi：“Lambda-可表示的代数函数”国际计算机科学基础杂志。