4-Variable Boolean Functions Representations Classification in the Form of Nonlinearity Minimal Degree Separating Surfaces

Full Text

Понятие разделяющей поверхности для булевой функции f(x1, … , xn) введено в работе [1] как равенство в действительной области вида a1x1 + ... + anxn + a12x1x2 + ... + aijxixj + ... + a1...nx1 ... xn = b, (1) где aν, b - целочисленные; xi = {0, 1} - булевы, такое что для всех векторов (x1, … , xn) = (ε1, … , εn), в которых функция f(ε1, … , εn) = 1, выполняется неравенство f(ε1, … , εn) = 1 ⇔ a1ε1 + ... + anεn + a12ε1ε2 + (2) + ... + aijεiεj + ... + a1...nε1 ... εn > b, а на всех наборах (x1, … , xn) = (δ1, … , δn), в которых f(δ1, … , δn) = 0, выполняется неравенство f(δ1, … , δn) = 0 ⇔ a1δ1 + ... + anδn + a12δ1δ2 + (3) + ... + aijδiδj + ... + a1...nδ1 ... δn ≤ b. Выражение (2) будем называть заданием единичных вершин, а выражение (3) заданием нулевых вершин булевой функции с помощью разделяющей поверхности. В работе [1] методы сведения булевых функций и уравнений к равносильным системам неравенств в действительной области названы псевдобулевыми, так как функции с булевыми переменными, принимающие значения в действительной области были названы псевдобулевыми в ранее опубликованных трудах [2]. Известно, что для любой булевой функции разделяющая поверхность всегда существует, более того, для конкретной булевой функции можно построить бесконечное количество разделяющих поверхностей [1]. В левой части выражения (1) стоит полином от переменных x1, … , xn P(x1, … , xn) = a1x1 + ... + anxn + a12x1x2 + (4) + ... + aijxixj + ... + a1...nx1 ... xn, в котором все слагаемые содержат переменные xi в степени не выше первой, так как для булевых переменных xi справедливо очевидное неравенство xi2 = xi. В связи с этим степень нелинейности полинома P(x1, … , xn) - deg P(x1, … , xn) - определяется как наибольшее количество умножающихся переменных в слагаемых представления (4) с ненулевыми коэффициентами. Если для функции f(x1, … , xn) существует разделяющая поверхность с полиномом P(x1, … , xn), степень нелинейности которого равна 1, то такая функция называется пороговой: f(x1, … , xn) = 1 ⇔ a1x1 + ... + anxn > b. (5) Изучению пороговых функций посвящено большое количество работ, составляющих вместе с рассмотрением приложений, самостоятельное направление дискретной математики - пороговую логику. Во многом пороговая логика стала основой для построения систем искусственного интеллекта и автоматизированного управления, базой для решения сложных трудно формализуемых задач. С геометрической точки зрения линейное неравенство (5) задает гиперплоскость, которая разделяет n-мерное пространство на два полупространства так, что единичные вершины функции f(x1, … , xn) лежат по одну сторону плоскости, а нулевые - по другую сторону (вершины, лежащие на самой плоскости относятся к нулевым). В силу этого плоскость, задаваемая неравенством (5), названа разделяющей. Функция действительного переменного, стоящая в левой части выражения (1), дифференцируемая, так как задается полиномом, вследствие чего можно констатировать, что выражение (1) определяет разделяющую поверхность так, что по одну сторону ее лежат единичные вершины (см. (2)), а по другую - нулевые вершины (см. (3)). В связи с этим задание булевой функции f(x1, … , xn) с помощью (1) можно назвать заданием f(x1, … , xn) с помощью разделяющей поверхности. Также как и разделяющая плоскость для пороговых функций, разделяющая поверхность для произвольной булевой функции определяется неоднозначно, причем разные представления для одной и той же функции могут иметь различные степени нелинейности задающего неравенство полинома. В то же время для любой булевой функции однозначно определяется параметр df - минимальная степень нелинейности задающего ее полинома в виде (1). Нахождению параметров df и построению разделяющих поверхностей степени df для всех булевых функций от 4-х переменных посвящена настоящая работа. Величина df для функции f(x1, … , xn) имеет не только теоретическое, но и практическое значение, определяя сложность вычислительных операций при задании функции f(x1, … , xn) в виде полиномиального равенства (1), которое можно назвать нелинейным пороговым степени df. Степень нелинейности df является объективной сложностной характеристикой задания (1), которая проявляет себя как в задачах синтеза, так и анализа булевых функций. Традиционные задачи синтеза булевых функций, как правило, связаны с представлением в каком-либо базисе: ДНФ, КНФ, штрихов Шеффера, многочленов Жегалкина и др. При этом применительно к любому конкретному базису все булевы функции делятся на сравнительно легкореализуемые и труднореализуемые. Задание булевых функций с помощью нелинейных пороговых неравенств дает еще один подход к их синтезу, причем с использованием простых арифметических команд, присутствующих практически во всех вычислительных средах. Представление булевых функций в виде неравенств пусть даже нелинейных, может оказаться крайне полезным и в задачах анализа самих булевых функций и при анализе порождаемых ими систем уравнений, так как в большинстве случаев использование традиционных базисов, как правило, крайне затруднительно. В то же время системы булевых уравнений, трансформированные в системы неравенств, могут изучаться, анализироваться и решаться с помощью естественных арифметических приемов, таких как формирование линейных комбинаций - следствий, привлечение алгоритмов дискретной оптимизации, бионических, эволюционных алгоритмов и др. Во всех этих приемах, как правило, чем меньше степень нелинейности разделяющей поверхности, тем выше их эффективность. Для построения разделяющей поверхности может быть использован полиномиальный алгоритм Л.Г. Хачияна [3]. Действительно, в общем виде желая найти разделяющую поверхность для функции f(x1, … , xn), можно в нелинейный полином P(x1, … , xn) (см. (4)) подставить сначала все единичные вершины функции f(x1, … , xn) и выписать неравенства (6) а затем - нулевые вершины в которых (7) Общая система, состоящая из подсистем (6) и (7) (8) является системой линейных неравенств относительно неизвестных коэффициентов разделяющей поверхности a1, … , a1…n, определяющих полином P(x1, … , xn). Система (8) будет системой c целыми коэффициентами и действительными неизвестными, поэтому для ее решения может быть применен полиномиальный алгоритм Л.Г. Хачияна [3]. Если положить в аналитическом представлении полинома P(x1, … , xn) равными нулю все коэффициенты при степенях строго больших некоторого значения d0 и с таким дополнительным условием составить систему (8), то окажется в случае ее совместности, что df ≤ d0, а в случае несовместности df > d0. Такой путь позволит после проведения определенного числа итераций точно определить значение df и найти разделяющую поверхность с такой степенью нелинейности. Известные трудности при таком подходе сопряжены с тем, что прямое применение алгоритма Хачияна может привести, а в большинстве случаев приводит, к нахождению не целочисленных коэффициентов, а дробных и, как показывает практика к значительному разбросу модулей максимальных и минимальных коэффициентов. В связи с этим, для решения задачи была применена модифицированная версия адаптивного алгоритма эллипсоидов, предложенного в работе [4]. В отличии от классического алгоритма Хачияна в адаптивном алгоритме введены дополнительные критерии выхода, т.е. условия завершения работы алгоритма, а также переоценена величина максимального количества итераций алгоритма: (9) где n - количество неизвестных системы (8); h - максимальный по модулю коэффициент СЛН; Mi - количество ненулевых коэффициентов i-го неравенства системы; N = max {Mi} ; m - число неравенств системы [4]. С целью поиска минимальных коэффициентов разделяющих поверхностей в качестве начальной области локализации решений выбран гипершар с центром в точке x0(0, 0, 0, 0) и радиусом R0. Эмпирически установлено, что для решаемых задач по построению разделяющих поверхностей для функций от 4-х переменных минимальным значением исходной области локализации решений, в которую укладываются коэффициенты разделяющих поверхностей является гипершар радиусом R0 = 10 в условиях решаемых задач. При этом значении были найдены разделяющие поверхности минимальных степеней для всех булевых функций от 4-х переменных. Вышеизложенные положения справедливы и для построения разделяющей поверхности булевой функции от произвольного числа переменных. В то же время конкретный и обозримый полигон для применения предложенных приемов представляют булевы функции от 4-х переменных. Наиболее известным классификационным исследованием булевых функций от 4-х переменных является Гарвардский каталог, перечисляющий по типам все булевы функции и содержащий информацию о мощности типов и оптимальных реализациях классифицируемых функций на конкретной элементной базе [5]. Другой каталог был составлен группой японских ученых по руководством профессора Ниномия [6]. В основе этого каталога, также как и Гарвардского, лежит задача построения оптимальной реализации каталогизируемой функции, но для реализации предлагается другая элементная база. Среди трудов отечественных ученых следует выделить исследование [7], в котором проведена классификация минимальных пороговых представлений всех булевых функций 4-х переменных. В этой работе был использован оригинальный и удобный для пользования каталогом принцип классификации функций на основе графов связности единичных вершин. Еще одним ее достоинством являются приведенные доказательства минимальности найденных пороговых представлений геометрическим способом с помощью так называемых систем существенных вершин. Именно этот каталог послужил основой для данного исследования. В каталоге [7] булевы функции от 4-х переменных сгруппированы в 402 типа на основе графов связности единичных вершин, которые образуют 222 класса геометрической эквивалентности. Напомним, что две функции f1(x1, … , xn) и f2(x1, … , xn) называются однотипными, если одна из них переводится в другую с помощью перестановки переменных и навешивания отрицания на некоторые переменные. Две функции f1(x1, … , xn) и f2(x1, … , xn) лежат в одном классе геометрической эквивалентности, если функция f1(x1, … , xn) однотипна функции f2(x1, … , xn) либо ее отрицанию f̅2(x1, … , xn). Принципиальное отличие классификаций минимальных систем разделяющих плоскостей и разделяющих поверхностей минимальной степени нелинейности заключается в том, что уравнения f(x1, … , xn) = 1 и f(x1, … , xn) = 0 приводят к двум различным системам линейных неравенств, в то время как нелинейная разделяющая поверхность для них одна и та же. Выбор 4-х переменных для построения классификации не случаен, так как при n = 4 еще можно провести полные классификационные исследования, представить их в удобном для опубликования виде, получить необходимые суммарные выводы. Действительно, при n = 4 существует 222 класса, геометрической эквивалентности, а при n = 5 их уже несколько десятков тысяч, что не позволяет дать полное обозримое описание изучаемых параметров для всех функций в виде традиционной научной публикации. В предлагаемом нами каталоге используется графическое задание булевых функций в виде геометрического представления на проекции четырехмерного куба (см. рис. 1). Каждой вершине соответствует определенная комбинация входных значений функции. Закрашенные вершины означают, что в точке (x1, x2, x3, x4) функция равна 1, если вершина не закрашена, то - 0. Рис. 1. Геометрическое представление булевой функции от 4-х переменных заданием вершин на проекции четырехмерного куба Fig. 1. 4-variables Boolean functions geometric representation by specifying vertices on the projection of a four-dimensional cube Проведенное классификационное исследование не было ограничено только поиском разделяющей поверхности минимальной степени нелинейности. Дополнительно была поставлена задача - найти поверхность с наименьшим числом ненулевых нелинейных членов. При построении таких поверхностей определен следующий лексикографический порядок весовых коэффициентов a1, … , a1234 a1 > a2 > a3 > a4 > a12 > a13 > a14 > a23 > (10) > a24 > a34 > a123 > a124 > a234 > a1234. Приведем в виде сводной таблицы (табл. 1) классификацию разделяющих поверхностей булевых функций от четырех переменных минимальной степени нелинейности. В столбцах таблицы представлены порядковый номер функции в нашем каталоге, номер в каталоге [7] по типу графа связности, графическое задание функции (см. рис. 1), минимальная степень разделяющей поверхности для данной функции и непосредственно само задание единичных вершин булевой функции с помощью разделяющей поверхности минимальной степени нелинейности с наименьшим числом нелинейных членов в соответствии с отношением порядка (10). Таблица 1 Каталог разделяющих поверхностей минимальной степени нелинейности с наименьшим числом нелинейных членов для булевых функций от 4-х переменных [Catalog of nonlinearity minimal degree separating surfaces with the smallest number of nonlinear terms for 4 variables Boolean functions] По результатам классификации удалось обнаружить что все простейшие непороговые функции, т.е. функции с пороговой структурой (2, 2), для которых либо уравнение f = 0, либо f = 1, задается двумя неравенствами, имеют разделяющую поверхность второй степени, т.е. обладают простейшим нелинейным представлением. Для всех функций с разделяющей поверхностью 3-й степени по крайней мере в одной минимальной системе линейных неравенств, равносильной или уравнению f(x1, x2, x3, x4) = 1, или f(x1, x2, x3, x4) = 0 содержится не менее 4-х неравенств, при этом общее число неравенств в этих двух системах больше или равно 7. Самая сложная для задания разделяющей поверхностью функция № 222 (8.8.1.1) обладает и самым сложным заданием с помощью систем линейных неравенств (8 неравенств для задания уравнения f(x1, x2, x3, x4) = 1 и f(x1, x2, x3, x4) = 0). Данный каталог можно рассматривать как важный источник для проведения последующих исследований как в области псевдобулевой тематики, так и шире - в целом при изучении свойств булевых функций.

About the authors

Igor I. Lapikov

MIREA - Russian Technological University

Email: lapikov.i.i@yandex.ru
Cand. Sci. (Eng.); аssociate professor at the Cybersecurity and Digital Technologies Institute of the Russian Technological Moscow, Russian Federation

Vladimir G. Nikonov

Russian Academy of Natural Sciences

Email: nikonovu@yandex.ru
Dr. Sci. (Eng.), Professor, Member at the Presidium of the Russian Academy of Natural Sciences Moscow, Russian Federation

Kristina V. Kasyanenko

S.M.Kirov Military Medical Academy

Email: dr.snegur@gmail.com
lecturer Saint-Petersburg, Russian Federation

References

Supplementary files