×

Generating sequences for \(k\)-valued logic. (English) Zbl 0752.06006

Summary: The concept of a generating set of boolean functions was introduced by S. Kundu in a recent paper [Basis for synthesis of switching functions, Preprint, Digit. Equipm. Corp. (1988)]. Its treatment depends heavily on the choice of a basis for boolean functions [e.g., the familiar basis consisting of disjunction, conjunction, negation, and the two constants, or the Reed-Muller basis [see M. Davio, J.-P. Deschamps and A. Thayse, Discrete and switching functions (1978; Zbl 0385.94020)] consisting of the sum \(\mod 2\), conjunction, and the two constants]. In this note we make the basic ideas of Davio et al. [loc. cit.] more precise and expand them. The essence is the study of self-maps of \(\{0,1\}^ n\), which is completely basis independent. Without any additional effort we get the same result for the functions of \(k\)-valued logic for all integers \(k>1\). We therefore present it directly in this setting.

MSC:

06E30 Boolean functions
03B50 Many-valued logic
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)

Citations:

Zbl 0385.94020
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Davio, M.; Deschamps, J.; Thayse, A., Discrete and Switching Functions (1978), Mc-Graw-Hill
[2] Kundu, S., Basis for synthesis of switching functions, ((1988), Digital Equipment Corp), 15, Preprint
[3] Post, E., The Two-Valued Iterative Systems of Mathematical Logic, (Ann. Math. Stud., 5 (1941), Princeton U.P) · Zbl 0063.06326
[4] Rosenberg, I. G., Composition of functions on finite sets, completeness and relations, a short survey, (Rine, D., Multiple-Valued Logic and Computer Science (1977), North-Holland), 144-187
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.