Класс M. Теорема о замкнутости класса M

Функция называется монотонной: $(\beta\_1, \beta\_2, \ldots, \beta\_n) \ge (\alpha\_1, \alpha\_2, \ldots, \alpha\_n) \Rightarrow f(\beta\_1, \beta\_2, \ldots, \beta\_n) \ge f(\alpha\_1, \alpha\_2, \ldots, \alpha\_n)$. Обозначают, что $f \in M$.

$(\beta\_1, \beta\_2, \ldots, \beta\_n) \ge (\alpha\_1, \alpha\_2, \ldots, \alpha\_n) \Leftrightarrow \forall i (\beta\_i \ge \alpha\_i)$

**Определение.**Набор $\tilde { \alpha } = (\alpha\_1, ..., \alpha\_n)$ предшествует набору $\tilde { \beta } = (\beta\_1, ..., \beta\_n)$ и обозначается $\tilde { \alpha } \leq \tilde { \beta }$, если для $1 \leq i \leq n$ $\alpha\_i \leq \beta\_i$, например: $\tilde { \alpha } = (0010)$, $\tilde { \beta } = (0110)$, тогда $\tilde { \alpha } \leq \tilde { \beta }$. Не любые два набора находятся в отношении предшествования, например, наборы $(0110)$ и $(1010)$ в таком отношении не находятся. Отношение предшествования $(\leq )$ является отношением порядка на множестве наборов длины $n$, множество таких наборов будет частично упорядоченным множеством по отношению к операции.

**Определение.**Функция $f(x\_1, ..., x\_n)$ называется монотонной, если для двух наборов $\tilde { \alpha }$ и $\tilde { \beta }$, таких что $\tilde { \alpha } \leq \tilde { \beta }$, выполняется $f( \alpha ) \leq f( \beta )$. Функции $0, 1, x, x\_1\wedge x\_2, x\_1\vee x\_2 \in M, x\_1\downarrow x\_2, x\_1\oplus x\_2, x\_1 \sim x\_2 \notin M$.

Для числа монотонных функций, зависящих от $n$ переменных, существуют оценки сверху и снизу, но точное число сосчитать не удается. Покажем, что $М$ замкнутый класс. Рассмотрим функцию $\Phi \in [M], \Phi = f(f\_1, ..., f\_m)$, где $f, f\_1, ..., f\_m\in M$, причем можем считать, что все они зависят от $n$ переменных. Пусть набор $\tilde { \alpha } = (\alpha\_1, ..., \alpha\_n), \tilde { \beta } = (\beta\_1, ..., \beta\_n)$. Рассмотрим $\Phi (\alpha\_1, ..., \alpha\_n) = f(f\_1(\alpha\_1, ..., \alpha\_n)), ..., f\_m(\alpha\_1, ..., \alpha\_n) и \Phi (\beta\_1, ..., \beta\_n) = f(f\_1(\beta\_1, ..., \beta\_n), ..., f\_m(\beta\_1, ..., \beta\_n))$. Здесь $f\_1(\alpha) \leq f\_1(\beta), ..., f\_m(\alpha) \leq f\_m(\beta)$, тогда набор $(f\_1(\alpha), ..., f\_m(\alpha)) \leq (f1(\beta), ..., fm(\beta))$, но тогда $\Phi(\alpha) \leq \Phi(\beta)$, так как $f\in M$, отсюда $\Phi = f(f\_1, ..., )$ – монотонная функция.

**Определение.**Функция $f$ есть суперпозиция над $M$, если $f$ реализуется некоторой формулой над $M$.

**Лемма о немонотонной функции.**Отрицание можно получить суперпозицией констант $0$ и $1$, тождественной функции и немонотонной функции.

**Доказательство.**Пусть $f(x\_1, ..., x\_n)$ – немонотонная функция. Тогда существуют наборы $\tilde { \alpha } = (\alpha\_1, ..., \alpha\_n)$ и $\tilde { \beta } = (\beta\_1, ..., \beta\_n)$, для которых $\tilde { \alpha } \leq \tilde { \beta }$, но $f(\tilde { \alpha } ) \succ f(\tilde { \beta } )$ Пусть $i\_1, …, i\_k$ есть все те номера аргументов, для которых $\alpha\_ { i\_p } < \beta\_ { i\_p }$, $p=1, ..., k$. На всех остальных аргументных местах $j$ имеем $\alpha\_j = \beta\_j$. В выражении $f(\alpha\_1, ..., \alpha\_n)$ заменим нули на местах $i\_1, …, i\_k$ на $x$. В результате получим функцию $g(x)$, для которой $g(0) = f(\tilde { \alpha } ) = 1$ и $g(1) = f(\tilde { \beta } ) = 0$. Функция $g(x)$ является отрицанием.