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


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

Суперпозицией нелинейной функции, отрицания и константы 1 можно получить конъюнкцию.

Доказательство:
Пусть f(x1,…, xn ) — нелинейная функция, тогда полином Жигалкина для нее содержит слагаемое, в котором присутствует произведение каких-то переменных xi*xj. Пусть для простоты это будет произведение х1х2. Произведя группировку слагаемых в полиноме Жегалкина для f относительно x1х2, х1, х2, функцию f представим в виде f(x1,…, xn)=x1*x2*h0(x3,..,xn)+ {собрали все слагаемые с x1*x2 и вынесли x1*x2 за скобки. В скобках осталась сумма h0(x3,…,xn), в которой переменных x1, x2 нет} + x1*h1(x3,…, xn) + x2*h2(x3,…, xn) + h3(x3,…, xn)

Функция h0(x3,…, xn)≠0, в противном случае многочлен Жигалкина слагаемых с произведением x1x2 не имеет, тогда существует набор (a3,…, an) из 0 и1, для которого h0(a3,…, an)=1. Пусть на этом наборе h1(a3,…, an)=a h2(a3,…, an)=b h3(a3,…, an)=c. Тогда функция g(x1,x2)=f(x1,x2,a3,…, an)=x1*x2+a*x1+b*x2+c. Построим функцию h(x1,x2) = g(x1+bx2+a) = (x1+b)(x2+a)+a(x1+b)+b(x2+a)+c = x1*x2+a*x1+b*x2+a*b+a*x1+a*b+b*x2+a*b+c = x1*x2+a*b+c=x1*x2+d, d=a*b+c
Если d=0, то h(x1,x2)=x1*x2, конъюнкция получена. Если d=1, то h(x1,x2)=x1*x2+1 ⇒ x1*x2=⌈h(x1,x2), что и требовалось доказать.


Комментарии запрещены.




Статистика