Определение. Функция f(x1,…,xn)
называется линейной, если существует a0,a1,…,anÎB такие, что
f(x1,…,xn)=a0+a1×x1+…+an×xn.
Примерами
линейных функций являются q(x), i(x), n(x), x+y. Функции x×y, xÚy, x®y линейными не являются.
Докажем, например, нелинейность импликации f(x,y)=x®y. Предположим противное.
Пусть f(x,y) – линейная функция. Это означает, что
x®y=a0+a1×x+a2×y для некоторых a0,a1,a2ÎB. Составим таблицу, задающую функции, стоящие в левой и
правой части последнего равенства (см. таблицу 2.5).
Таблица
2.5
x |
y |
x® y |
a0+a1×x+a2×y |
Следствие |
0 |
0 |
1 |
a0 |
a0=1 |
0 |
1 |
1 |
1+a2 |
a2=0 |
1 |
0 |
0 |
1+a1 |
a1=1 |
1 |
1 |
1 |
0 |
Противоречие |
Противоречие показывает, что x® y –
нелинейная функция.
Класс всех
линейных функций обозначим буквой L. Класс L
является замкнутым. Действительно, тождественная функция является линейной.
Далее очевидно, что замена аргументов у линейной функции дает линейную и
суперпозиция линейных функций линейна.
Следующее
утверждение называется леммой о
нелинейной функции.
Лемма. Пусть f(x1,…,xn)
– нелинейная функция. Тогда замыкание класса K={f(x1,…,xn), q(x), i(x), n(x)} содержит произведение x×y.
Доказательство. Как отмечалось в §1
каждая функция может быть задана полиномом Жегалкина. Это означает, что
f(x1,…,xn)=åai1,…,ik xi1×xi2×…×xik, (1)
где {i1,…,ik} Í
{1,…,n}, ai1,…,ikÎB и суммирование ведется по всем подмножествам множества
{1,…,n}. Так как f(x1,…,xn) – нелинейная функция, то
хотя бы одно слагаемое имеет степень большую или равную двум. Без ограничения
общности можно считать, что это слагаемое содержит произведение x1×x2. Слагаемое
правой части равенства (1) разделим на 4 группы: содержащие x1×x2; содержащие x1 и не содержащие
x2; не
содержащие x1
и содержащие x2,
не содержащие x1
и x2. В
первой группе вынесем за скобки х1×х2, во второй – х1, в третьей
– х3, получим, что
f(x1,…,xn)=
x1×x2×f0(x3,…,xn)+x1×f1(x3,…,xn)+x2×f2(x3,…,xn)+f3(x3,…,xn).
Если f0(x3,…,xn) есть
тождественный нуль, то выделим произведение переменных в одном из оставшихся
слагаемых и проведем аналогичную группировку. Будем поэтому считать, что
существуют a3,…,anÎB такие, что f0(a3,…,an)=1. Пусть c1=f1(a3,…,an),
c2=f2(a3,…,an), c3=f3(a3,…,an).
Рассмотрим функции
g(x1,x2)=f(x1,x2,a3,…,an)=x1×x2+c1×x1+c2×x2+c3 и
h(x1,x2)=g(x1+c2, x2+c1)+c1×c2+c3
Если c=1, то c×x=i(x)×x, x+c=n(x); если же с=0, то c×x=q(x), x+c=x. Отсюда следует, что функции g(x1,x2) и h(x1,x2)
принадлежат замыканию класса K.
В то же время
h(x1,x2)=(x1+c2)( x2+c1)+c1(x1+c2)+ c2(x2+c1)+c3+c1×c2+c3=
x1×x2+c2×x2+c1×x1+c1×c2+c1×x1+c1×c2+c2x2+c1c2+c3+c1×c2+c3=x1x2
поскольку сложение на множестве B удовлетворяет тождеству u+u=0.
Итак, замыкание класса K
содержит произведение х×y.
Лемма доказана.
|