О связи функциональных систем полиномов и арифметических полиномов, представляющих системы булевых функций

  • Андрей [Andrey] Игоревич [I.] Мамонтов [Mamontov]
Ключевые слова: функциональная система полиномов, арифметический полином, параллельные логические вычисления

Аннотация

Одной из основных областей математической кибернетики является теория функциональных систем. Функциональная система представляет собой пару (P, O), в которой P — носитель системы, а O — совокупность операций, заданных на P, т. е. функциональная система — это алгебра, элементами которой являются функции, а операции в этой алгебре соответствуют правилам построения функций друг из друга. Традиционными модельными объектами теории считаются функциональные системы с операцией суперпозиции (переименование и отождествление переменных, подстановка функций на места переменных другой функции). Исследована функциональная система полиномов с целыми коэффициентами. Рассмотрена связь функциональной системы полиномов с целыми коэффициентами с введенными В.Д. Малюгиным для выполнения параллельных логических вычислений арифметическими полиномами. Проанализированы линейные полиномы с целыми коэффициентами. Множество всех таких функций обозначено L(Z) и рассмотрено как подмножество в более обширном множестве P(Z) функций, представленных полиномами произвольной степени с целыми коэффициентами. На L(Z) и P(Z) заданы операции суперпозиции. Приведены арифметические полиномы, представляющие некоторые системы булевых функций. Установлено, что множество арифметических полиномов, представляющих некоторые системы булевых функций, не совпадают с P(Z), однако замыкание относительно операции суперпозиции множества арифметических полиномов, представляющих некоторые системы булевых функций, с P(Z) совпадает. Показано, что множество линейных арифметических полиномов, представляющих некоторые системы булевых функций, не совпадают с L(Z), однако замыкание относительно операции суперпозиции множества линейных арифметических полиномов, представляющих некоторые системы булевых функций, совпадает с L(Z).

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

Андрей [Andrey] Игоревич [I.] Мамонтов [Mamontov]

Учёная степень:

кандидат технических наук

Место работы

кафедра Математического моделирования НИУ «МЭИ»

Должность

доцент

Литература

1. Кудpявцев В.Б. Функциональные системы. М.: Изд-во МГУ, 1982.

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.
Опубликован
2019-01-21
Раздел
Информатика, вычислительная техника и управление (05.13.00)