Теорема (лемма о несамодвойственной булевой функции)

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

Доказательство. Пусть f Ï S Þ f ¹ f^*. Это означает, что найдется набор значений переменных, для которого т.е.

Если

то и для функции от одной переменной х имеем

т.е. ■

ТЕОРЕМА (лемма о немонотонной булевой функции). Из любой немонотонной булевой функции с помощью подстановки в нее вместо переменных констант 0 и 1 и тождественной функции можно получить функцию отрицания.

Доказательство. Пусть f Ï M Þ $ a =< a ₁, …, a_n >, b = < b ₁,…, b_n >, a µ b, но f (a) > f (b),т.е. f (a) =1, f (b) =0. Неравенство a_i < b_i, означает, что a_i = 0, b_i = 1.

Если

то и для функции имеем ■

ТЕОРЕМА (лемма о нелинейной булевой функции). Из любой нелинейной булевой функции с помощью подстановки в нее вместо переменных констант 0 и 1, тождественной функции, функции отрицания можно получить конъюнкцию или отрицание конъюнкции.

Доказательство. Представление нелинейной булевой функции f в виде полинома Жегалкина содержит слагаемое, в котором обязательно присутствуют конъюнкция каких-либо двух переменных. Изменение нумерации переменных не ослабит общности доказательства теоремы, и мы изменим нумерацию переменных таким образом, чтобы в полиноме Жегалкина присутствовало слагаемое с конъюнкцией х ₁ х ₂. Тогда, собрав в одну скобку все слагаемые, содержание х ₁ х ₂, в другую все слагаемые, содержание х ₁,но не содержащие х ₂,в третью – содержащие х ₂, но не содержащие х ₁, получим