On the complexity of enumerations for multiple-valued Kleenean functions and unate functions

Author

Hata, Yutaka ; Yuhara, M. ; Miyawaki, Fujio ; Yamato, Kazuharu

Author_Institution

Fac. of Eng., Himeji Inst. of Technol., Japan

fYear

1991

fDate

26-29 May 1991

Firstpage

55

Lastpage

62

Abstract

Multiple-valued Kleenean functions are represented by multiple-valued AND, OR, NOT, variables and constants. In their previous work (see proc. of 20th Int. Symp. Multiple Valued Logic, IEEE, p.410-17, 1990), the authors pointed out that both mapping from Kleenean functions to some (3,p)-functions and mapping from unate functions to some (2,p)-functions are bijections. In this paper, by using the above relations, 3-up-to-7 valued Kleenean functions of 3-or-less variables are enumerated on a computer. Their exact numbers are tabulated. The results show that as p becomes larger, the number of p-valued Kleenean functions increases stepwise, and that of p-valued unate functions increases smoothly

Keywords

computational complexity; many-valued logics; switching functions; bijections; multiple-valued Kleenean functions; p-valued unate functions; unate functions; Facsimile; Logic functions; Multivalued logic; Quantization; Telephony;

fLanguage

English

Publisher

ieee

Conference_Titel

Multiple-Valued Logic, 1991., Proceedings of the Twenty-First International Symposium on

Conference_Location

Victoria, BC

Print_ISBN

0-8186-2145-1

Type

conf

DOI

10.1109/ISMVL.1991.130705

Filename

130705