Functional Completeness of Multi-valued Logical Functions under Uniform Compositions
Akihiro Nozaki · Institutional Repositories DataBase (IRDB) · 1978
Here considered is the problem of functional completeness of multi-valued logical functions under a certain restricted composition. We define the notion of ^*-completeness of a set of functions, which represents the universality of a set of gate-type elements of digital circuits each of which has a common delay. We have established a decidable criterion for a set of multi-valued logical functions to be ^*-complete. We gave a representation theorem of maximal ^*-incomplete sets, and listed up all maximal ^*-incomplete sets of logical functions and those of ternary logical functions. As S. V. Yablonski has conjectured, the number of maximal ^*-incomplete sets is shown to be finite.