На множестве B={0,1} в этом параграфе будем смотреть, как на частично упорядоченное множество с отношением 0<1.

Рассмотрим множество

Bⁿ=B ´ …´ B (n раз).

На множестве Bⁿ введем порядок прямого произведения, т.е.

(a₁,…,a_n)£(b₁,…,b_n) Û a₁£b₁,…,a_n£b_n

для любых a₁,…,a_n, b₁,…,b_nÎB. Например, (1,0,0,1)£(1,0,1,1), (1,0,1,0)£(1,0,1,1). В то же время, неверно, что (1,0,0,1) £(1,0,1,0).

Определение. Функция f(x₁,…,x_n) называется монотонной, если для любых двух векторов a=(a₁,…,a_n) и b=(b₁,…,b_n) из условия a£b следует, что f(a)£f(b).

Примерами монотонных функций являются q(x), i(x), x×y, xÚy. Функции n(x), x®y, x+y немонотонны.

Рассмотрим задачу: выяснить будет ли функция f(x₁,x₂,x₃)=x₁+x₂×x₃ монотонной? Для решения этой задачи удобно начертить диаграмму частично упорядоченного множества B³ и в вершинах этой диаграммы проставить значения функции f(x₁,x₂,x₃). Такая диаграмма приведена на рис. 2.1, значения функции f(x₁,x₂,x₃) заключены в квадрат, чтобы их отличать от обозначения вершин множества B³.

Рис. 2.1

Монотонность функции означает, что если в какой-то вершине диаграммы она принимает значение 1, то и всюду выше функция принимает то же значение 1. Функция f(x₁,x₂,x₃)=x₁+x₂×x₃ монотонной не является, так как в вершине (1,1,0) она принимает значение 1, а в вершине (1,1,1), которая выше первой, принимает значение 0.

Класс всех линейных функций обозначим буквой М. Убедимся в том, что М – это замкнутый класс. Монотонность тождественной функции очевидна. Пусть f(x₁,…,x_n)ÎM и y₁,…,y_n – новые переменные. Возьмем два набора значений переменных y₁,…,y_n: a=(a₁,…,a_n), b=(b₁,…,b_n) таких, что a£b. Но эти векторы будут наборами значений переменных x₁,…,x_n, и поэтому выполняется неравенство f(a)£f(b). Это означает, что М замкнут относительно переименования аргументов.

Пусть f(x₁,…,x_k), g₁(x₁,…,x_n),…, g_n(x₁,…,x_n) – монотонные функции и a=(a₁,…,a_n), b=(b₁,…,b_n) – два набора значений переменных x₁,…,x_n таких что a£b. Рассмотрим суперпозицию

h(x₁,…,x_n)= f(g₁(x₁,…,x_n),…, g_n(x₁,…,x_n)).

Значение функций g₁(a₁,…,a_n),…,g_k(a₁,…,a_n) обозначим соответственно через c₁,…,c_k, а значение g₁(b₁,…,b_n), …, g_k(b₁,…,b_n) – через d₁,…,d_k. В силу монотонности функций g₁,…,g_k имеем, что c₁£d₁,…,c_k£d_k. Тогда h(a₁,…,a_n)=f(g₁(a₁,…,a_n),…,g_k(a₁,…,a_n))=f(c₁,…,c_k) £ f(d₁,…,d_k)=f(g₁(b₁,…,b_n),…,

g_k(b₁,…,b_n))=h(b₁,…,b_n). (Знак неравенства поставлен в силу монотонности функции f). Мы доказали, что класс М замкнут относительно суперпозиции.

Следующее утверждение называется леммой о немонотонной функции.

Лемма. Пусть f(x₁,…,x_n) – немонотонная функция. Тогда замыкание класса K={f(x₁,…,x_n), q(x), i(x)} содержит n(x).

Доказательство. Поскольку f(x₁,…,x_n) немонотонна, то существуют наборы значений переменных a=(a₁,…,a_n), b=(b₁,…,b_n) такие, что a<b, но f(a)>f(b). Неравенство f(a)>f(b) означает, что f(a)=1 и f(b)=0. Рассмотрим диаграмму частично упорядоченного множества Bⁿ. Так как a<b, то точка а на диаграмме лежит ниже точки b. Существует восходящая цепь, соединяющая точку а с точкой b (см. рис. 2.2).

Рис. 2.2

На этой цепи найдутся соседние точки c=(c₁,…,c_n) и d=(d₁,…,d_n) такие, что c<d, f(c)=1 и f(d)=0. Поскольку c и d – соседние точки, то

c=(c₁,…,c_i-1,0,c_i+1,…,c_n) и d=( c₁,…,c_i-1,0,c_i+1,…,c_n).

Для удобства обозначений будем считать, что c₁=…=c_i-1=0,c_i+1=…c_n=1. Рассмотрим функцию g(x)=f(q(x),…, q(x),x;i(x),…,i(x)), где точка с запятой отделяет i-ю компоненту от (i+1)-ой. Ясно, что g(x) принадлежит замыканию класса K.

Это означает, что g(x)=n(x).

Лемма доказана.