Класс 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)$ является отрицанием.
Далее:
Поток векторного поля через поверхность
Соленоидальное векторное поле
Введение
Полином Жегалкина. Пример.
Свойства криволинейного интеграла второго рода
Класс M. Теорема о замкнутости класса M
Выражение площади плоской области через криволинейный интеграл
Решение задач с помощью алгебры высказываний
Вычисление площади поверхности
Формула Грина
Переход от двойного интеграла к повторному. Изменение порядка интегрирования. Переход к полярным координатам
Вычисление криволинейного интеграла первого рода. Плоский случай
Теорема о предполных классах
Криволинейный интеграл первого рода
Вычисление поверхностного интеграла второго рода
Огравление $\Rightarrow $
Комментарии ()