1_Algebra_logiki

Полнота и замкнутость Замкнутые классы

Класс монотонных функций

M замкнутый класс

Рассмотрим (x1; : : : ; xn) = f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )),

f(f1( 11; : : : ; 1p1 ); : : : ; fm( m 1; : : : ; m pm )) 6

f(f1( 11; : : : ; 1p1 ); : : : ; fm( m 1; : : : ; m pm )) ò.ê. f 2 M

) (x1; : : : ; xn) 2 M.

) класс M замкнут.

Класс монотонных функций

Лемма о немонотонной функции

Åñëè f(x1; : : : ; xn) 2= M, то из нее путем замены переменных на константы 0, 1 и x можно получить немонотонную функцию одной переменной, а именно x.

Класс монотонных функций

Лемма о немонотонной функции

Доказательство

Полнота и замкнутость Замкнутые классы

Класс монотонных функций

Лемма о немонотонной функции

Доказательство

Докажем, что если f 2= M, то 9 пара соседних наборов 4 , для которых f( ) > f( )

Полнота и замкнутость Замкнутые классы

Класс монотонных функций

Лемма о немонотонной функции

Доказательство

Докажем, что если f 2= M, то 9 пара соседних наборов 4 , для которых f( ) > f( ) Два набора значений переменных называются

соседними по i-й переменной, если они отличаются только значениями этой переменной.

Полнота и замкнутость Замкнутые классы

Класс монотонных функций

Лемма о немонотонной функции

Доказательство

Докажем, что если f 2= M, то 9 пара соседних наборов 4 , для которых f( ) > f( )

f 2= M ) 9 наборы и такие что f( ) > f( )

Полнота и замкнутость Замкнутые классы

Класс монотонных функций

Лемма о немонотонной функции

Доказательство

Докажем, что если f 2= M, то 9 пара соседних наборов 4 , для которых f( ) > f( )

f 2= M ) 9 наборы и такие что f( ) > f( )

Наборы и отличаются значениями в t компонентах (t > 1).

Полнота и замкнутость Замкнутые классы

Класс монотонных функций

Лемма о немонотонной функции

Доказательство

Докажем, что если f 2= M, то 9 пара соседних наборов 4 , для которых f( ) > f( )

f 2= M ) 9 наборы и такие что f( ) > f( )

Наборы и отличаются значениями в t компонентах (t > 1).

i 6 i ) i = 0, i = 1

Полнота и замкнутость Замкнутые классы

Класс монотонных функций

Лемма о немонотонной функции

Доказательство

Докажем, что если f 2= M, то 9 пара соседних наборов 4 , для которых f( ) > f( )

f 2= M ) 9 наборы и такие что f( ) > f( )

Наборы и отличаются значениями в t компонентах (t > 1).

i 6 i ) i = 0, i = 1 èëè i = i

Полнота и замкнутость Замкнутые классы

Класс монотонных функций

Лемма о немонотонной функции

Доказательство

Докажем, что если f 2= M, то 9 пара соседних наборов 4 , для которых f( ) > f( )

f 2= M ) 9 наборы и такие что f( ) > f( )

Наборы и отличаются значениями в t компонентах (t > 1).

i 6 i ) i = 0, i = 1 èëè i = i

) между и можно вставить t 1 промежуточных наборов