Алгоритм поиска минимальных алгебр бинарных мультиопераций ранга 3
Аннотация
В теории дискретных функций, помимо всюду определенных функций k-значной логики, изучаются и функции, определенные не на всех наборах. В этом случае неопределенность понимается по-разному, в зависимости от рассматриваемого класса задач. Если образ элемента является произвольным конечным подмножеством, то такие функции принято называть мультиоперациями.
Теория мультиопераций является достаточно новым направлением в математике, и ее развитие, в перспективе, может привести к разработке новых подходов в теоретической информатики, математической кибернетики и их приложений. Как и в любом новом направление, в теории мультиопераций имеется много открытых проблем. Для решения таких задач необходимо разрабатывать алгоритмы, которые способны работать с большим объемом данных, так как с увеличением параметров число мультиопераций экспоненциально растет.
Статья посвящена разработке алгоритма для поиска минимальных алгебр бинарных мультиопераций на трехэлементном множестве. Работа алгоритма основывается на двух этапах. Первый этап сделан для того, чтобы найти часть минимальных алгебр для второго этапа. Во втором этапе проверяются все алгебры на основе результата из первого этапа. С помощью такого подхода удалось обнаружить все минимальные алгебры, а также найти все минимальные алгебры с дополнительной метаоперацией объединения.
Литература
[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.)
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
