ВУЗ:
Составители:
Рубрика:
38
доказательство завершено.
Если же
1
α
~
и
1
β
~
не являются соседними наборами, то набор
1
β
~
отличается от набора
1
α
~
в
t координатах, где t>1, причем эти t
координат в наборе
1
α
~
равны
0, а в наборе
1
β
~
равны 1. В силу
этого между
1
α
~
и
1
~
β
можно вставить t-1 промежуточных наборов
t2
αα
~
,...,
~
:
12 1
... ,
t
α
ααβ
≺≺≺≺
причем наборы, стоящие рядом, будут соседними. Т.к.
)
~
()
~
(
11
ff
βα
> , то, по крайней мере, на какой-то одной паре
соседних наборов (обозначим их
α
~
и )
~
()
~
()
~
βαβ
ff > . Пусть
α
~
и
β
~
- соседние по i-ой координате, т.е.
),...,,,,...,(
~
),,...,,,,...,(
~
n1i1i1
n1i1i1
1
0
ααααβ
α
α
α
α
α
+−
+−
=
=
Рассмотрим функцию
).,...,,,,...,()(
n1i1i1
xfx
α
α
α
α
ϕ
+−
=
Имеем
).(),...,,,,...,(
)
~
()
~
(),...,,,,...,()(
11f
ff0f0
n1i1i1
n1i1i1
ϕαααα
βαααααϕ
==
=>==
+−
+−
Следовательно
.)(..,)(,)( xxет01а10
=
=
=
ϕ
ϕ
ϕ
Класс L
Последним классом является класс L всех линейных функций.
Он содержит константы 0 и 1,функции x,
x, yx
⊕
и не содержит
функций x
∨
y, x&y. Ранее было показано, что этот класс замкнут.
Лемма
(о нелинейной функции). Если f(x
1
,…,x
n
)∉L, то из нее
путем подстановки констант 0 и 1 и функций x и
x ,а также, быть
может, путем навешивания отрицания над f можно получить
функцию x
1
& x
2
.
Замечание.
Любая формула, построенная из констант 0,1 и
функций x
1
& x
2
и x
1
⊕
x
2
, после раскрытия скобок и несложных
алгебраических преобразований переходит в полином по mod2 –
Страницы
- « первая
- ‹ предыдущая
- …
- 36
- 37
- 38
- 39
- 40
- …
- следующая ›
- последняя »
