Минимизация функций алгебры логики при различных их представлениях востребована при логическом проектировании цифровых устройств. Среди других представлений рассматриваются полиномиальные формы. Полиномиальной формой называется выражение, являющееся суммой по модулю два произведений сомножителей определенного вида. Можно выделить такие классы полиномиальных форм, как поляризованные полиномиальные, полиномиальные нормальные, псевдополиномиальные и др. В ряде работ разработаны алгоритмы минимизации и получены оценки длины функций в этих классах полиномиальных форм. При этом исследования ведутся в нескольких направлениях, в частности, получение оценок длины самых сложных функций n переменных для произвольных n и нахождение точной длины функций малого числа переменных.

Настоящая работа посвящена нахождению точной длины функций малого числа переменных. В ней рассматриваются псевдополиномиальные формы для функций алгебры логики. Под псевдополиномиальной формой (ПСПФ), или псевдополиномом, понимается выражение, являющееся суммой по модулю двух произведений линейных функций. Длиной ПСПФ называется число ее слагаемых; длиной функции алгебры логики в классе ПСПФ — наименьшая длина среди всех ПСПФ, представляющих эту функцию. В работе получена полная классификация по длине в классе ПСПФ функций, зависящих от четырех переменных. Для функций, зависящих от пяти переменных, найдена наибольшая и средняя длина в классе ПСПФ.

Селезнева Светлана Николаевна, д-р физ.-мат. наук, проф., факультет вычислительной математики и кибернетики, Московский государственный университет им. М. В. Ломоносова, Российская Федерация, 119991, г. Москва, Ленинские горы, 1, стр. 52, тел.: (495)9395392, email: selezn@cs.msu.ru

Лобанов Алексей Андреевич, студент, факультет вычислительной математики и кибернетики, Московский государственный университет им. М. В. Ломоносова, Российская Федерация, 119991, г. Москва, Ленинские горы, 1, стр. 52, тел.: (495)9395392, email: alex_cmc@likemath.ru

Selezneva S.N., Lobanov A.A. On Length of Boolean Functions of a Small Number of Variables in the Class of Pseudo-Polynomials // Известия Иркутского государственного университета. Серия Математика. 2020. Т. 33. С. 96-105. https://doi.org/10.26516/1997-7670.2020.33.96

1. Baliuk A. S. Complexity lower bound for Boolean functions in the class of extended operator forms // Известия Иркутского государственного университета. Серия Математика. 2019. Т. 30. С. 125–140. https://doi.org/10.26516/1997-7670.2019.30.125
2. New three-level Boolean expression based on EXOR gates / R. Ishikawa, T. Hirayama, G. Koda, K. Shimizu // IEICE Trans. Inf. & Syst. 2004. Vol. E87-D, N 5. P. 1214–1222.
3. Кириченко К. Д. Верхняя оценка сложности полиномиальных нормальных форм булевых функций // Дискретная математика. 2005. Т. 17, вып. 3. С. 80–88. https://doi.org/10.1515/156939205774464891
4. Распределенная система и алгоритмы поиска минимальных и близких к ним контактных схем для булевых функций от малого числа переменных / С. А. Ложкин, М. С. Шуплецов, В. А. Коноводов, Б. Р. Данилов, В. В. Жуков, Н.Ю. Багров // Сборник трудов Всероссийских научно-технических конференций «Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС)». 2016. Т. 1. С. 40–47.
5. Перязев Н. А. Сложность булевых функций в классе полиномиальных поляризованных форм // Алгебра и логика. 1995. Т. 34, вып. 3. С. 323–326. https://doi.org/10.1007/BF02341875
6. Sasao T., Besslich P. On the complexity of mod-2 sum PLA’s // IEEE Trans. on Comput. 1990. Vol. 39, N 2. P. 262–266.
7. Селезнева С. Н. О длине булевых функций в классе полиномиальных форм с аффинными множителями в слагаемых // Вестник Московского университета. Серия 15, Вычислительная математика и кибернетика. 2014. Вып. 2. С. 34–38. https://doi.org/10.3103/S0278641914020083
8. Селезнева С. Н. Порядок длины функций алгебры логики в классе псевдополиномиальных форм // Вестник Московского университета. Серия 15, Вычислительная математика и кибернетика. 2016. Вып. 3. С. 27–31. https://doi.org/10.3103/S0278641916030043
9. Супрун В. П. Сложность булевых функций в классе канонических поляризованных полиномов // Дискретная математика. 1993. Т. 5, вып. 2. С. 111–115.
10. Угрюмов Е. П. Цифровая схемотехника. СПб. : БХВ-Петербург, 2004. 528 с.
11. Винокуров С. Ф., Казимиров А. С. О сложности одного класса булевых функций // Известия Иркутского государственного университета. Серия Математика. 2010. Т. 3, вып. 4. С. 2–6.
12. Яблонский С. В. Введение в дискретную математику. М. : Высшая школа, 2001. 384 с.