Зарипова, Э.Р. Дискретная математика Часть II. Математическая логика

42 Пусть  ~ и  ~ два набора длины n значений переменной x ~ , находящихся в отношении предшествования:   ~ ~  . Эти наборы определяют наборы 1 1 m m     ~ ,..., ~ , ~ ~ , значений переменных 1 m x x ~ ,..., ~ такие, что 1 m m 1     ~ ~ ,..., ~ ~   . Так как функции f 1 ,…,f m монотонны, то ) ~ ( ( ~ ) ),..., ~ ( ( ~ ) m m m m 1 1 1 1 f f f f       . Поэтому )) ~ ( ),..., ~ ( ~ )) ( ( ),..., ( ( ~ m m 1 1 m m 1 1 f f f f      и в силу монотонности f имеем ) ~ ( )) ~ ( ),..., ~ ( ( ( ~ )) ),..., ( ~ ) ( ( ~            m m 1 1 m m 1 1 f f f f f f , т.е. ) ~ ( ( ~ )      – монотонна. Определение. Будем называть наборы  ~ и  ~ соседними, если ) ,..., , , ,..., ( ~ ), ,..., , , ,..., ~ ( n i 1 i i 1 1 n i 1 i i 1 1                   и докажем следующую лемму. Лемма (о немонотонной функции). Если f(x 1 ,…,x n )  M , то из нее путем подстановки констант 0 и 1 и функции x можно получить функцию x . Доказательство. Докажем сначала, что найдутся соседние наборы  ~ и  ~ :   ~ ~  и ) ~ ( ~ ) (   f f  . Действительно, так как f  M , то существуют наборы 1  ~ и 1 1 1 :     и ) ~ ( ~ ) ( 1 1 f f    . Если 1  ~ и 1  соседние, то доказательство завершено. Если же 1  ~ и 1  ~ не являются соседними наборами, то набор 1  ~ отличается от набора 1  ~ в t координатах, где t>1 , причем эти t координат в наборе 1  ~ равны 0 , а в наборе 1  ~