Algorithm for Finding Minimal Algebras of Binary Multioperations of Rank 3
Abstract
The theory of discrete functions studies not only the everywhere defined functions of k-valued logic, but also functions that are not defined on all sets. Uncertainty can be understood in different ways depending on the class of problems under consideration. If the image of an element is an arbitrary finite subset, then such functions are usually called multioperations.
The theory of multioperations is a fairly new direction in mathematics and has many open problems. The development of this theory, in the future, can lead to the development of new approaches in theoretical informatics, mathematical cybernetics and their applications. To solve such problems, it is necessary to develop algorithms that are capable of working with a large amount of data, since with an increase in parameters, the number of multioperations grows exponentially.
The article proposes an algorithm for finding all minimal algebras of binary multioperations of rank 3. The algorithm is based on two stages. The first stage prepares the base of minimal algebras for the second stage. In the second step, all algebras are checked based on the result of the first step. This algorithm helped to find all minimal algebras of binary multioperations of rank 3, as well as find all minimal algebras closed with union.
References
[2] Post E.L. Determination of All Closed System of Truth Tables. Bulletin American Mathematical Society. 1920; 26:437. (In Eng.)
[3] Vinokurov S.F., Periazeva N.A. (ed.) Izbrannye voprosy teorii bulevyh funkcij [Selected Questions of the Theory of Boolean Functions]. Fizmatlit, Moscow; 2001. (In Russ.)
[4] Marchenkov S.S. Zamknutye klassy bulevyh funkcij [Closed Classes of Boolean Functions]. Fizmatlit, Moscow; 2000. (In Russ.)
[5] Yablonskiy S.V., Gavrilov G.P., Kudryavtsev V.B. Funkcii algebry logiki i klassy Posta [Logic Algebra Functions and Post Classes]. Nauka, Moscow; 1966. (In Russ.)
[6] Kudryavtsev V.B. O funkcional'nyh sistemah [On Functional Systems]. Computing Center of the Academy of Sciences of the USSR, Moscow; 1981. (In Russ.)
[7] Maltsev A.I. Iterativnye algebry Posta [Iterative Post Algebras]. Novosibirsk: NSU; 1976. (In Russ.)
[8] Yablonskii S.V. Functional constructions in a k-valued logic. Trudy Matematicheskogo Instituta imeni V.A. Steklova = Proceedings of the Steklov Institute of Mathematics. 1958; 51:5-142. (In Russ.)
[9] Lau D. Function Algebras on Finite Sets: A Basic Course on Many-Valued Logic and Clone Theory. Springer Monographs in Mathematics. Springer, Berlin, Heidelberg; 2006. (In Eng.) DOI: https://doi.org/10.1007/3-540-36023-9
[10] Panteleev V.I. The criteria of completeness for redefining Boolean function. Vestnik NSU. Series: Mathematics, Mechanics, Informatics. 2009; 9(3):95-114. Available at: https://elibrary.ru/item.asp?id=12916752 (accessed 03.08.2020). (In Russ., abstract in Eng.)
[11] Peryazev N.A., Sharankhaev I.K. Galois theory for clones and superclones. Discrete Mathematics and Applications. 2016; 26(4):227-238. (In Eng.) DOI: https://doi.org/10.1515/dma-2016-0020
[12] Peryazev N.A., Sharankhaev I.K. On some sufficient condition for the equality of multi-clone and super-clone. Journal of Siberian Federal University. Mathematics & Physics. 2018; 11(1):97-102. (In Eng.) DOI: https://doi.org/10.17516/1997-1397-2018-11-1-97-102
[13] Sharankhaev I. K. O metode dekompozicii mul'tifunkcij [On the method of decomposition of multifunctional functions]. In: V. B. Alekseev, D. S. Romanov, B. R. Danilov (ed.) Discrete models in the theory of control systems. MAKS Press, Moscow; 2015. p. 266-267. (In Russ.)
[14] Peryazev N.A. Standard forms of multioperations in superclones. The Bulletin of Irkutsk State University. Series Mathematics. 2010; 3(4):88-95. Available at: https://elibrary.ru/item.asp?id=15540118 (accessed 03.08.2020). (In Russ., abstract in Eng.)
[15] Peryazev N.A., Yakovjuk I.A. Minimisation of multioperations in a class standard forms. Bulletin of Irkutsk State University. Series Mathematics. 2009; 2(2):117-126. Available at: https://elibrary.ru/item.asp?id=15183533 (accessed 03.08.2020). (In Russ., abstract in Eng.)
[16] Kazimirov A.S. On complexity of standard forms for multifunctions. Bulletin of Irkutsk State University. Series Mathematics. 2017; 22:63-70. (In Russ., abstract in Eng.) DOI: https://doi.org/10.26516/1997-7670.2017.22.63
[17] Todikov S.I. Minimisation of multioperations in a class key standerd forms. Proceedings of Saint Petersburg Electrotechnical University. 2019; (5):53-58. Available at: https://elibrary.ru/item.asp?id=38247454 (accessed 03.08.2020). (In Russ., abstract in Eng.)
[18] Peryazev N.A. Galois theory for finite algebras of operations and multioperations of rank 2. Bulletin of Irkutsk State University. Series Mathematics. 2019; 28:113-122. (In Russ., abstract in Eng.) DOI: https://doi.org/10.26516/1997-7670.2019.28.113
[19] Peryazev N.A. Identities in fixed dimension algebras of multioperations. Bulletin of Irkutsk State University. Series Mathematics. 2019; 29:86-97. (In Russ., abstract in Eng.) DOI: https://doi.org/10.26516/1997-7670.2019.29.86
[20] Peryazev N.A., Sharankhaev I.K. Algebry mul'tioperacij [Algebras of Multioperations]. In: Pinus A.G., Poroshenko E.N., Sudoplatov S.V., Timoshenko E.I. (ed.) Algebra and Model Theory 11. Collection of papers. NSTU Publisher, Novosibirsk; 2017. p. 102-111. (In Russ.)
[21] Peryazev N.A. Algebras of n-ary Operations and Multioperations. In: XV International Conference on "Algebra, Number Theory and Discrete Geometry: Modern Problems and Applications". Tula State Pedagogical University, Tula; 2018. p. 113-116. (In Eng.)
[22] Peryazev N.A. Finite Algebras of Multioperations. In: XVI International Conference on "Algebras, Number Theory and Discrete Geometry: Modern Problems and Applications". TSPU; 2019. p. 51-54. (In Russ.)
[23] Eremenko D.A. Algebras of unary operations of rank 3. Proceedings of Saint Petersburg Electrotechnical University. 2019; (7):14-18. Available at: https://elibrary.ru/item.asp?id=42372860 (accessed 03.08.2020). (In Russ., abstract in Eng.)
[24] Eremenko D.A. Minimal Algebras of Binary Operations of Rank 3. Kompjuternye instrumenty v obrazovanii = Computer Tools in Education. 2020; (1):38-48. (In Russ., abstract in Eng.) DOI: https://doi.org/10.32603/2071-2340-2020-1-38-48
[25] Peryazev N.A. Clones, Co-Clones, Hyperсlones and Superсlones. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki. 2009; 151(2):120-125. Available at: https://elibrary.ru/item.asp?id=12833150 (accessed 03.08.2020). (In Russ., abstract in Eng.)
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
