Книги и конспекты / Шпоры / 22
.pdf22. Предшествующие наборы. Монотонная функция. Замкнутость класса монотонных функций. Соседние
наборы. Лемма о немонотонной функции. Замкнутость класса линейных функций. Теорема о нелинейной функции.
Def. Для 2 наб: =( |
|
) и =( |
) выполнено отношение предшествования ( |
|
) if |
. |
|||||||
2) |
|
, то |
|
|
|
|
|
|
|
|
|
|
|
Def: Функция f( |
) монот. If для любых 2 наборов |
|
) имеет место: f( ) |
f( |
) (0,1,x, |
) |
|||||||
М- мн-во монотонных функций. док-м замкнутость |
|
|
|
|
|
|
|
||||||
Док-м, что Ф= f( |
) монотонна если f и |
|
- монот. |
|
|
|
|
|
|
||||
Пусть |
|
, |
|
|
|
|
|
, наборы переменных функций Ф, |
мн-ва |
||||
перем. Ф сост. лишь из тех, которые встречаются у |
|
|
|
|
|
|
|
||||||
Пусть |
с l=n; |
; Они определяют наборы |
|
|
значений переменных |
: |
|
||||||
. В силу монотонности |
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
В силу монотонности Ф: |
|
|
|
|
|
|
|
|||
|
оседние по i-той корд. Если |
|
|
|
, |
|
|
|
|
|
|||
|
Т1. (о немонотонной Ф): если |
|
|
М, то из неё подстановкой 0,1, и Ф х можно получить |
|||||||||
Док, что найдётся пара соседних наборов |
: |
и |
|
|
. |
|
|
|
|||||
Т.к. f не принадлежит М,то существует |
|
: |
и |
|
|
. если |
|
–соседние – то да. |
|||||
Если не соседние, то |
отличается от |
в t корд-x, t>1. |
|
|
|
|
|
|
|||||
В t корд. |
|
. В силу этого можно между |
встав. t-1 наборов |
: |
|
|
|||||||
|
|
|
Наборы рядом из цепочки - соседние, т.к. |
|
, то хоть на 1 из этих пар |
||||||||
соседних наборов ( |
|
) )они им соседние по i-ой корд. |
т.е. |
|
|
|
|||||||
f(x)=f( |
|
) |
|
|
|
|
|
|
|
|
|
|
|
|
f( |
|
|
)= |
|
|
= f( |
|
|
)=f(1). Т.е. f(0)=1, |
|
||
f(1)=0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Класс L всех линейных ф-й замкнут. |
|
|
|
|
|
|
|
|
|
||||
он содержит 0,1,x, |
, x1 + x2 |
т: x1 |
|
и нет: замкнут. |
|
|
|
|
|
||||
1) |
(о нелинейной функции) Если |
|
|
|
|
т , то из неё путём подстановки const может |
|||||||
|
можно get x1&x2 |
|
|
|
|
|
|
|
|
|
|
||
Док-во: Полином Жегалкина |
|
|
|
|
|
: |
|
|
|
|
|||
В силу нелинейности: в нём есть член, содержащий не менее 2 множителей. Пусть x1 и |
|
||||||||||||
x2 |
|
|
=x1x2f1(x3..xn)+x1f2(x3…xn) +x2f3(x3…xn)+ fu(x3…xn) (т.к. он единственный полином |
||||||||||
f1(x3…xn)не равный 0) Пусть a3…an: f (a3…an)=1 |
f(x1,x2)=f(x1,x2,a3…an)=x1x2+ax1+ x2+ . |
|
|||||||||||
|
|
= |
|
+a |
+ . |
|
|
|
|
|
|
|
|
|
|
+a |
+ =( |
)( |
|
)+ ( |
)+ |
( |
)+ |
=x1x2 |
|
= x1&x2. |