СВ в 10:39, 25 октября 2026

2026-10-25T10:39:58Z

← Предыдущая		Версия 10:39, 25 октября 2026
Строка 156:		Строка 156:

	[[Файл:p43-01-monotone-chain-descent.svg\|frame\|none\|900px\|alt=Булев куб с выделенной цепочкой 000—001—011—111 и значениями 1, 1, 1, 0\|Рис. 1. Монотонность проверяется вдоль цепочек: на цепочке <math>000 \preceq 001 \preceq 011 \preceq 111</math> значения равны <math>1, 1, 1, 0</math>. Одного спуска <math>1 \to 0</math> достаточно, чтобы заключить <math>f \notin M</math>.]]		[[Файл:p43-01-monotone-chain-descent.svg\|frame\|none\|900px\|alt=Булев куб с выделенной цепочкой 000—001—011—111 и значениями 1, 1, 1, 0\|Рис. 1. Монотонность проверяется вдоль цепочек: на цепочке <math>000 \preceq 001 \preceq 011 \preceq 111</math> значения равны <math>1, 1, 1, 0</math>. Одного спуска <math>1 \to 0</math> достаточно, чтобы заключить <math>f \notin M</math>.]]

			Конспект: [[Дискретная математика]]

СВ: Новая страница: «{{Определение |definition= Пусть $\widetilde \alpha^n = (\alpha_1,...,\alpha_n)$, $\widetilde\beta^n = (\beta_1,...,\beta_n)$, $\alpha_i,\beta_i\i...»

2026-10-25T10:39:45Z

Новая страница: «{{Определение |definition= Пусть $\widetilde \alpha^n = (\alpha_1,...,\alpha_n)$, $\widetilde\beta^n = (\beta_1,...,\beta_n)$, $\alpha_i,\beta_i\i...»

Новая страница

{{Определение
|definition=
Пусть $\widetilde \alpha^n = (\alpha_1,...,\alpha_n)$,
$\widetilde\beta^n = (\beta_1,...,\beta_n)$, $\alpha_i,\beta_i\in\{0,1\}$, $i=\overline{1,n}$.
}}

Говорят, что набор $\widetilde \alpha^n$ предшествует набору $\widetilde \beta^n$
(набор $\widetilde \beta^n$ следует после набора $\widetilde \alpha^n$)
и пишут $\widetilde \alpha^n\preceq \widetilde \beta^n$, если
<math>
\alpha_1\leq \beta_1,\quad\alpha_2\leq\beta_2,\quad...,\quad \alpha_n\leq\beta_n.
</math>

Будем говорить, что $\widetilde \alpha^n$ строго предшествует $\widetilde \beta^n$
и обозначать $\widetilde \alpha^n\prec \widetilde \beta^n$, если
$\widetilde \alpha^n\preceq \widetilde \beta^n$ и
$\widetilde \alpha^n\neq \widetilde \beta^n$.

Будем говорить, что $\widetilde \alpha^n$ непосредственно предшествует $\widetilde \beta^n$
и обозначать $\widetilde \alpha^n\prec' \widetilde \beta^n$,
если $\widetilde \alpha^n\prec \widetilde \beta^n$ и не существует набора $\widetilde \gamma^n$
такого, что $\widetilde \alpha^n\prec \widetilde \gamma^n \prec \widetilde \beta^n$.

{{Замечание
|content=
$\preceq$ {{---}} отношение частичного порядка.

$\prec$ {{---}} отношение строгого порядка.
}}
{{Определение
|definition=
Пусть $f(x_1,...,x_n)\in P_2$.
Функция $f$ называется монотонной, если
<math>\widetilde \alpha^n\preceq \widetilde \beta^n\quad \Longrightarrow \quad
f(\widetilde \alpha^n)\leq f(\widetilde \beta^n).
</math>
}}
Класс всех монотонных функций будем обозначать $M$.

{{Пример
|content=Функция $x$ является монотонной. Функция $\overline x$ {{---}} не монотонна.
}}
{{Теорема
|statement=Класс функций $M$ замкнут.
|proof=
Рассмотрим суперпозицию ранга 1 от функций из $M$.

a) Пусть $f(x_1,...,x_n)\in M$ и
<math>
g(x_1,...,x_{j-1},x_{j+1},...,x_n, y) = f(x_1,...,x_{j-1},y,x_{j+1},...,x_{n}).
</math>
Тогда монотонность $g$ непосредственно следует из монотонности функции $f$.

b) Пусть $f(x_1,...,x_n)\in M$ и $h(y_1, ...,y_m)\in M$ и
<math>
g(x_1,...,x_{j-1},x_{j+1},...,x_n, y_1,...,y_m) = f(x_1,...,x_{j-1},h(y_1,...,y_{m}),x_{j+1},...,x_{n}).
</math>
Пусть $\widetilde \alpha^{n+m-1}\preceq \widetilde \beta^{n+m-1}$.
Тогда, в частности,
<math>(\alpha_{n},...,\alpha_{n+m-1})\preceq (\beta_{n},...,\beta_{n+m-1}).</math>
Поскольку $h$ монотонна, то
<math>h(\alpha_{n},...,\alpha_{n+m-1})\leq h(\beta_{n},...,\beta_{n+m-1})</math>
и, следовательно,
<math>
(\alpha_1,...,\alpha_{j-1}, h(\alpha_{n},...,\alpha_{n+m-1}), \alpha_{j},...,\alpha_{n-1})
\preceq
(\beta_1,...,\beta_{j-1}, h(\beta_{n},...,\beta_{n+m-1}), \beta_{j},...,\beta_{n-1}).
</math>

Таким образом, из монотонности $f$ следует, что
<math>
g(\widetilde \alpha^{n+m-1}) = f(\alpha_1,...,\alpha_{j-1},
h(\alpha_{n},...,\alpha_{n+m-1}), \alpha_{j},...,\alpha_{n-1})\leq
</math>
<math>
\leq f(\beta_1,...,\beta_{j-1}, h(\beta_{n},...,\beta_{n+m-1}), \beta_{j},...,\beta_{n-1})
= g(\widetilde \beta^{n+m-1}).
</math>
Получаем, что $g(x_1,...,x_{j-1},x_{j+1},...,x_n, y_1,...,y_m)\in M$.
Таким образом, $[M] = M$.
}}
{{Замечание
|content=
Тождественная функция $f(x)=x$ лежит в классе $M$.

Функция отрицания $f(x) = \overline x$ не лежит в $M$.

Таким образом, $M\neq \varnothing$ и $M\neq P_2$.
}}
{{Лемма
|about=О немонотонной функции
|statement=
Пусть $f(x_1,...,x_n)\notin M$.
Тогда, подставляя в $f$ вместо аргументов $0$, $1$, $x$
можно получить $\overline x$.
|proof=
Так как $f\notin M$, существуют два набора $\widetilde\alpha^n$ и $\widetilde\beta^n$,
такие что $\widetilde\alpha^n\preceq \widetilde\beta^n$ и
$f(\widetilde\alpha^n) \gt f(\widetilde\beta^n)$.
Очевидно, что
$f(\widetilde\alpha^n)= 1$ и $f(\widetilde\beta^n)=0$.
Пусть $\widetilde\alpha^n$ отличен от $\widetilde\beta^n$ в $t$ позициях.

a) Пусть $t=1$. Тогда $\widetilde\alpha^n \prec' \widetilde\beta^n$ для некоторого $i$ верно, что
<math>
\widetilde\alpha^n = (\alpha_1,...,\alpha_{i-1},0,\alpha_{i+1},...,\alpha_n)
</math>
и
<math>
\widetilde\beta^n = (\alpha_1,...,\alpha_{i-1},1,\alpha_{i+1},...,\alpha_n).
</math>
Определим функцию $\varphi(x)$ следующим образом:
<math>
\varphi(x) = f(\alpha_1,...,\alpha_{i-1},x,\alpha_{i+1},...,\alpha_n).
</math>
Тогда:
<math>
\varphi(0) = f(\alpha_1,...,\alpha_{i-1},0,\alpha_{i+1},...,\alpha_n)=1
</math>
<math>
\varphi(1) = f(\alpha_1,...,\alpha_{i-1},1,\alpha_{i+1},...,\alpha_n)=0.
</math>
То есть $\varphi(x) = \overline x$, что и требовалось доказать.

b) Пусть теперь $t \gt 1$. В этом случае построим последовательность наборов
<math>
\widetilde\alpha^n = \widetilde\gamma^n(0) \prec \widetilde\gamma^n(1) \prec ...
\prec \widetilde\gamma^n(t-1) \prec \widetilde\gamma^n(t) = \widetilde\beta^n,
</math>
где каждая пара наборов $\widetilde\gamma^n(i-1)$ и $\widetilde\gamma^n(i)$
отличаются только в одной позиции, $i=\overline{1,t}$.
Это не трудно сделать, последовательно заменяя каждую позицию, в которой наборы
$\widetilde\alpha^n$ и $\widetilde\beta^n$ различаются с нуля на единицу.
Поскольку $f(\widetilde\alpha^n)= 1$ и $f(\widetilde\beta^n)=0$,
найдется такое $k$, что $f(\widetilde\gamma^n(k-1))=1$ и $f(\widetilde\gamma^n(k))=0$.
Такая ситуация возвращает нас к пункту $a)$ доказательства.
}}

{{Пример
|content= '''Построение $\overline x$ с помощью немонотонной функции'''

Пусть $f(x,y,z) = x\supset (y\oplus z)$.
Эта функция немонотонна, так как
<math>
f(0,0,0) = 0\supset (0\oplus 0) = 1 \gt 0 = 1\supset (1\oplus 1) = f(1,1,1).
</math>
Рассмотрим последовательность наборов
<math>(0,0,0)\prec (0,0,1)\prec(0,1,1)\prec(1,1,1)</math>
и значения функции $f$ на этих наборах
<math>1=f(0,0,0)= f(0,0,1)= f(0,1,1) \gt f(1,1,1)=0.</math>

Тогда $\varphi(x) = f(x,1,1) = \overline x$.
Действительно,
<math>\varphi(x) = x\supset(1\oplus 1) = x\supset 0 = \overline x</math>.
}}

[[Файл:p43-01-monotone-chain-descent.svg|frame|none|900px|alt=Булев куб с выделенной цепочкой 000—001—011—111 и значениями 1, 1, 1, 0|Рис. 1. Монотонность проверяется вдоль цепочек: на цепочке <math>000 \preceq 001 \preceq 011 \preceq 111</math> значения равны <math>1, 1, 1, 0</math>. Одного спуска <math>1 \to 0</math> достаточно, чтобы заключить <math>f \notin M</math>.]]

Монотонные функции - История изменений

СВ в 10:39, 25 октября 2026

СВ: Новая страница: «{{Определение |definition= Пусть $\widetilde \alpha^n = (\alpha_1,...,\alpha_n)$, $\widetilde\beta^n = (\beta_1,...,\beta_n)$, $\alpha_i,\beta_i\i...»