Класс 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)$ является отрицанием.