О работах О. М. Касим-Заде в области теории сложности и теории многозначных логик
https://doi.org/10.22405/2226-8383-2022-23-2-121-150
Аннотация
В работе предпринята попытка не только дать обзор результатов, полученных О. М. Касим–Заде, крупнейшим специалистом по дискретной математике и математической кибернетике, но и осознать его научное наследие в таких направлениях как исследование мер схемной сложности булевых функций, связанных с функционированием схем,
проблематика неявной и параметрической выразимости в конечнозначных логиках, вопросы глубины и сложности булевых функций и функций многозначной логики в бесконечных базисах.
Ключевые слова
схемная сложность,
активность,
мощность,
глубина,
бесконечный ба- зис,
неявная выразимость,
параметрическая выразимость.
Об авторе
Вадим Васильевич Кочергин
Московский государственный университет имени М. В. Ломоносова
Россия
Россия
доктор физико-математических наук
Список литературы
1. Аманжаев Г. Г. О замыкании ненулевого инвариантного класса Яблонского по операции отождествления переменных // Вестник МГУ. Математика. Механика. 1995. №3. С. 76–79.
2. Вайнцвайг М. Н. О мощности схем из функциональных элементов // Доклады АН СССР. 1961. Т. 139, № 2. С. 320–323.
3. Гилберт Э. Н. Теоретико-структурные свойства замыкающих переключательных функций // Кибернетический сборник. Вып. 1. М.: Изд-во иностанной литературы, 1960. C. 175–188.
4. Горяшко А. П. Энергетические оценки сложности функционирования логических сетей // Известия АН СССР. Сер. техн. кибернетика. 1969. № 2. С. 86–95.
5. Горяшко А. П. Логические схемы и реальные ограничения. М.: Энергоиздат, 1982.
6. Данильченко А. Ф. О параметрической выразимости функций трехзначной логики // Алгебра и логика. 1977. Т. 16, № 4. С. 397–416.
7. Дебрев Е. В. Об одной задаче комбинаторного поиска // Дискретная матемематика. 2002. Т. 14, № 3. С. 8–17.
8. Дебрев Е. В. О различении графов из некоторых множеств посредством безусловных реберных тестов // Математические вопросы кибернетики. Вып. 11. М.: Наука, 2002. С. 177–192.
9. Дебрев Е. В. О безусловных реберных тестах для некоторых семейств графов // Дискретный анализ и исследование операций. Сер. 1. 2003. Т. 10, № 4. С. 8–17.
10. Ермакова Д. И. О сложности реализации системы констант 𝑃3 в некоторых базисах // Математические вопросы кибернетики. Вып. 17. М.: ФИЗМАТЛИТ, 2008. С. 137–158.
11. Закиров Н. Р. О представлении произвольного алгебраического числа периодической ветвящейся цепной дробью // Математические вопросы кибернетики. Вып. 15. М.: ФИЗМАТ-ЛИТ, 2006. С. 65–78.
12. Закиров Н. Р. О представлении алгебраических чисел периодическими ветвящимися цепными дробями // Вестник Московского университета. Серия 1. Математика. Механика.
13. № 4. C. 24–29.
14. Избранные задачи из журнала «American Mathematical Monthly». M.: Мир, 1977.
15. Карпова Н. А. О некоторых свойствах функций Шеннона // Матем. заметки. 1970. Т. 8, вып. 5. С. 663–674.
16. Кочергин А. В. О глубине функций 𝑘-значной логики в бесконечных базисах // Вестник Моск. ун-та. Сер. 1. Математика. Механика. 2011. № 1. С. 22–26.
17. Кочергин А. В. О глубине функций 𝑘-значной логики в конечных базисах // Вестник Московского университета. Сер. 1. Математика. Механика. 2013. № 1. С. 56–59.
18. Кочергин А. В. О глубине функций 𝑘-значной логики над произвольными базисами // Фундамент. и прикл. матем. 2015. Т. 20, № 6. С. 155–158.
19. Кочергин В. В., Михайлович А. В. О сложности функций многозначной логики в одном бесконечном базисе // Дискретный анализ и исследование операций. 2018. Т. 25, № 1. С. 42–74.
20. Кочергин В. В., Михайлович А. В. О схемной сложности функций 𝑘-значной логики водном бесконечном базисе // Прикладная математика и информатика. 2018. № 58. С. 21–
21.
22. Кузьмин В. А. Оценка сложности реализации функций алгебры логики простейшими видами бинарных программ // Методы дискретного анализа в теории кодов и схем. Вып. 29. Новосибирск, 1976. С. 11–39.
23. Кузнецов А. В. О средствах для обнаружения невыводимости или невыразимости // Логический вывод. М.: Наука, 1979. С. 5–33.
24. Кузнецов Ю. В. О классах булевых функций, инвариантных относительно отождествления переменных // Доклады АН СССР. 1986. Т. 290, № 4. C. 780–785.
25. Кузнецов Ю. В. Исследование инвариантных классов, связанных с функциональными системами. Диссертация на соискание ученой степени кандидата физико-математических наук. М.: МГУ, 1987.
26. Ложкин С. А. Асимптотическое поведение функций Шеннона для задержек схем из функциональных элементов // Матем. заметки. 1976. Т. 19, № 6. С. 939–951.
27. Лупанов О. Б. Об одном методе синтеза схем // Изв. вузов. Сер. радиофизика. 1958. № 1. 120–140.
28. Лупанов О. Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики, вып. 10. М.: Физматгиз, 1963. C 63–97.
29. Лупанов О. Б. О синтезе схем из пороговых элементов // Проблемы кибернетики, вып. 26. М.: Наука, 1973. C. 109–140.
30. Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984.
31. Ляпунов А. А. О логических схемах программ // Проблемы кибернетики, вып. 1. М.: Физматгиз, 1958. С. 46–74.
32. Марков А. А. Об инверсионной сложности систем функций // Докл. АН СССР. 1957. Т. 116. № 6. С. 917–919.
33. Марков А. А. Об инверсионной сложности систем булевых функций // Докл. АН СССР. 1963. Т150. № 3. С. 477–479.
34. Михайлец Е. В. О ранге неявных представлений над одним классом функций трехзначной логики // Вестник Московского университета. Сер. 1. Математика. Механика. 2008. № 5. С. 65–67.
35. Нечипорук Э. И. О сложности схем в некоторых базисах, содержащих нетривиальные элементы с нулевыми весами // Проблемы кибернетики, вып. 8. М.: Физматгиз, 1962. C. 123–
36.
37. Нечипорук Э. И. О синтезе схем из пороговых элементов // Проблемы кибернетики, вып. 11. М.: Наука, 1964. С. 49–62.
38. Орехова Е. А. Об одном критерии неявной полноты в трехзначной логике // Математические вопросы кибернетики. Вып. 12. М.: Физматлит, 2003. С. 27–74.
39. Орехова Е. А. О критерии неявной шефферовости в трёхзначной логике // Дискретный анализ и исследование операций. Серия 1. 2003. Т. 10, № 3. С. 82–105.
40. Подольская О. В. О нижних оценках сложности схем в базисе антицепных функций // Вестник Московского университета. Сер. 1. Математика. Механика. 2013. № 2. С. 17–23.
41. Подольская О. В. Сложность реализации симметрических булевых функций схемами в базисе антицепных функций // Дискретная матемематика. 2015. Т. 27, № 3. С. 95–107.
42. Подольская О. В. Об оценках функций Шеннона сложности схем в некоторых бесконечных базисах // Материалы XII Международного семинара «Дискретная математика и ее приложения» имени академика О. Б. Лупанова. М., 2016. C. 150–152.
43. Проскуряков А. И. О сложности реализации некоторых функций сетями из элементов, осуществляющих аналитические операции // Математические вопросы кибернетики. Вып. 11. М.: ФИЗМАТЛИТ, 2002. С. 262–269.
44. Сапоженко А. А., Ложкин С. А. Методы логического проектирования и оценки сложности схем на дополняющих МОП-транзисторах // Микроэлектроника. 1983. Т. 12, вып. 1. С. 42–47.
45. Старостин М. В. Неявно предполные классы и критерий неявной полноты в трехзначной логике // Вестник МГУ. Серия 1. Математика. Механика. 2018. № ,2. С. 56–59.
46. Старостин М. В. Критерий неявной полноты в трехзначной логике в терминах предполных классов [Электронный ресурс] // arXiv.org. URL: https://arxiv.org/abs/2103.16631 (дата обращения: 30.03.2021)
47. Яблонский С. В. Об алгоритмических трудностях синтеза минимальных контактных схем // Проблемы кибернетики, вып. 2. М.: Наука, 1959. С. 75–121.
48. Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. М.: Наука, 1966.
49. Яглом И. М. Как разрезать квадрат? М.: Наука, 1968.
50. Яшунский А. Д. Об асимптотике вероятности значений случайных булевых выражений // Дискретный анализ и исследование операций. 2006, Т. 13, № 2. 59–99.
51. Яшунский А. Д. Полиномиальные преобразования случайных величин на конечных множествах // Матем. заметки. 2019. Т. 106, № 6. С. 951–954.
52. Яшунский А.Д. О необходимых условиях предельных вероятностных теорем в конечных алгебрах // Доклады Российской академии наук. Математика, информатика, процессы управления. 2020. Т. 493, № 1. С. 47–50.
53. Яшунский А. Д. Исследования по теории итеративных систем, порождаемых конечными случайными величинами. Арифметический и комбинаторно-логический подход. Диссертация на соискание ученой степени доктора физико-математических наук. М., 2021. (URL:
54. https://istina.msu.ru/dissertations/364891994/)
55. Burks A. W.,Wright J. B. Theory of logical nets // Proc. IRE. 1953. V. 41, № 10. P. 1357–1365.
56. Вuггis S., Willагd R. Finitely many primitive positive clones // Proc. of the American Mathematical Society. 1987. V. 101, № 3. P. 427–430.
57. Lee C. Y. Representation of switching circuits by binary-decision programs // Bell System Technical Journal. 1959. V. 38, № 4. P. 985–1000.
58. Muller D. E. Complexity in electronic switching circuits // IRE Trans. on Electronic Computers. 1958. V. EC-5, N 1. P. 15–19.
59. Shannоn C. E. Mathematical theory of the differential analyzer // J. Math, and Phys. 1941. V. 20, № 4. P. 337–354.
60. Shepherdson J., Sturgis H. Computability of recursive functions // Journal of the Association for Computer Machinery. 1963. V. 10, № 2. P. 217–255.
61. Yashunsky A. D. Clone-induced approximation algebras of Bernoulli distributions. Algebra Univers. 2019. V. 80, № 5.
Рецензия
Для цитирования:
Кочергин В.В. О работах О. М. Касим-Заде в области теории сложности и теории многозначных логик. Чебышевский сборник. 2022;23(2):121-150. https://doi.org/10.22405/2226-8383-2022-23-2-121-150
For citation:
Kochergin V.V. On the papers of O. M. Kasim-Zade in field of complexity theory and theory of multivalued logics. Chebyshevskii Sbornik. 2022;23(2):121-150. (In Russ.) https://doi.org/10.22405/2226-8383-2022-23-2-121-150
Просмотров:
313
Послать статью по эл. почте 