Помимо принадлежности к классам, существуют теоремы (леммы) о функциях, не принадлежащих этим классам.
Лемма о несамодвойственной функции
Из любой несамодвойственной функции, подставляя вместо всех переменных функции
и
, можно получить константу.
Алгоритм
- Выделяется пара строк, на которых самодвойственность теряется, (значения переменных противоположны, а значения функции одинаковы).
- Далее, выбирается одна из этих строк и в ней заменяются значения переменных по правилу:
- если переменная принимает значение 0, то в функции она заменяется на
,
- если переменная принимает значение 1, то в функции она заменяется на x.
Например, рассмотрим функцию
, не являющуюся самодвойственной.
Рассмотрим наборы, на которых теряется самодвойственность: (0,1), (1,0) и выберем первый из них.
Тогда, вместо x подставляя
и вместо y подставляя x,
получим функцию
.
Рассмотрев полученную функцию от аргументов 0 и 1, получим константу 1:
,
Лемма о немонотонной функции
Из любой немонотонной функции, подставляя вместо всех переменных функции x, 0, 1, можно получить функцию
.
Алгоритм
- Выделяется пара строк, на которых монотонность нарушается.
- Для каждой переменной из этих строк сравниваются её значения в этих двух строчках и:
- если значения переменной одинаковые – в функции вместо этой переменной подставляется эта константа (либо 0, либо 1),
- если значения не одинаковые, то в функции вместо этой переменной подставляется x.
Например, рассмотрим функцию
, не являющуюся монотонной.
Рассмотрим наборы, на которых монотонность теряется: (0,1), (1,1).
Тогда, вместо x подставляя x и вместо y подставляя 1, получим функцию
.
Рассмотрев полученную функцию от аргументов 0 и 1, получим
:
,
Лемма о нелинейной функции
Из любой нелинейной функции, подставляя вместо всех переменных
,
можно получить
или
.
Алгоритм для функции двух переменных
- Разложить функцию в полином Жегалкина, если она представлена в другом виде. Так как она является нелинейной, то в полиноме обязательно содержится конъюнкция переменных.
Обозначим это разложение через
.
- Рассмотреть суперпозицию функций
,
где
– коэффициенты перед x и y соответственно в разложении полинома
.
- Если
– нелинейная функция получена.
- Если
, то рассматриваем функцию
.
Тогда
– нелинейная функция получена.
Например, рассмотрим функцию
, не являющуюся линейной.
Её разложение в полином Жегалкина
.
Рассмотрим суперпозицию
.
Раскрываем скобки, приводим подобные и получаем, что
.
Поскольку конъюнкция не получилась, сделаем из нее дизъюнкцию, рассмотрев функцию
.
Преобразуем полученную функцию h и получим искомую дизъюнкцию:
.
Нелинейная функция получена.