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

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

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