Класс м.

М – класс монотонных ф-ций.

Пусть =(1,…,n) и =(1,…, n).

Набор  меньше набора  (<), {(< – такой треугольничек)} если 11, 22,…,nn. Например: (1001)<(1011).

< – рефликсивно, транзитивно, антисиметрично, т.е. это отношение частичного порядка, но в общем случае не линейного порядка. Ф-ция f наз. монотонной, или всегда из того, что < следует f()f().

входят: 0, 1, x, &, .

невходят: x, , , .

Для проверки ф-ции на монотонность необходимо проверить, что f()f() для всевозможных пар сравнимых наборов.

Класс мон. ф-ций замкнут: [M]=M.

Соотношение < индуцирует это же соотношение на всевозможных поднаборов  и .

(j1, j2, …,jij)<(j1, j2, …,jij).

Пусть i=fj(j1, j2, …,jij), i=fj(j1, j2, …,jij) тогда из того, что fjM, ij (j=1,k), т.е. < но f0M т.е. f0()f0(), а, значит Ф()Ф(). ч.т.д.

Лема о немонотонных ф-циях: Если ф-ция f немонотонна, то из нее путем подстановки вместо переменных констант и тождественной ф-ции можно подставить отрицание.

Пусть fM т.е. <: f()<f(), поэтому f()=1, f()=0. Покажем, что найдутся два соседних набора (по некоторой переменной)  и  такие, что <, а f()>f(). Предположим обратное: пусть < и они отличаются, например, по первым t переменным.

=(0, 0, …, 0, t+1,…,n)

=(1, 1, …, 1, t+1,…, n)

По  и  построим последовательность наборов (0)=, (1) – соседний с (0) по 1-й переменной, (2) – по 2-й переменной и т.д., (t)=.

=(0)<(1)<…<(t)=, причем f((0))>f((t)), поэтому в этой последовательности найдутся два соседних набора (i)<(i+1), а f((0))>f((i+1)).

Поэтому будем предпологать, что  и  – два соседних набора, для которых нарушается монотонность. Эти наборы можно найти по таблице истинности. Построим ф-цию (x)=( 1,…,i-1,x,i+1,…,n) (наборы и соседние по х).

(0)=( 1,…,i-1,0,i+1,…,n)=f()=1

(1)=( 1,…,i-1,1,i+1,…,n)=f()=0

т.е. (x)=x ч.т.д.