Помимо принадлежности к классам, существуют теоремы (леммы) о функциях, не принадлежащих этим классам.

Лемма о несамодвойственной функции

Из любой несамодвойственной функции, подставляя вместо всех переменных функции и , можно получить константу.

Алгоритм

1. Выделяется пара строк, на которых самодвойственность теряется, (значения переменных противоположны, а значения функции одинаковы).
2. Далее, выбирается одна из этих строк и в ней заменяются значения переменных по правилу:
   1. если переменная принимает значение 0, то в функции она заменяется на ,
   2. если переменная принимает значение 1, то в функции она заменяется на x.

Например, рассмотрим функцию , не являющуюся самодвойственной.
Рассмотрим наборы, на которых теряется самодвойственность: (0,1), (1,0) и выберем первый из них.
Тогда, вместо x подставляя и вместо y подставляя x, получим функцию .
Рассмотрев полученную функцию от аргументов 0 и 1, получим константу 1: ,

Лемма о немонотонной функции

Из любой немонотонной функции, подставляя вместо всех переменных функции x, 0, 1, можно получить функцию .

Алгоритм

1. Выделяется пара строк, на которых монотонность нарушается.
2. Для каждой переменной из этих строк сравниваются её значения в этих двух строчках и:
   1. если значения переменной одинаковые – в функции вместо этой переменной подставляется эта константа (либо 0, либо 1),
   2. если значения не одинаковые, то в функции вместо этой переменной подставляется x.

Например, рассмотрим функцию , не являющуюся монотонной.
Рассмотрим наборы, на которых монотонность теряется: (0,1), (1,1).
Тогда, вместо x подставляя x и вместо y подставляя 1, получим функцию .
Рассмотрев полученную функцию от аргументов 0 и 1, получим : ,

Лемма о нелинейной функции

Из любой нелинейной функции, подставляя вместо всех переменных , можно получить или .

Алгоритм для функции двух переменных

1. Разложить функцию в полином Жегалкина, если она представлена в другом виде. Так как она является нелинейной, то в полиноме обязательно содержится конъюнкция переменных. Обозначим это разложение через .
2. Рассмотреть суперпозицию функций , где – коэффициенты перед x и y соответственно в разложении полинома .
   1. Если – нелинейная функция получена.
   2. Если , то рассматриваем функцию . Тогда – нелинейная функция получена.

Например, рассмотрим функцию , не являющуюся линейной.
Её разложение в полином Жегалкина .
Рассмотрим суперпозицию .
Раскрываем скобки, приводим подобные и получаем, что .
Поскольку конъюнкция не получилась, сделаем из нее дизъюнкцию, рассмотрев функцию .
Преобразуем полученную функцию h и получим искомую дизъюнкцию: .
Нелинейная функция получена.