On the Connection between the Functional Systems of Polynomials and Arithmetic Polynomials Representing Systems of Boolean Functions
Abstract
The theory of functional systems is one of the basic fields of mathematical cybernetics. A functional system is a pair (P, O), in which P is the system carrier and O is the totality of operations specified in P. That is, a functional system is an algebra the elements of which are functions, and operations in this algebra correspond to the rules according to which the functions are constructed from each other. Functional systems involving a superposition operation (renaming and identifying the variables, and substituting functions for the variables of another function) are considered to be the conventional model objects of the theory. A functional system of polynomials with integer coefficients is investigated. The connection between a functional system of polynomials with integer coefficients and the arithmetic polynomials introduced by V.D. Malyugin to perform parallel logic computations is considered. Linear polynomials with integer coefficients are analyzed. The set of all such functions is denoted as L(Z) and is considered as a subset in the broader set P(Z) of functions represented by arbitrary-power polynomials with integer coefficients. Superposition (composition) operations are defined in L(Z) and P(Z). Arithmetic polynomials representing some systems of Boolean functions are given. It has been found that the set of arithmetic polynomials representing certain systems of Boolean functions do not coincide with P(Z). However, the closure with respect to the superposition operation of the set of arithmetic polynomials representing certain systems of Boolean functions coincides with P(Z). It is shown that the set of linear arithmetic polynomials representing some systems of Boolean functions does not coincide with L(Z). However, the closure with respect to the superposition operation of the set of linear arithmetic polynomials representing certain systems of Boolean functions coincides with L(Z).
References
2. Алексиадис Н.Ф. Функциональная система полиномов с натуральными коэффициентами // Вестник МЭИ. 2013. № 6. С. 125—140.
3. Алексиадис Н.Ф. Алгоритмическая неразрешимость проблемы полноты для полиномов с целыми коэффициентами // Вестник МЭИ. 2015. № 3. С. 110—117.
4. Малюгин В.Д. Параллельные логические вычисления поcредством арифметических полиномов. М.: Физматлит, 1997.
5. Finko O., Samoylenko D., Dichenko S., Eliseev N. Parallel Generator of Q-valued Pseudorandom Sequences Based on Arithmetic Polynomials // Przeglad Elektrotechniczny. 2015. V. 91. No. 3. Pp. 24—27.
6. Сизоненко А.Б. Параллельная реализация криптографических блоков подстановок и перестановок арифметическими полиномами // Доклады Томского гос. ун-та систем управления и радиоэлектроники. 2012. № 1—2 (26). С. 140—144.
7. Власов А.А., Мамаев Е.И. Расширенные арифметико-логические формы для реализации булевых функций // Труды науч. конф. по итогам науч.-исслед. работ Марийского гос. техн. ун-та. Йошкар-Ола, 2000. C. 100—107.
8. Мамонтов А.И., Мещанинов Д.Г. Алгоритм рас познавания полноты в функциональной системе L(Z) // Дискретная математика. 2014. Т. 26. № 1. C. 85—95.
9. Шмерко В.П. Теоремы Малюгина: новое понимание в логическом управлении, проектировании СБИС и структурах данных для новых технологий // Автоматика и телемеханика. 2004. № 6. C. 61—83.
10. Дзюжаньски П., Малюгин В., Шмерко В., Янушкевич С. Линейные модели схем на многозначных элементах // Автоматика и телемеханика. 2002. № 6. C. 99—119.
11. Финько О.А. Реализация систем булевых функций большой размерности методами модулярной арифметики // Автоматика и телемеханика. 2004. № 6. C. 37—60.
---
Для цитирования: Мамонтов А.И. О связи функциональных систем полиномов и арифметических полиномов, представляющих системы булевых функций // Вестник МЭИ. 2017. № 6. С. 161—165. DOI: 10.24160/1993-6982-2017-6-161-165.
#
1. Kudpyavtsev V.B. Funktsional'nye Sistemy. M.: Izd-vo MGU, 1982. (in Russian).
2. Aleksiadis N.F. Funktsional'naya Sistema Polinomov s Natural'nymi Koeffitsientami. Vestnik MPEI. 2013;6:125—140. (in Russian).
3. Aleksiadis N.F. Algoritmicheskaya Nerazreshimost' Problemy Polnoty dlya Polinomov s Tselymi Koeffitsientami. Vestnik MPEI. 2015;3:110—117. (in Russian).
4. Malyugin V.D. Parallel'nye Logicheskie Vychisleniya Pocredstvom Arifmeticheskih Polinomov. M.: Fizmatlit, 1997. (in Russian).
5. Finko O., Samoylenko D., Dichenko S., Eliseev N. Parallel Generator of Q-valued Pseudorandom Sequences Based on Arithmetic Polynomials. Przeglad Elektrotechniczny. 2015;91;3:24—27.
6. Sizonenko A.B. Parallel'naya Realizatsiya Kriptograficheskih Blokov Podstanovok i Perestanovok Arifmeticheskimi Polinomami. Doklady Tomskogo Gos. Un-ya Sistem Upravleniya i Radioelektroniki. 2012;1—2 (26):140—144.(in Russian).
7. Vlasov A.A., Mamaev E.I. Rasshirennye Arifmetiko-Logicheskie Formy dlya Realizatsii Bulevyh Funktsiy. Trudy Nauch. Konf. po Itogam Nauch.-issled. Rabot Mariyskogo Gos. Tekhn. Un-ya, Yoshkar-Ola, 2000:100—107. (in Russian).
8. Mamontov A.I., Meshchaninov D.G. Algoritm Raspoznavaniya Polnoty v Funktsional'noy Sisteme L(Z). Diskretnaya Matematika. 2014;26;1:85—95. (in Russian).
9. Shmerko V.P. Teoremy Malyugina: Novoe Ponimanie v Logicheskom Upravlenii, Proektirovanii SBIS i Strukturah Dannyh dlya Novyh Tekhnologiy. Avtomatika i telemekhanika. 2004;6:61—83.(in Russian).
10. Dzyuzhan'ski P., Malyugin V., Shmerko V., Yanushkevich S. Lineynye Modeli Skhem na Mnogo- znachnyh Elementah. Avtomatika i Telemekhanika. 2002;6:99—119. (in Russian).
11. Fin'ko O.A. Realizatsiya Sistem Bulevyh Funktsiy Bol'shoy Razmernosti Metodami Modulyarnoy Arifmetiki. Avtomatika i Telemekhanika. 2004;6:37—60. (in Russian).
---
For citation: Mamontov A.I. On the Connection between the Functional Systems of Polynomials and Arithmetic Polynomials Representing Systems of Boolean Functions. MPEI Vestnik. 2017; 6:161—165. (in Russian). DOI: 10.24160/1993-6982-2017-6-161-165.
