Класс м.

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

На множестве наборов одинаковой длины введём бинарное отношение ∆(треугольник с нижней чертой!)

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

α∆βα1≤β1,…,αn≤βn

(0,0,1)∆(0,1,1)

Данное отношение является отношением порядка, но оно не является отношением линейного порядка, потому что не все наборы сравнимы.

Свойства

1.α∆α

2.α∆β, β∆α=>α=β

3.α∆β, β∆ј=>α∆ј

Данное бинарное отношение ∆ называют отношением предшествия. В табл истинности «меньшее» наборы находятся выше.

Ф-ция назыв. монотонной, если всегда из того, что α предшествует β: α∆β=>f(α)≤f(β)

Покажем, что класс М является замкнутым [M]. Для этого достаточно показать, что элементарная суперпозиция этой ф-ции является монотонной ф-цией.

Пусть α∆β, и α и β-наборы длины n. Каждому набору α соответствует поднабор значений аргументов ф-ций f1,f2,…,fk. То есть, каждому α соответствует α^(1),α^(2),…,α^(k) аналогично соответствует β^(1),β^(2),…,β^(k). Отсжда следует, что α^(1)∆β^(1), α^(2)∆β^(2),…,α^(k)∆β^(k)

Так как f1,f2,…,fk монотонны, то f1^(α^(1))≤f1(β^(1))

f2(α^(2))≤f(β^(2)) ……………… fk(α^(k))≤fk(β^(k)), а так f0 тоже монотонно, то получаем, что f0(α)≤f0(β).

То есть Ф(α)=f0(α)=f(f1(α^(1),…,fk(α^(k)))≤f0(f1(β^(1)),…,fk(β^(k)))=f0(β)=Ф(β). И это значит, что класс ф-ций замкнут.

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

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

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

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

По  и  построим последовательность наборов ^ (0)=α, ^ (1) – соседний с (0) по 1-й переменной,…, ^ (t) – совпадает с набором β:(t)=. Очевидно, что при таком построении все наборы будут находиться в отношении предшествия.

^(0)∆ ^ (1)∆…∆ ^ (t) f(α)=f(α^(0))>f(α^(t))=f(β)

Следовательно найдётся пара наборов α^(i) и α^(i+1), на которых нарушается монотонность.

f(α^(i))>f(α^(i+1)). Эти наборы соседние по (i+1) координате.

α^(1)=(1,1,…,1,0,0,…,αt+1,…,αn)

α^(i+1)=(1,1,…,1,0,0,…,0,αt+1,…,αn)

По набору α^(i) и ф-ции f построим ф-цию φ по одной переменной.

φ(х)=f(1,1,…,1,x,0,0,…,αt+1,…,αn)

Ф-ция φ получена в результате подстановки вф-цию f констант и тождественных ф-ций.

φ(0)=f(α^(i))>f(α^(i+1))=φ(1)

φ(0)=1, φ(1)=0 f(x)=¬x