Алгоритм поиска минимальных алгебр бинарных мультиопераций ранга 3

  • Sergey Igorevich Todikov Санкт-Петербургский государственный электротехнический университет "ЛЭТИ" им. В.И. Ульянова (Ленина) http://orcid.org/0000-0002-1249-6838

Аннотация

В теории дискретных функций, помимо всюду определенных функций k-значной логики, изучаются и функции, определенные не на всех наборах. В этом случае неопределенность понимается по-разному, в зависимости от рассматриваемого класса задач. Если образ элемента является произвольным конечным подмножеством, то такие функции принято называть мультиоперациями.
Теория мультиопераций является достаточно новым направлением в математике, и ее развитие, в перспективе, может привести к разработке новых подходов в теоретической информатики, математической кибернетики и их приложений. Как и в любом новом направление, в теории мультиопераций имеется много открытых проблем. Для решения таких задач необходимо разрабатывать алгоритмы, которые способны работать с большим объемом данных, так как с увеличением параметров число мультиопераций экспоненциально растет.
Статья посвящена разработке алгоритма для поиска минимальных алгебр бинарных мультиопераций на трехэлементном множестве. Работа алгоритма основывается на двух этапах. Первый этап сделан для того, чтобы найти часть минимальных алгебр для второго этапа. Во втором этапе проверяются все алгебры на основе результата из первого этапа. С помощью такого подхода удалось обнаружить все минимальные алгебры, а также найти все минимальные алгебры с дополнительной метаоперацией объединения.

Сведения об авторе

Sergey Igorevich Todikov, Санкт-Петербургский государственный электротехнический университет "ЛЭТИ" им. В.И. Ульянова (Ленина)

аспирант кафедры вычислительной техники

Литература

[1] Post E.L. Two-Valued Iterative Systems of Mathematical Logic. Princeton-London: Princeton Univ. Press; 1941. (In Eng.) DOI: https://doi.org/10.2307/2268608
[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.)
Опубликована
2020-12-25
Как цитировать
TODIKOV, Sergey Igorevich. Алгоритм поиска минимальных алгебр бинарных мультиопераций ранга 3. Современные информационные технологии и ИТ-образование, [S.l.], v. 16, n. 4, p. 841-850, dec. 2020. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/668>. Дата доступа: 29 sep. 2022 doi: https://doi.org/10.25559/SITITO.16.202004.841-850.
Раздел
Теоретические вопросы информатики, прикладной математики, компьютерных наук