Задача сравнения базисов относится к проблематике сложности булевых функций при реализации их формулами (суперпозициями) в различных базисах. Базисом мы называем произвольную конечную полную систему булевых функций. Например, базисами являются множества Б₀={&,V,Ш}, Б₁={&,V,Ш,Е}, Б₀ И T, где T - конечное множество булевых функций, P₂(n) при n>1 - множество всех булевых функций от n аргументов.

Пусть Б - произвольный базис. Определим класс формул в базисе Б. Формулы в базисе Б - это выражения в алфавите, состоящем из функциональных символов (соответствующих функциям из базиса Б), переменных из счетного множества {x₁,x₂,...}, и символов "левая круглая скобка", "правая круглая скобка" и "запятая". Формулами в базисе Б являются выражения следующего и только следующего вида:

1) c, где c - символ константы, принадлежащей базису Б;

2) f(F₁,...,F_n), где f - символ функции от n аргументов, принадлежащей базису Б, а каждое из выражений F₁,...,F_n является либо формулой в базисе Б, либо переменной из множества {x₁,x₂,...}.

Например, выражение Ъ (&(x₁,Ш (x₂)),&(x₂,Ш (x₁))) является формулой в базисе Б₀, а также в любом базисе вида Б₀ И T, но не является формулой в базисе {&,Ш }. Данная формула реализует функцию x₁Еx₂.

Сложностью формулы F назовем число вхождений в формулу F символов переменных. Например, сложность формулы Ъ (&(x₁,Ш (x₂)),&(x₂,Ш (x₁))) равна четырем. В то же время, сложность формулы Е (x₁,x₂), реализующей ту же функцию x₁ Е x₂, но в другом базисе - Б₁, равна двум. Сложностью булевой функции f в базисе Б называется наименьшая из сложностей формул в базисе Б, которые реализуют функцию f. Можно показать, что сложность функции x₁ Еx₂ в базисе Б₀ равна четырем, а в базисе Б₁ равна двум, т. е. выписанные выше формулы являются минимальными по сложности.

Мы видим, что одна и та же функция в разных базисах может иметь разную сложность. Вопрос состоит в следующем: во сколько раз может измениться сложность функции при переходе от одного базиса к другому. Будет ли это отношение ограничено сверху некоторой константой, зависящей от пары базисов, или же будет неограниченным? Как показал О.Б.Лупанов в [1], сложность почти всех булевых функций асимптотически не зависит от базиса. В то же время, как показала Б.А.Субботовская в [2], существует последовательность функций, сложность которой в одном базисе строго больше по порядку, чем ее сложность в другом базисе. А именно, рассмотрим последовательность линейных функций f_n=x₁ Е x₂Е ...Е x_n. Очевидно, что сложность функции f_n в базисе Б₁ равна n. В то же время в [2] доказано, что сложность функции f_n в базисе Б₀ по порядку не меньше, чем n^1.5, что строго больше по порядку, чем n.

В начале 1960-х годов, в связи с этим результатом Б.А.Субботовской, О.Б.Лупанов поставил перед ней задачу сравнения базисов в общем виде. На множестве базисов введем отношение частичного порядка. Скажем, что базис Б предшествует (или не хуже) базиса Б', если отношение сложности произвольной функции в базисе Б к сложности этой же функции в базисе Б' не больше некоторой константы, зависящей только от базисов Б и Б'. Задача сравнения базисов "в узком смысле" состоит в следующем: для произвольной пары базисов Б и Б' определить, предшествует ли базис Б базису Б', или нет. Из результата Б.А.Субботовской следует, что базис Б₀ не предшествует базису Б₁. Скажем, что базисы Б и Б' эквивалентны, если они предшествуют друг другу. Таким образом, базисы Б₀ и Б₁ неэквивалентны, что показывает нетривиальность отношения предшествования. Задача сравнения базисов "в широком смысле" состоит в описании структуры базисов (т. е. структуры отношения предшествования) с точностью до эквивалентности.

Сам О.Б.Лупанов получил несколько результатов в этой области (они сформулированы в [3]). Во-первых, он дал признак сравнения базисов, т. е. сформулировал условие, накладываемое на пару базисов Б и Б', при выполнении которого базис Б предшествует базису Б'. Сформулируем этот признак. Формула называется бесповторной, если каждая существенная переменная входит в нее ровно один раз (при этом несущественные переменные могут входить неограниченное число раз). Например, формула &(x₁,Ш (x₁)) является бесповторной, так как она тождественно равна нулю, а значит, не имеет существенных переменных. Переменная x₁ несущественна для нее. Скажем, что функция f бесповторно выразима в базисе Б, если существует бесповторная формула в базисе Б, реализующая функцию f. Как показал О.Б.Лупанов, константы, функции одного аргумента и нелинейные функции двух аргументов бесповторно выразимы в любом базисе. В частности, все функции из базиса Б₀ бесповторно выразимы в любом базисе. Признак сравнения базисов звучит так: если все функции из базиса Б' бесповторно выразимы в базисе Б, то базис Б предшествует базису Б'. Таким образом, каждый базис предшествует базису Б₀. Другими словами, базис Б₀ является минимальным (или самым плохим).

Скажем, что базис Б строго предшествует (или лучше) базису Б', если Б предшествует базису Б', а Б' не предшествует базису Б. Мы знаем, что базис Б₁ предшествует базису Б₀, а Б₀ не предшествует базису Б₁, поэтому базис Б₁ строго предшествует базису Б₀. Если ограничиться только базисами, состоящими из двуместных функций, то с помощью признака Лупанова можно показать, что каждый из них эквивалентен либо базису Б₀, либо базису Б₁, а именно, двуместный базис эквивалентен базису Б₁ тогда и только тогда, когда он содержит хотя бы одну из функций: x₁ Еx₂ или x₁Е x₂ Е1. Например, базис {|}, состоящий из штриха Шеффера, эквивалентен базису Б₀, а базис P₂(2), состоящий из всех двуместных функций - базису Б₁. Таким образом, существуют ровно два класса эквивалентности среди базисов, состоящих из двуместных функций, причем второй из этих классов строго предшествует первому.

Мы получили полное описание структуры двуместных базисов. Возникает вопрос: как выглядит структура всех базисов, т. е. конечно в ней число классов эквивалентности, или бесконечно, существуют ли несравнимые классы, бесконечно возрастающие и бесконечно убывающие цепи и т. д. Усилиями нескольких исследователей, в том числе автора, на перечисленные выше вопросы удалось получить ответы, но полностью описать структуру базисов до сих пор не удалось, полностью описан только второй ярус, следующий за максимальным базисом Б₀ - м ножество предмаксимальных базисов.

В [3] Субботовская получила следующий критерий эквивалентности произвольного базиса базису Б₀: базис Б эквивалентен Б₀ тогда и только тогда, когда все функции из базиса Б бесповторно выразимы в базисе Б₀. Другими словами, она доказала обращение признака О.Б.Лупанова в частном случае, когда одним из базисов является базис Б₀. С помощью критерия Субботовской доказательство неэквивалентности базисов Б₀ и Б₁ сводится к следующему: достаточно доказать, что функция x₁Е x₂ бесповторно невыразима в базисе Б₀, что делается несложным перебором. Критерий Субботовской позволил выделить базисы, неэквивалентные базису Б₀.

Исследования в этом направлении продолжил спустя 20 лет В.А.Стеценко. В работе [5] он рассмотрел предмаксимальные базисы, т. е. базисы, непосредственно предшествующие базису Б₀. Скажем, что базис Б непосредственно предшествует базису Б', если, во-первых, Б строго предшествует базису Б', а во-вторых, не существует такого базиса Б'', что Б строго предшествует базису Б''. а Б'' строго предшествует базису Б'. В.А.Стеценко дал необходимый признак того, что произвольный базис Б является предмаксимальным. А именно, он ввел понятие S-функции, выписал все S-функции с точностью до некоторой эквивалентности, и доказал, что каждый предмаксимальный (или предплохой) базис эквивалентен базису вида Б₀ И {f}, где f - S-функция. В.А.Стеценко также выдвинул гипотезу, что все упомянутые им базисы действительно являются предмаксимальными и попарно неэквивалентны. Описание яруса предмаксимальных базисов завершено в [7], где доказана гипотеза Стеценко, и таким образом, получена классификация предмаксимальных базисов с точностью до эквивалентности. Оказалось, что существует бесконечное число попарно неэквивалентных предмаксимальных базисов. Например, Б₁ - предмаксимальный базис.

Заметим, что если два предмаксимальных базиса неэквивалентны, то они несравнимы, поэтому существует бесконечное множество попарно несравнимых базисов, т. е. структура базисов бесконечна в "ширину". Также оказалось, что эта структура бесконечна в "длину", т. е. существует бесконечная строго убывающая цепь базисов. Первый шаг в этом направлении, как мы уже говорили, был сделан в работе [3], где доказано существование строго убывающей цепи из двух базисов. Следующий шаг также сделала Субботовская в [4], предъявив строго убывающую цепь из трех базисов. Затем, после двадцатилетнего перерыва, в [6] удалось получить бесконечную строго убывающую цепь базисов. А именно, в [6] показано, что базис P₂(n+1) строго предшествует базису P₂(n) при n>1. Из этого результата следует, что не существует минимального (или наилучшего) базиса.

Далее, в работе [8] получен критерий сравнения произвольных базисов, являющийся
обращением признака Лупанова. А именно: для произвольных базисов Б и Б' базис Б предшествует базису Б' тогда и только тогда, когда все функции из базиса Б' бесповторно выражаются в базисе Б. Оказалось, что данный критерий алгоритмичен, т. е. существует алгоритм, проверяющий, предшествует ли базис Б базису Б', или нет. Более того, каждому базису можно алгоритмически сопоставить конечное множество функций - ядро этого базиса так, что базис Б предшествует базису Б' тогда и только тогда, когда ядро базиса Б' является подмножеством ядра базиса Б, причем если базис Б непосредственно предшествует базису Б', то его ядро содержит ровно на одну функцию больше, чем ядро базиса Б'. Из этого уточненного критерия, в частности следует, что множество базисов можно разбить на ярусы, т. е. оно является бесконечно ранжируемым множеством; что каждый базис предшествует лишь конечному числу классов эквивалентности базисов, поэтому не существует бесконечно возрастающих цепей базисов. Наконец, можно показать, что каждому базису непосредственно предшествует бесконечное число различных классов эквивалентности базисов.

Таким образом, задача сравнения базисов "в узком смысле" была решена, более того, были получены глобальные характеристики структуры базисов, но, тем не менее, полное описание структуры базисов получить не удается ввиду ее сложности. Некий фрагмент структуры базисов третьего яруса был получен Н.А.Перязевым в [9], описавшим множество базисов, непосредственно предшествующих базису Б₁. Однако, даже задача полного описания третьего яруса далека от завершения.

[9] Перязев Н. А. Слабоповторные булевы функции в бинарном базисе - Иркутский университет. Серия: Дискретная математика и информатика. Вып. 4. Иркутск. 1998. 12с.