chebЧебышевский сборникChebyshevskii Sbornik2226-8383Tula State Lev Tolstoy Pedagogical University10.22405/2226-8383-2022-23-2-121-150cheb-1274Research ArticleСтатьиArticleО работах О. М. Касим-Заде в области теории сложности и теории многозначных логикOn the papers of O. M. Kasim-Zade in field of complexity theory and theory of multivalued logicsКочергинВадим ВасильевичKocherginVadim Vasil’evich

доктор физико-математических наук

doctor of physical and mathematical sciences

vvkoch@yandex.ruМосковский государственный университет имени М. В. ЛомоносоваРоссияLomonosov Moscow State UniversityRussian Federation202207072022232121150Copyright © Кочергин В.В., 20222022Кочергин В.В.Kochergin V.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.chebsbornik.ru/jour/article/view/1274

В работе предпринята попытка не только дать обзор результатов, полученных О. М. Касим–Заде, крупнейшим специалистом по дискретной математике и математической кибернетике, но и осознать его научное наследие в таких направлениях как исследование мер схемной сложности булевых функций, связанных с функционированием схем,проблематика неявной и параметрической выразимости в конечнозначных логиках, вопросы глубины и сложности булевых функций и функций многозначной логики в бесконечных базисах.

The paper is an attempt both to give an overview of the results of OM Kasim-Zade, the largest specialist in discrete mathematics and mathematical cybernetics, and to understand hisscientific legacy in fields such as research measures the circuit complexity of Boolean functions related to the operation of the circuits, the problems of implicit and parametric expressibilityin finite-valued logics, the questions of the depth and the complexity of Boolean functions and functions of multivalued logics in infinite bases.

схемная сложностьактивностьмощностьглубинабесконечный ба- зиснеявная выразимостьпараметрическая выразимость.circuits complexityactiyvitypowerdepthinfinite basisimplicit expressibility parametric expressibility.ReferencesАманжаев Г. Г. О замыкании ненулевого инвариантного класса Яблонского по операции отождествления переменных // Вестник МГУ. Математика. Механика. 1995. №3. С. 76–79.Amanzhaev, G. G. 1995, “On the closure of the nonzero invariant Yablonski˘ı class by the variable identification operation”, Moscow Univ. Math. Bull., vol. 50, no. 3, pp. 43–45.Вайнцвайг М. Н. О мощности схем из функциональных элементов // Доклады АН СССР. 1961. Т. 139, № 2. С. 320–323.Va˘ıncva˘ıg, M. N. 1961, “On the power of networks of functional elements”, Soviet Physics Dokl., vol. 6, pp. 545–547.Гилберт Э. Н. Теоретико-структурные свойства замыкающих переключательных функций // Кибернетический сборник. Вып. 1. М.: Изд-во иностанной литературы, 1960. C. 175–188.Gilbert, E. N. 1954, “Lattice Theoretic Properties of Frontal Switching Functions”, J. Math. Phys., vol. 33, no. 1, pp. 57–67.Горяшко А. П. Энергетические оценки сложности функционирования логических сетей // Известия АН СССР. Сер. техн. кибернетика. 1969. № 2. С. 86–95.Goryashko, A. P. 1969, “Energy bounds of complexity of functioning of logical networks”, Izvestiya AN SSSR. Ser. Tekhn. Kibernetika, no. 2, pp. 86–95.Горяшко А. П. Логические схемы и реальные ограничения. М.: Энергоиздат, 1982.Goryashko, A. P. 1982, Logicheskie skhemy i real’nye ogranicheniya [Logic Circuits and Real Restrictions], Moscow, Energoizdat.Данильченко А. Ф. О параметрической выразимости функций трехзначной логики // Алгебра и логика. 1977. Т. 16, № 4. С. 397–416.Danil’chenko, A. F. 1977, “On parametric expressibility of functions of three-valued logic”, Algebra i logika, vol. 16, no. 4, pp. 397–416.Дебрев Е. В. Об одной задаче комбинаторного поиска // Дискретная матемематика. 2002. Т. 14, № 3. С. 8–17.Debrev, E. B. 2002, “On a combinatorial search problem”, Discrete Math. Appl., vol. 12, no. 4, pp. 325–335.Дебрев Е. В. О различении графов из некоторых множеств посредством безусловных реберных тестов // Математические вопросы кибернетики. Вып. 11. М.: Наука, 2002. С. 177–192.Debrev, E. B. 2002, “On distinguishing graphs from certain families by unconditional edge tests”, Mat. Vopr. Kibern., vol. 11, pp. 177–192.Дебрев Е. В. О безусловных реберных тестах для некоторых семейств графов // Дискретный анализ и исследование операций. Сер. 1. 2003. Т. 10, № 4. С. 8–17.Debrev, E. B. 2003, “On unconditional edge tests for some families of graphs”, Diskretn. Anal. Issled. Oper. Ser. 1, vol. 10, no. 4, pp. 8–30.Ермакова Д. И. О сложности реализации системы констант 𝑃3 в некоторых базисах // Математические вопросы кибернетики. Вып. 17. М.: ФИЗМАТЛИТ, 2008. С. 137–158.Ermakova, D. I. 2008, “On the complexity of realization a system of constants of 𝑃3 in some bases”, Mat. Vopr. Kibern., vol. 17, pp. 137–158.Закиров Н. Р. О представлении произвольного алгебраического числа периодической ветвящейся цепной дробью // Математические вопросы кибернетики. Вып. 15. М.: ФИЗМАТ-ЛИТ, 2006. С. 65–78.Zakirov, N. R. 2006, “On representing an arbitrary algebraic number as a periodic branching continuous fraction”, Mat. Vopr. Kibern., vol. 15, pp. 65–78.Закиров Н. Р. О представлении алгебраических чисел периодическими ветвящимися цепными дробями // Вестник Московского университета. Серия 1. Математика. Механика.Zakirov, N. R. 2007, “On the representation of algebraic numbers by periodic branching continued fractions”, Moscow Univ. Math. Bull., vol. 62, no. 4, pp. 148–152.№ 4. C. 24–29.Alekseyev, V. M. (ed.) 1977, Izbrannye zadachi iz zhurnala «American Mathematical Monthly» [Favorites problems from the journal «American Mathematical Monthly»], Mir, Moscow.Избранные задачи из журнала «American Mathematical Monthly». M.: Мир, 1977.Karpova, N. A. 1970, “Some properties of Shannon functions”, Math. Notes, vol. 8, no. 5, pp. 843– 849.Карпова Н. А. О некоторых свойствах функций Шеннона // Матем. заметки. 1970. Т. 8, вып. 5. С. 663–674.Kochergin, A. V. 2011, “On the depth of functions of 𝑘-valued logic in infinite bases”, Moscow Univ. Math. Bull., vol. 66, no. 1, pp. 20–24.Кочергин А. В. О глубине функций 𝑘-значной логики в бесконечных базисах // Вестник Моск. ун-та. Сер. 1. Математика. Механика. 2011. № 1. С. 22–26.Kochergin, A. V. 2013, “Depth of functions of 𝑘-valued logic in finite bases”, Moscow Univ. Math. Bull., vol. 68, no. 1, pp. 77–79.Кочергин А. В. О глубине функций 𝑘-значной логики в конечных базисах // Вестник Московского университета. Сер. 1. Математика. Механика. 2013. № 1. С. 56–59.Kochergin, A. V. 2018, “On the depth of 𝑘-valued logic functions over arbitrary bases”, J. Math. Sci., vol. 233, no. 1, pp. 100–102.Кочергин А. В. О глубине функций 𝑘-значной логики над произвольными базисами // Фундамент. и прикл. матем. 2015. Т. 20, № 6. С. 155–158.Kochergin, V. V. & Mikhailovich, A. V. 2018, “On the complexity of multivalued logic functions over some infinite basis”, J. Appl. Ind. Math., vol. 12, pp. 40–58.Кочергин В. В., Михайлович А. В. О сложности функций многозначной логики в одном бесконечном базисе // Дискретный анализ и исследование операций. 2018. Т. 25, № 1. С. 42–74.Kochergin, V. V. & Mikhailovich, A. V. 2019, “Circuit complexity of k-valued logic functions in one infinite basis”, Comput. Math. and Mod., vol. 30, no. 1, pp. 13–25.Кочергин В. В., Михайлович А. В. О схемной сложности функций 𝑘-значной логики водном бесконечном базисе // Прикладная математика и информатика. 2018. № 58. С. 21–Kuz’min, V. A. 1976, “Bound of realization complexity of logic algebra functions by the simplest types of binary programs”, Metody diskretnogo analiza v teorii kodov i skhem, vol. 29, pp. 11–39.Kuznetsov, A. V. 1979, “On the means for detecting non-derivability or inexpressibility”, Logicheskij Vyvod, Nauka, Moscow, pp. 5–33.Kuznetsov, A. V. 1979, “On the means for detecting non-derivability or inexpressibility”, Logicheskij Vyvod, Nauka, Moscow, pp. 5–33.Кузьмин В. А. Оценка сложности реализации функций алгебры логики простейшими видами бинарных программ // Методы дискретного анализа в теории кодов и схем. Вып. 29. Новосибирск, 1976. С. 11–39.Kuznetsov, Yu. V. 1986, “On classes of Boolean functions which are invariant with respect to identification of variables”, Sov. Math., Dokl., vol. 34, pp. 339–344.Кузнецов А. В. О средствах для обнаружения невыводимости или невыразимости // Логический вывод. М.: Наука, 1979. С. 5–33.Kuznetsov, Yu. V. 1987, Issledovanie invariantnyh klassov, svyazannyh s funkcional’nymi sistemami [Study of invariant classes related to functional systems], Dissertation for the Degree of Candidate of Physical and Mathematical Sciences, MGU, Moscow.Кузнецов Ю. В. О классах булевых функций, инвариантных относительно отождествления переменных // Доклады АН СССР. 1986. Т. 290, № 4. C. 780–785.Lozhkin, S. A. 1976, “Asymptotic behavior of Shannon functions for the delays of schemes of functional elements”, Math. Notes, vol. 19, no. 6, pp. 548–555.Кузнецов Ю. В. Исследование инвариантных классов, связанных с функциональными системами. Диссертация на соискание ученой степени кандидата физико-математических наук. М.: МГУ, 1987.Lupanov, O. B. 1958, “A method of circuit synthesis”, Izvesitya VUZ, Radiofiz., vol. 1, pp. 120–140.Ложкин С. А. Асимптотическое поведение функций Шеннона для задержек схем из функциональных элементов // Матем. заметки. 1976. Т. 19, № 6. С. 939–951.Lupanov, O. B. 1963, “On the synthesis of some classes of control systems”, Probl. Kibern., vol. 10, pp. 63–97.Лупанов О. Б. Об одном методе синтеза схем // Изв. вузов. Сер. радиофизика. 1958. № 1. 120–140.Lupanov, O. B. 1973, “The synthesis of circuits from threshold elements”, Probl. Kibern., vol. 26, pp. 109–140.Лупанов О. Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики, вып. 10. М.: Физматгиз, 1963. C 63–97.Lupanov, O. B. 1984, Asimptoticheskie Ocenki Slozhnosti Upravlyayushchih Sistem [Asymptotic Estimates of Complexity of Control Systems], MSU, Moscow.Лупанов О. Б. О синтезе схем из пороговых элементов // Проблемы кибернетики, вып. 26. М.: Наука, 1973. C. 109–140.Lyapunov, A. A. 1958, “On logic circuits of programs”, Probl. Kibern., vol. 1, pp. 46–74.Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984.Markov, A. A. 1958, “On the inversion complexity of a system of functions”, J. ACM, vol. 5, no. 4, pp. 331–334.Ляпунов А. А. О логических схемах программ // Проблемы кибернетики, вып. 1. М.: Физматгиз, 1958. С. 46–74.Markov, A. A. 1963, “On the inversion complexity of systems of Boolean functions”, Sov. Math. Dokl., vol. 4, pp. 694–696.Марков А. А. Об инверсионной сложности систем функций // Докл. АН СССР. 1957. Т. 116. № 6. С. 917–919.Mikhailets, E. V. 2008, “A rank of implicit representations over a class of three-valued logic functions”, Moscow Univ. Math. Bull., vol. 63, no. 5, pp. 221–223.Марков А. А. Об инверсионной сложности систем булевых функций // Докл. АН СССР. 1963. Т150. № 3. С. 477–479.Nechiporuk, E. I. 1962, “On the complexity of circuits in some bases containing nontrivial elements with zero weights”, Probl. Kibern., vol. 8, pp. 123–160.Михайлец Е. В. О ранге неявных представлений над одним классом функций трехзначной логики // Вестник Московского университета. Сер. 1. Математика. Механика. 2008. № 5. С. 65–67.Nechiporuk, E. I. 1964, “On a synthesis of schemes of threshold elements”, Probl. Kibern., vol. 11, pp. 49–62.Нечипорук Э. И. О сложности схем в некоторых базисах, содержащих нетривиальные элементы с нулевыми весами // Проблемы кибернетики, вып. 8. М.: Физматгиз, 1962. C. 123–Orekhova, E. A. 2003, “On a criterion for implicit completeness in three-valued logic”, Mat. Vopr. Kibern., vol. 12, pp. 27–74.Orekhova, E. A. 2003, “A criterion for the implicit Sheffer property in three-valued logic”, Diskretn. Anal. Issled. Oper. Ser. 1 , vol. 10, no. 3, pp. 82–105.Orekhova, E. A. 2003, “A criterion for the implicit Sheffer property in three-valued logic”, Diskretn. Anal. Issled. Oper. Ser. 1 , vol. 10, no. 3, pp. 82–105.Нечипорук Э. И. О синтезе схем из пороговых элементов // Проблемы кибернетики, вып. 11. М.: Наука, 1964. С. 49–62.Podolskaya, O. V. 2013, “Lower estimates of circuit complexity in the basis of antichain functions”, Moscow Univ. Math. Bull., vol. 68, no. 2, pp. 98–103.Орехова Е. А. Об одном критерии неявной полноты в трехзначной логике // Математические вопросы кибернетики. Вып. 12. М.: Физматлит, 2003. С. 27–74.Podolskaya, O. V. 2016, “Circuit complexity of symmetric Boolean functions in antichain basis”, Discrete Math. Appl., vol. 26, no. 1, pp. 31–39.Орехова Е. А. О критерии неявной шефферовости в трёхзначной логике // Дискретный анализ и исследование операций. Серия 1. 2003. Т. 10, № 3. С. 82–105.Podolskaya, O. V. 2016, “On bounds of Shannon functions of circuit complexity in some infinite bases”, Proc. Academician O. B. Lupanov XII International Seminar “Discrete Mathematics andПодольская О. В. О нижних оценках сложности схем в базисе антицепных функций // Вестник Московского университета. Сер. 1. Математика. Механика. 2013. № 2. С. 17–23.its Applications“, pp. 150–152.Подольская О. В. Сложность реализации симметрических булевых функций схемами в базисе антицепных функций // Дискретная матемематика. 2015. Т. 27, № 3. С. 95–107.Proskuryakov, A. I. 2002, “On the complexity of the realization of some functions by networks of elements that perform analytic operations”, Mat. Vopr. Kibern., vol. 11, pp. 262–269.Подольская О. В. Об оценках функций Шеннона сложности схем в некоторых бесконечных базисах // Материалы XII Международного семинара «Дискретная математика и ее приложения» имени академика О. Б. Лупанова. М., 2016. C. 150–152.Sapozhenko, A. A. & Lozhkin, S. A. 1983, “Methods of logical design and evaluation of the complexity of circuits on complementary MOSFETs”, Mikroelektronika, vol. 12, no. 1, pp. 42– 47.Проскуряков А. И. О сложности реализации некоторых функций сетями из элементов, осуществляющих аналитические операции // Математические вопросы кибернетики. Вып. 11. М.: ФИЗМАТЛИТ, 2002. С. 262–269.Starostin, M. V., 2018, “Implicit precomplete classes and a criterion of implicit completeness in the three-valued logic”, Moscow Univ. Math. Bull., vol. 73, no. 2, pp. 82–84.Сапоженко А. А., Ложкин С. А. Методы логического проектирования и оценки сложности схем на дополняющих МОП-транзисторах // Микроэлектроника. 1983. Т. 12, вып. 1. С. 42–47.Starostin, M. V. 2021, “Implicit completeness criterion in three-valued logic in terms of maximal classes”. Available at: https://arxiv.org/abs/2103.16631Старостин М. В. Неявно предполные классы и критерий неявной полноты в трехзначной логике // Вестник МГУ. Серия 1. Математика. Механика. 2018. № ,2. С. 56–59.Yablonskiy, S. V. 1959, “On algorithmic difficulties in the synthesis of minimal contact circuits”, Probl. Kibern., vol. 2, pp. 75–121.Старостин М. В. Критерий неявной полноты в трехзначной логике в терминах предполных классов [Электронный ресурс] // arXiv.org. URL: https://arxiv.org/abs/2103.16631 (дата обращения: 30.03.2021)Yablonskiy, S. V., Gavrilov G.P. & Kudryavcev V. B. 1966, Funkcii Algebry Logiki i Klassy Posta [Logic Algebra Functions and Post Classes], Nauka, Moscow.Яблонский С. В. Об алгоритмических трудностях синтеза минимальных контактных схем // Проблемы кибернетики, вып. 2. М.: Наука, 1959. С. 75–121.Yaglom, I. M. 1968, Kak razrezat’ kvadrat? [How to cut a square?], Nauka, Moscow.Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. М.: Наука, 1966.Yashunsky, A. D. 2007, “Asymptotics of the probability of values of random Boolean expressions”, J. Appl. Industr. Math., vol. 1, no. 4, pp. 509–531.Яглом И. М. Как разрезать квадрат? М.: Наука, 1968.Yashunsky, A. D. 2019, “Polynomial transformations of random variables on finite sets”, Math. Notes, vol. 106, no. 6, pp. 1025–1027.49. Yashunsky, A. D. 2020, “On necessary conditions of probability limit theorems in finite algebras”,Яшунский А. Д. Об асимптотике вероятности значений случайных булевых выражений // Дискретный анализ и исследование операций. 2006, Т. 13, № 2. 59–99.Doklady Mathematics, vol. 102, no. 1, pp. 301–303.Яшунский А. Д. Полиномиальные преобразования случайных величин на конечных множествах // Матем. заметки. 2019. Т. 106, № 6. С. 951–954.Yashunsky, A. D. 2021, Issledovaniya po teorii iterativnyh sistem, porozhdaemyh konechnymi sluchajnymi velichinami. Arifmeticheskij i kombinatorno-logicheskij podhod [Research on the theory of iterative systems generated by finite random variables. Arithmetic and combinatoriallogical approach], Dissertation for the degree of doctor of physical and mathematical sciences. Available at: https://istina.msu.ru/dissertations/364891994/Яшунский А.Д. О необходимых условиях предельных вероятностных теорем в конечных алгебрах // Доклады Российской академии наук. Математика, информатика, процессы управления. 2020. Т. 493, № 1. С. 47–50.Burks, A. W. &Wright, J. B. 1953, “Theory of logical nets”, Proc. IRE., vol. 41, no. 10, pp. 1357–1365.Яшунский А. Д. Исследования по теории итеративных систем, порождаемых конечными случайными величинами. Арифметический и комбинаторно-логический подход. Диссертация на соискание ученой степени доктора физико-математических наук. М., 2021. (URL:Вuггis, S. & Willагd, R. 1987, “Finitely many primitive positive clones”, Proc. of the American Mathematical Society, vol. 101, no. 3, pp. 427–430.https://istina.msu.ru/dissertations/364891994/)Lee, C. Y. 1959, “Representation of switching circuits by binary-decision programs”, Bell System Technical Journal, vol. 38, no. 4, pp. 985–1000.Burks A. W.,Wright J. B. Theory of logical nets // Proc. IRE. 1953. V. 41, № 10. P. 1357–1365.Muller, D. E. 1958, “Complexity in electronic switching circuits”, RE Trans. on Electronic Computers, vol. EC-5, no. 1, pp. 15–19.Вuггis S., Willагd R. Finitely many primitive positive clones // Proc. of the American Mathematical Society. 1987. V. 101, № 3. P. 427–430.Shannоn, C. E. 1941, “Mathematical theory of the differential analyzer”, J. Math, and Phys., vol. 20, no. 4, pp. 337–354.Lee C. Y. Representation of switching circuits by binary-decision programs // Bell System Technical Journal. 1959. V. 38, № 4. P. 985–1000.Shepherdson, J. & Sturgis, H. 1963, “Computability of recursive functions”, Journal of the Association for Computer Machinery, vol. 10, no. 2, pp. 217–255.Muller D. E. Complexity in electronic switching circuits // IRE Trans. on Electronic Computers. 1958. V. EC-5, N 1. P. 15–19.Yashunskiy, A. D. 2019, “Clone-induced approximation algebras of Bernoulli distributions”, Algebra Univers., vol. 80, no. 5.Shannоn C. E. Mathematical theory of the differential analyzer // J. Math, and Phys. 1941. V. 20, № 4. P. 337–354.Shannоn C. E. Mathematical theory of the differential analyzer // J. Math, and Phys. 1941. V. 20, № 4. P. 337–354.Shepherdson J., Sturgis H. Computability of recursive functions // Journal of the Association for Computer Machinery. 1963. V. 10, № 2. P. 217–255.Shepherdson J., Sturgis H. Computability of recursive functions // Journal of the Association for Computer Machinery. 1963. V. 10, № 2. P. 217–255.Yashunsky A. D. Clone-induced approximation algebras of Bernoulli distributions. Algebra Univers. 2019. V. 80, № 5.Yashunsky A. D. Clone-induced approximation algebras of Bernoulli distributions. Algebra Univers. 2019. V. 80, № 5.

The authors declare that there are no conflicts of interest present.