Монотонные функции
Говорят, что набор $\widetilde \alpha^n$ предшествует набору $\widetilde \beta^n$
(набор $\widetilde \beta^n$ следует после набора $\widetilde \alpha^n$)
и пишут $\widetilde \alpha^n\preceq \widetilde \beta^n$, если
[math]\displaystyle{
\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$.
Функция $f$ называется монотонной, если
[math]\displaystyle{ \widetilde \alpha^n\preceq \widetilde \beta^n\quad \Longrightarrow \quad f(\widetilde \alpha^n)\leq f(\widetilde \beta^n). }[/math]Класс всех монотонных функций будем обозначать $M$.
Рассмотрим суперпозицию ранга 1 от функций из $M$.
a) Пусть $f(x_1,...,x_n)\in M$ и [math]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ (\alpha_{n},...,\alpha_{n+m-1})\preceq (\beta_{n},...,\beta_{n+m-1}). }[/math] Поскольку $h$ монотонна, то [math]\displaystyle{ h(\alpha_{n},...,\alpha_{n+m-1})\leq h(\beta_{n},...,\beta_{n+m-1}) }[/math] и, следовательно, [math]\displaystyle{ (\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]\displaystyle{ 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]\displaystyle{ \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$.
Функция отрицания $f(x) = \overline x$ не лежит в $M$.
Таким образом, $M\neq \varnothing$ и $M\neq P_2$.
Тогда, подставляя в $f$ вместо аргументов $0$, $1$, $x$
можно получить $\overline x$.Так как $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]\displaystyle{ \widetilde\alpha^n = (\alpha_1,...,\alpha_{i-1},0,\alpha_{i+1},...,\alpha_n) }[/math] и [math]\displaystyle{ \widetilde\beta^n = (\alpha_1,...,\alpha_{i-1},1,\alpha_{i+1},...,\alpha_n). }[/math] Определим функцию $\varphi(x)$ следующим образом: [math]\displaystyle{ \varphi(x) = f(\alpha_1,...,\alpha_{i-1},x,\alpha_{i+1},...,\alpha_n). }[/math] Тогда: [math]\displaystyle{ \varphi(0) = f(\alpha_1,...,\alpha_{i-1},0,\alpha_{i+1},...,\alpha_n)=1 }[/math] [math]\displaystyle{ \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]\displaystyle{ \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)$ доказательства.
Пусть $f(x,y,z) = x\supset (y\oplus z)$. Эта функция немонотонна, так как [math]\displaystyle{ f(0,0,0) = 0\supset (0\oplus 0) = 1 \gt 0 = 1\supset (1\oplus 1) = f(1,1,1). }[/math] Рассмотрим последовательность наборов [math]\displaystyle{ (0,0,0)\prec (0,0,1)\prec(0,1,1)\prec(1,1,1) }[/math] и значения функции $f$ на этих наборах [math]\displaystyle{ 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]\displaystyle{ \varphi(x) = x\supset(1\oplus 1) = x\supset 0 = \overline x }[/math].
Конспект: Дискретная математика