Лемма о нелинейной функции
Если функция f(`хn) Ï L, то путем подстановки вместо ее переменных констант 0, 1, функций х,`х и, возможно, навешивания общего отрицания из f(`хn) всегда можно получить двухместную функцию умножения ху.
Доказательство. Из f (`х n) ÏL следует, что ее можно представить в виде f (`х n) = L(`х n ) + N (`х n ), где L(`х n )—линейная часть (возможно, L(`х n ) º 0 ), N (`х n )— нелинейная часть (N (`х n )¹ 0).
Рассмотрим самое короткое произведение, содержащееся в нелинейной части N (`х n ). Выделим в нём две произвольные переменные (допустим, начальные) и обозначим их х и у. Данное произведение можно представить в виде хухк1...хкs. Другие произведения, содержащие х и у, будут обязательно включать и другие сомножители хк(s+1) , . . . , хкm. Подставляя вместо переменных хк1, . . . , хкs константу 1, а вместо остальных (включая хк(s+1) , ... , хкm ) константу 0, получим функцию двух переменных F(x,у), которая в общем случае имеет следующий вид:
F(x,у) = ху +a1 х +a2 у +a3 .
При a1= 1 выполняем подстановку у =`у, если a2= 1, то выполняем подстановку х =` х. В итоге получаем новую функцию F1(x,у) = ху + a3 .
Если a3 = 0 , то искомое умножение получено, если a3 = 1 , то умножение получаем, навешивая общее отрицание:
Ø F1(x,у) = F2(x,у) = ху.
ЗАДАЧИ
1. Почему линейны все функции, у которых число переменных не превышает 1?
2. Какие из перечисленных систем линейных функций образуют базис в L: а) {0, х Å у}, б) {1, х Å у} в) {0, 1, х Å у}?
3. Доказать, что если f(`хn) линейна и не является константой, то в векторе значений f(`х n) всегда будет равное число значений 1 и 0. Верно ли обратное? Ответ обосновать.
4. Проверить линейность функций:
а) ху Ú yz Ú xz ;б) х ® у ® х у;в) (10110110); г) х у ®`х` у; д) (10011001); е) (0001100111111011).
5. Найти мощность класса Ln.
6. Сколько существует в Ln функций, существенно зависящих ровно от k (k ≤ n) своих переменных ?
7. Доказать замкнутость класса L.
8. Доказать предполноту класса Lв Р2, например, с использованием леммы о нелинейной функции и сведением дополненной системы к {f} = {& ,Ú ,Ø} .
Дата добавления: 2015-10-05; просмотров: 4706;