Классификация представлений всех булевых функций от 4-х переменных в виде разделяющих поверхностей минимальной степени нелинейности
(Стр. 56-92)

В работе проведено классификационное исследование по построению представлений булевых функций от 4-х переменных в виде разделяющих поверхностей минимальной степени нелинейности. Для построения этих поверхностей использован адаптивный алгоритм эллипсоидов, основанный на алгоритме Хачияна решения систем линейных неравенств с целочисленными коэффициентами. Для задания булевых функций использовано их графическое представление на проекции четырехмерного куба. Проведенное классификационное исследование не было ограничено только поиском разделяющей поверхности минимальной степени нелинейности. Дополнительно была поставлена задача - найти поверхность с наименьшим числом ненулевых нелинейных членов в соответствии с заданным лексикографическим порядком. По результатам исследования построен каталог разделяющих поверхностей минимальной степени нелинейности с наименьшим числом нелинейных членов для булевых функций от 4-х переменных, а также определено что 15 классов функций геометрической эквивалентности имеют минимальную степень нелинейности 1, 166 - степень 2, 40 - степень 3, и 1 функция степень 4.

Лапиков И.И., Никонов В.Г., Касьяненко К.В., (2022), КЛАССИФИКАЦИЯ ПРЕДСТАВЛЕНИЙ ВСЕХ БУЛЕВЫХ ФУНКЦИЙ ОТ 4-Х ПЕРЕМЕННЫХ В ВИДЕ РАЗДЕЛЯЮЩИХ ПОВЕРХНОСТЕЙ МИНИМАЛЬНОЙ СТЕПЕНИ НЕЛИНЕЙНОСТИ. Computational nanotechnology, 1 => 56-92.

Балакин Г.В., Никонов В.Г. Методы сведения булевых уравнений к системам пороговых соотношений // Обозрение прикл. промышл. матем. 1994. Т. 1. № 3. C. 389-401.
Ivanescu P.L., Rudeanu S. Boolean methods in operator research and related areas. Berlin; Heidelberg; New York: Springer Verlag, 1968. 331 p.
Хачиян Л.Г. Полиномиальные алгоритмы в линейном программировании // ЖВМиМФ. 1980. Т. 20. № 1. С. 51-68.
Лапиков И.И. О возможности построения пространственно-декомпозиционного алгоритма на базе геометрического распараллеливания адаптивного алгоритма эллипсоидов // Computational Nanotechnology. 2018. № 1. С. 140-145.
Harisson M.A. Introduction to switching and automata theory. NY: McGraw-Hill, 1964. 499 p.
Ninomiya I. A study of the structures of Boolean functions and its application to the synthesis of switching circuits // Mem. Faculty Engineering, Nagoya Univ. 1961. Vol. 13. No. 2. Pp. 149-363.
Никонов В.Г. Классификация минимальных базисных представлений всех булевых функций от четырех переменных // Обозрение прикл. промышл. матем. 1994. Т. 1. № 3. С. 458-545.

булевы функции, алгоритм Хачияна, адаптивный алгоритм эллипсоидов, классификация булевых функций.