ВУЗ:
Составители:
Рубрика:
37
),...,(
m1
fff=
Φ
является монотонной, если f, f
1
,…,f
m
монотонны.
Действительно, пусть
),...,(
~
),...,,...,(
~
),,...,(
~
m1
ml1m
m
l111
1
n1
xxxxxxxxx ===
наборы переменных функций
Φ
, f
1
,…,f
m
. Причем множество
переменных функции
Φ
состоит из тех и только тех переменных,
которые встречаются у функций f
1
,…,f
m
.
Пусть
α
~
и
β
~
два набора длины n значений переменной x
~
,
находящихся в отношении предшествования:
βα
~
~
≺ . Эти наборы
определяют наборы
mm11
βαβα
~
,
~
,...,
~
,
~
значений переменных
m1
xx
~
,...,
~
такие, что
mm11
βαβα
~
~
,...,
~
~
≺≺ . Так как функции f
1
,…,f
m
монотонны, то
)
~
()
~
(),...,
~
()
~
(
m
m
m
m
1
1
1
1
ffff
βαβα
≤≤ .
Поэтому
))
~
(),...,
~
(())
~
(),...,
~
((
m
m
1
1
m
m
1
1
ffff
ββαα
≺
и в силу монотонности f имеем
)
~
())
~
(),...,
~
(())
~
(),...,
~
(()
~
(
βΦββαααΦ
=≤=
m
m
1
1
m
m
1
1
ffffff ,
т.е. )
~
()
~
(
βΦαΦ
≤ - монотонна.
Определение.
Будем называть наборы
α
~
и
β
~
соседними, если
),...,,,,...,(
~
),,...,,,,...,(
~
n1ii1i1
n1ii1i1
αααααβ
α
α
α
α
α
α
+−
+−
=
=
и докажем следующую лемму.
Лемма
(о немонотонной функции). Если f(x
1
,…,x
n
)
∉
M , то из нее
путем подстановки констант
0 и 1 и функции x можно получить
функцию
x
.
Доказательство.
Докажем сначала, что найдутся соседние
наборы
α
~
и
β
~
:
βα
~
~
≺ и )
~
()
~
(
βα
ff > .
Действительно, так как
f
∉
M, то существуют наборы
1
α
~
и
11 1
:
β
αβ
≤
и )
~
()
~
(
11
ff
βα
> . Если
1
α
~
и
1
β
соседние, то
Страницы
- « первая
- ‹ предыдущая
- …
- 35
- 36
- 37
- 38
- 39
- …
- следующая ›
- последняя »
