Archive
Special Issues Volume 8, Issue 2, April 2019, Page: 30-36
Algebra of Finite-Valued Functions: Classification of Functions and Subalgebras, Essential and Fictitious Subalgebras
Maydim Malkov, Department of mathematics, Russian Research Center for Artificial Intelligence, Moscow, Russia
Received: Apr. 28, 2019;       Accepted: Jun. 2, 2019;       Published: Jun. 26, 2019
Abstract
The classification of subalgebras of every algebra of finite-valued functions is constructed. Classes of this classifications do not intersect. Each class contains subalgebras with the same number of functions in minimal basis. Class with ordinal number 0 contains subalgebras that have no basis. The class with finite ordinal number n contains subalgebras whose minimal basis has n functions. The set of subalgebras of this class are countable. There is a class with infinite ordinal number. Subalgebras of this class have a minimal basis with infinite number of functions. The set of these subalgebras is continual. Only the class with ordinal number 1 is essential, all other classes are fictitious, since they are useless to classify functions. But classification of functions is the main problem of the algebra of finite-valued functions. A class of this classification is a set of functions extracted from one-member bases of a subalgebra. Each function generates by superpositions some subalgebra, and only this subalgebra. So, this function belongs to only one class. All these classes of functions belong to the class 1 of subalgebras. All subalgebras from classes with the other ordinal numbers are useless to classify functions. The set of these fictitious subalgebras is continual, the set of essential subalgebras are countable. The top level of the classification of functions contains the algebra of finite-valued functions. Next level contains maximal subalgebras. According to I.G. Rosenberg, there are 6 sets of maximal subalgebras. I.G. Rosenberg was wrong to state the set of his quasilinear functions be maximal. Only Yablonsky’s set of quasilinear functions is maximal. The sixth Rosenberg’s set also turns to be wrong. This right set was built by A.I. Maltsev. But from 6 sets only 3 sets contain essential subalgebras. And all maximal essential subalgebras containing 3-valued 2-place functions are built.
Keywords
Algebra of Finite-Valued Functions, Classification of Finite-Valued Functions, Post Algebras, Maximal Algebras
Maydim Malkov, Algebra of Finite-Valued Functions: Classification of Functions and Subalgebras, Essential and Fictitious Subalgebras, Pure and Applied Mathematics Journal. Vol. 8, No. 2, 2019, pp. 30-36. doi: 10.11648/j.pamj.20190802.11
Reference

E. L. Post, Introduction to a general theory of elementary propositions Amer. J. Math., (43), 163–185 (1921).

E. L. Post, Two-valued iterative systems of mathematical logic, Princeton, Princeton Univ. Press (1941).

A. V. Kuznetsov, On means for detecting of non-deductibility and inexpressibleness (Russian), in Logical conclusion, M., Science, 5–33 (1979).

S. S. Marchenkov, On Expressibility of Multivalued Logic Functions in some Logic-Functional Languages (Russian), Discrete Mathematics, (11:4), 110–126 (1999).

S. S. Marchenkov, S-classification of many-valued logic functions, Discrete Mathematics (9:3), 125–152 (1997).

S. S. Marchenkov, S-classification of many-valued logic functions (Russian), M., Physmatlit (2001).

S. S. Marchenkov, Equational closure (Russian), Discrete Mathematics, (17:2), 117–126 (2005).

S. S. Marchenkov, On structure of equationally closed classes (Russian), Discrete Mathematics, (18), 18–30 (2006).

S. S. Marchenkov, Definability in language of functional equations of countably-valued logic (Russian), Discrete Mathematics, (25:4), 13–23 (2013).

S. S. Marchenkov, On FE-Precomplete Classes of Countable Logic (Russian), Discrete Mathematics, (28:2), 51–57 (2016).

A. V. Kuznetsov, Algebra of logic and its generalization (Russian), in Mathematics in USSR for 40 years, M. Physmatlit, 102–115 (1959).

E. Yu. Zakharova, V. B. Kudryavtsev, S. V. Yablonsky, On precomplete classes in k-valued logics (Russian), Reports of USSR Academy of Sciences (186:3), 509–513 (1969).

S. V. Yablonsky, Functional constructions in k-valued logic (Russian), Proceedings of Mat. Institute of the USSR Academy of Sciences. V. A. Steklova, (51) 5–142 (1958).

D. Lau, Submaximale klassen von P3, J. Inf. Process. Cybern. EIK (18:4/5), 227-243 (1982).

I. G. Rosenberg, The number of maximal closed classes in the set of functions over a finite domain, J. combinat. Theory, Ser. A (14), (1–7) (1973).

Yu. I. Yanov, A. A. Muchnik, On the existence of k -valued closed classes that do not have a finite basis (Russian), Doc. USSR Academy of Sciences, (127:1), 44–46 (1959).

M. A. Malkov, Classification of Closed Sets of Functions in Multi-valued Logic, SOP Transactions on applied Math., (1:3), 96–105 (2014).

M. A. Malkov Classifications of Boolean Functions and Their Closed Sets, SOP Transactions on applied Math., (1:2), 172–193 (2014).

A. I. Maltsev, Iterative Post Algebras, Novosibirsk, Novosib. state un-t (1976).

M. A. Malkov, Finite Closed Sets of Functions in Multi-Valued Logic, Pure and Appl. Math J., (6:1), 14-24 (2017).

S. V. Yablonsky, G. I. Gavrilov, V. B. Kudryavtsev, Functions of the algebra of logic and Post classes, M., Science (1966).

I. G. Rosenberg, Complete sets for finite algebras Math. Nachr., (4), 253-258 (1970).

D. Lau, Function algebras on finite sets, Berlin, Heidelberg, New York, Springer monographs in mathematics (2006).

N. M. Martin, The Sheffer functions of tree valued logic, J. Symb. Log (19), 45-51 (1954).

M. A. Malkov Complete generators in 4-valued logic and Rousseau’s results, Intern. J. of Math. and its Applications, (2:6), 49-57 (2014). 