Rational A-functions with rational coefficients
https://doi.org/10.22405/2226-8383-2022-23-4-11-19
Abstract
functional system is a set of functions endowed with a set of operations on these functions.
The operations allow one to obtain new functions from the existing ones.
Functional systems are mathematical models of real and abstract control systems and thus are one of the main objects of discrete mathematics and mathematical cybernetic.
The problems in the area of functional systems are extensive. One of the main problems is deciding completeness that consists in the description of all subsets of functions that are complete, i.e. generate the whole set.
In our paper we consider the functional system of rational functions with rational coefficients endowed with the superposition operation. We investigate the special case of the completeness problem which is of a particular interest, namely obtaining complete systems of minimum cardinality, i.e. complete systems consisting of a single rational function (such functions are
referred to as 𝐴-functions and are analogues of Schaeffer stroke in Boolean logic).
The main results of the paper are the following:
- there exists an A-function;
- the cardinality of the set of all A-functions equals c_0;
- a number of examples of A-functions are presented explicitly.
About the Author
Nikos Filippovich Aleksiadis
Lomonosov Moscow State University; National Research University “MPEI”
Russian Federation
Russian Federation
candidate of physical and mathematical sciences
References
1. Aleksiadis, N. Ph. 2021, “Rational 𝐴-functions with rational coefficients“, Proc. 19th Int. Conf.
2. “Algebra, number theory and discrete geometry: modern problems, applications and problems of
3. history“, pp. 97-101.
4. Aleksiadis, N. Ph. 2011, “On the existence of recursive A-functions“, Vestnik MPEI, no. 6, pp.
5. -111.
6. Aleksiadis, N.Ph., & Than Htun Aung 2013, “On the recursive A-function“, Proceedings of the
7. XXI International Scientific and Technical Conference ‘Information tools and Technologies”,
8. vol. 3, pp. 96-101.
9. Babin, D. N. 2020, “On the completeness problem for automata“, Proc. Intelligent systems.
10. Theory and Applications, vol. 23(4), pp. 82-83.
11. Gavrilov, G.P. 1965, “On functional completeness in countable logic“, Problems of cybernetics,
12. vol. 15, pp. 5-64.
13. Kudryavtsev, V. B. 1965, “On the powers of sets of discrete sets of some functional systems
14. related to automata“, Problems of cybernetics, vol. 13, pp. 45-74.
15. Kudryavtsev, V. B. 1982, “Functional systems “, Moscow: Publishing House of Mekh-mat. fac.
16. MSU., 157 p.
17. Maltsev, A. I. 1976, “Selected works“. vol. II — Moscow: Publishing House “Nauka“, 388 p.
18. Salomaa, A. 1963, “Some completeness criteria for sets of functions over a finite domain“, II.
19. Ibid., Ser. A I 63, 19 pp.
20. Chasavskikh, A. A. 2018, “The problem of completeness in classes of linear automata“, Intelligent
21. systems. Theory and Applications, vol. 22(2), pp. 151-154.
22. Yablonsky, S. V. 1986, “Introduction to discrete mathematics“, Moscow.:Science, 384 p.
23. Yablonsky, S. V. 1954, “On functional completeness in three-digit calculus“, DAN USSR, vol.
24. (6), pp. 1153–1156.
25. Yablonsky, S. V. 1958, “Functional constructions in 𝑘-valued logic“, Proceedings of the Steklov
26. Institute of Mathematics, vol.51, pp. 5–142.
27. Post, E. 1941,“Two-valued iterative sistems of mathematical logik“. — Prinston.
28. Rosenberg, Y.1970, “Uber die functionale Vollst¨andigkeit in den mehrwertigen Logiken“. Praha,
29. Rozpravi Ceskoslovenska Acodemie Ved., v. 80, №4, p. 393.
30. Slupecki, J. 1939, Kriterium pelnosci wielowar — tosciowych systemow logiki zdan. Comptes
31. Rendus des Seances de la Societe des Sciences et des Lettres de Varsivie, cl. III, v. 32, pp.
32. -128.
Review
For citations:
Aleksiadis N.F. Rational A-functions with rational coefficients. Chebyshevskii Sbornik. 2022;23(4):11-19. (In Russ.) https://doi.org/10.22405/2226-8383-2022-23-4-11-19
Views:
451
Email this article 