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

2026-10-25T10:33:53Z

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

2026-10-25T10:32:42Z

← Предыдущая		Версия 10:32, 25 октября 2026
Строка 408:		Строка 408:
	</math>		</math>
	}}		}}

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

СВ: Новая страница: «{{Определение |definition= Пусть $f(x_1,...,x_n)\in P_2$. Двойственной функцией к функции $f$ называется $f^...»

2026-10-25T10:32:17Z

Новая страница: «{{Определение |definition= Пусть $f(x_1,...,x_n)\in P_2$. Двойственной функцией к функции $f$ называется $f^...»

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

{{Определение
|definition=
Пусть $f(x_1,...,x_n)\in P_2$.
Двойственной функцией к функции $f$ называется $f^*(x_1,...,x_n) = \overline f(\overline x_1, ..., \overline x_n)$.
}}

{{Пример
|content=
Пусть $f(x,y,z) = \overline{xy\vee z}$. Тогда
<math>f^*(x,y,z) = \overline{\overline{\overline x\cdot \overline y\vee \overline z} } = \overline x\cdot \overline y \vee \overline z</math>.
}}
{{Пример
|content=
Пусть функция $f(x,y,z)$ задана таблицей.
Тогда, чтобы получить двойственную функцию, нужно перевернуть и инвертировать столбец значений:

<math>
\begin{array}{ccc|cc}
x & y & z & f(x,y,z) & f^*(x,y,z)\\
\hline
\begin{array}{c}
0\\
0\\
0\\
0\\
1\\
1\\
1\\
1\\
\end{array}
&
\begin{array}{c}
0\\
0\\
1\\
1\\
0\\
0\\
1\\
1\\
\end{array}
&
\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1\\
\end{array}
&
\begin{array}{c}
1\\
1\\
1\\
0\\
1\\
0\\
0\\
1\\
\end{array}
&
\begin{array}{c}
0\\
1\\
1\\
0\\
1\\
0\\
0\\
0\\
\end{array}
\end{array}
</math>
}}

[[Файл:p42-01-dual-reverse-invert.svg|frame|none|900px|alt=Таблица истинности с прямым и обратным порядком строк, столбцом f* и проверкой самодвойственности|Рис. 1. Двойственная функция получается в два шага: столбец значений читается снизу вверх (инверсия аргументов), затем инвертируется. Сравните строки <math>000</math> и <math>111</math>: <math>f(0,0,0)=1</math> переходит в <math>f^*(1,1,1)=0</math>.]]

{{Определение
|definition=
Функция $f(x_1,...,x_n)\in P_2$ {{---}} самодвойственная, если $f^*(x_1,...,x_n) = f(x_1,...,x_n)$.
}}
Обозначим за $S$ множество всех самодвойственных функций: $S = \{f | f(x_1,...,x_n)\in P_2, f^*(x_1,...,x_n) = f(x_1,...,x_n)\}.$

{{Пример
|content=
Пусть $f = x\vee y$, $f^* = \overline{\overline x \vee \overline y} = xy$. $f\neq f^*$ и, следовательно, $f^*$ не является самодвойственной.
}}
{{Пример
|content=
Пусть $f$ {{---}} функция голосования: <math>f(x,y,z) = xy\vee xz\vee yz.</math>

<math>
f^*(x,y,z) =
\overline{\overline x\cdot \overline y
\vee \overline x\cdot \overline z
\vee \overline y\cdot \overline z}
=
\overline{\overline x\cdot \overline y}
\cdot \overline{\overline x\cdot \overline z}
\cdot \overline{\overline y\cdot \overline z}
= (x\vee y)(x\vee z)(y\vee z) = (x\vee xz\vee xy\vee yz)(y\vee z)=
xy\vee xz \vee xyz \vee xz \vee xy\vee xyz \vee yz \vee yz =
xy \vee xz \vee yz \vee xyz =
= xy \vee xz \vee yz = f(x,y,z).
</math>

Функция голосования {{---}} самодвойственная.

Рассмотрим табличный вид функции голосования:

<math>
\begin{array}{ccc|c}
x & y & z & f(x,y,z) \\
\hline
\begin{array}{c}
0\\
0\\
0\\
0\\
1\\
1\\
1\\
1\\
\end{array}
&
\begin{array}{c}
0\\
0\\
1\\
1\\
0\\
0\\
1\\
1\\
\end{array}
&
\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1\\
\end{array}
&
\begin{array}{c}
0\\
0\\
0\\
1\\
0\\
1\\
1\\
1\\
\end{array}
\end{array}.
</math>

Можно видеть, что нижняя половина столбца значений
повторяет перевернутую и инвертированную верхнюю.
Это верно для любой самодвойственной функции.
}}

{{Теорема
|about=Принцип двойственности
|statement=Пусть формула $\mathcal U = f(\mathcal U_1,...,\mathcal U_n)$ реализует функцию $F (x_1,...,x_m)$,
где $\mathcal U_i$ {{---}} формулы, реализующие <math>f_{i}(x_{j_1},...,x_{j_{k_i} })</math>, $i=\overline{1,n}$.
Пусть <math>\mathcal U_i^*</math> {{---}} формулы реализующие <math>f_{i}^*</math>, $i=\overline{1,n}$.
Тогда формула
<math>\mathcal U^* = f^*(\mathcal U^*_1,...,\mathcal U^*_n)</math> реализует функцию <math>F^*(x_1,...,x_m)</math>.
|proof=
<math>F(x_1,...,x_m) =
f(f_{1}(x_{i_1},...,x_{ i_{k_1} }),...,f_{n}(x_{j_1},...,x_{ j_{k_n} })).</math>
Тогда, по определению двойственной функции
<math>
F^* (x_1,...,x_m) =
\overline f(f_{1}(\overline x_{i_1},...,\overline x_{i_{k_1} }),...,
f_{n}(\overline x_{j_1},...,\overline x_{j_{k_n} }))=
</math>
<math>
=
\overline f(\overline {\overline f}_{1}(\overline x_{i_1},...,\overline x_{i_{k_1} }),...,
\overline {\overline f}_{n}(\overline x_{j_1},...,\overline x_{j_{k_n} }))=
</math>
<math>
=
\overline f(\overline {f^*}_{1}(x_{i_1},..., x_{i_{k_1} }),...,
\overline {f^*}_{n}(x_{j_1},...,x_{j_{k_n} }))=
</math>
<math>
=
f^*({f^*}_{1}(x_{i_1},..., x_{i_{k_1} }),...,
{f^*}_{n}(x_{j_1},...,x_{j_{k_n} })).
</math>

С другой стороны, формула $f^*(\mathcal U_1^*,...,\mathcal U_n^*)$ реализует функцию
<math>
f^*(f_{\mathcal U_1^*}(x_{i_1},..., x_{i_{k_1} }), ..., f_{\mathcal U_n^*} (x_{j_1},...,x_{j_{k_n} }))=
f^*({f^*}_{1}(x_{i_1},..., x_{i_{k_1} }),..., {f^*}_{n}(x_{j_1},...,x_{j_{k_n} })).
</math>

Таким образом, один из способов задать функцию $F^*(x_1,...,x_m)$ формулой имеет вид
$\mathcal U^* = f^*(\mathcal U_1^*,...,\mathcal U_n^*)$.
}}
{{Пример
|content=
Пусть,
<math>F(x,y,z) = (x\equiv y)\supset(y | z)= f(f_1(x,y),f_2(y,z)).</math>

<math>
\begin{align}
f^*(x,y) = &(x\supset y)^* = \overline{\overline x\supset\overline y}=
\overline{x\vee \overline y} = \overline x y.
\\
f_1^*(x,y) = &(x\equiv y)^* = \overline{\overline x\equiv \overline y} =
\overline{x\equiv y} = x\oplus y.
\\
f_2^*(x,y) = &(x | y)^* = \overline{\overline x | \overline y} =
\overline{x\vee y} = \overline x\wedge \overline y = x\downarrow y.
\end{align}
</math>

Тогда $F^*(x,y,z)$ будет иметь вид $F^*(x,y,z) = f^*(f_1^*(x,y),f_2^*(y,z)) = \overline{(x\oplus y)}\wedge (y\downarrow z).$
Действительно,
<math>
F^*(x,y,z) = \neg {((\overline x\equiv \overline y)\supset(\overline y | \overline z))}
= \neg (\overline{(x\equiv y)}\vee(y\vee z)) =
\overline{\overline{(x\equiv y)} }\wedge\overline{(y\vee z)} = \overline{(x\oplus y)}\wedge (y\downarrow z)
</math>.
}}
{{Следствие
|statement=Пусть $f(x_1,...,x_n)$ задана формулой $\mathcal U$ над множеством функций $\{0,1, \neg, \vee,\wedge\}$.
Тогда $f^*(x_1,...,x_n)$ задается формулой, полученной из $\mathcal U$ заменой: нулей на единицы, единиц на нули, конъюнкций на дизъюнкции, дизъюнкций на конъюнкции.
|proof=
Пусть $f=\neg f_1$. Это значит, что $f = f_0(f_1)$, где $f_0(x) = \overline x$.
Тогда $f_0^* = \overline{\overline{\overline x} } = \overline x = f_0$.
Следовательно
<math>f^* = f_0^*(f_1^*) = f_0(f_1^*) = \neg f_1^*.</math>

Пусть $f = f_1\vee f_2$. Другими словами, $f = f_0(f_1,f_2)$, $f_0(x,y) = x\vee y$.
Тогда $f_0^* = \overline{\overline x \vee \overline y} = x\wedge y$ и
<math>
f^* = f_0^*(f_1^*, f_2^*) = f_1^*\wedge f_2^*.
</math>

Пусть $f = f_1\wedge f_2$. Другими словами, $f = f_0(f_1,f_2)$, $f_0(x,y) = x\wedge y$.
Тогда $f_0^* = \overline{\overline x \wedge \overline y} = x\vee y$ и
<math>
f^* = f_0^*(f_1^*, f_2^*) = f_1^*\vee f_2^*.
</math>

Пусть $f = 0$. Тогда $f^* = 1$.

Пусть $f=1$. Тогда $f^* = 0$.

Пусть $f = x$. Тогда $f^* = \overline{\overline x}=x = f$.
}}
{{Пример
|content=
Пусть, $f(x,y,z) = 0\wedge x\wedge \overline y\vee 1\wedge y\wedge \overline z$.
Тогда,

<math>
\begin{align}
f^*&(x,y,z) = \overline f(\overline x, \overline y, \overline z) =
\neg(0\wedge \overline x\wedge\overline{\overline y}
\vee 1 \wedge \overline y\wedge \overline{ \overline z}) = \\
&=
\overline{(0\wedge \overline x\wedge y)}
\wedge\overline{(1 \wedge \overline y\wedge z)} =
(1 \vee x \vee \overline y)\wedge (0\vee y \vee \overline z).
\end{align}
</math>
}}
{{Пример
|content=
Пусть, $f(x,y,z) = (\overline{0\vee x})(y\vee \overline x z)$.
Тогда

<math>
\begin{align}
f^*&(x,y,z) = \neg((\overline{0\vee \overline x})(\overline y\vee
\overline{\overline x}\wedge \overline z))=
\neg(1\wedge x)(\overline y\vee x\wedge \overline z))=
\\
&=
(\overline{1\wedge x})\vee(\overline{\overline y\vee x\wedge \overline z}))=
(\overline{1\wedge x})\vee(y\wedge ( \overline x\vee z))).
\end{align}
</math>
}}
{{Теорема
|statement=Класс функций $S$ замкнут.
|proof=
Рассмотрим суперпозицию ранга 1 от функций из $S$.

a) Пусть $f(x_1,...,x_n)\in S$ и
<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>
Тогда
<math>
\overline g(\overline x_1,...,\overline x_{j-1},\overline x_{j+1},...,\overline x_n, \overline y) =
\overline f(\overline x_1,...,\overline x_{j-1},\overline y,\overline x_{j+1},...,\overline x_{n})=
</math>
<math>
=
f^*(x_1,...,x_{j-1},y,x_{j+1},...,x_{n}) =
f(x_1,...,x_{j-1},y,x_{j+1},...,x_{n})
=
</math>
<math>
= g(x_1,...,x_{j-1},x_{j+1},...,x_n, y).
</math>

Следовательно $g(x_1,...,x_{j-1},x_{j+1},...,x_n, y)\in S$.

b) Пусть $f(x_1,...,x_n)\in S$ и $h(y_1, ...,y_m)\in S$ и
$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>
\overline g(\overline x_1,...,\overline x_{j-1},
\overline x_{j+1},...,\overline x_n, \overline y_1,...,\overline y_m)
=
</math>
<math>
=
\overline f(\overline x_1,...,\overline x_{j-1},
h(\overline y_1,...,\overline y_{m}),\overline x_{j+1},...,\overline x_{n})=
</math>
<math>
=
\overline f(\overline x_1,...,\overline x_{j-1},
\overline{\overline h}(\overline y_1,...,\overline y_{m}),\overline x_{j+1},...,\overline x_{n})=
</math>
<math>
=
\overline f(\overline x_1,...,\overline x_{j-1},
\overline{ h^*}( y_1,...,y_{m}),\overline x_{j+1},...,\overline x_{n})=
</math>
<math>
=
f^*(x_1,..., x_{j-1},
{ h^*}( y_1,...,y_{m}), x_{j+1},..., x_{n})=
</math>
<math>
=
f(x_1,..., x_{j-1},
{ h}( y_1,...,y_{m}), x_{j+1},..., x_{n})=
</math>
<math>
=
g(x_1,...,x_{j-1},x_{j+1},...,x_n, y_1,...,y_m)
</math>

Получаем, что $g(x_1,...,x_{j-1},x_{j+1},...,x_n, y_1,...,y_m)\in S$.

Таким образом, $[S] = S$.
}}

Тождественная функция $f(x)=x$ лежит в классе $S$.

Конъюнкция $f(x) = x \wedge y$ не лежит в $S$.

Таким образом, $S\neq \varnothing$ и $S\neq P_2$.

{{Лемма
|about=О несамодвойственной функции
|statement=
Пусть $f(x_1,...,x_n)\notin S$.
Тогда, подставляя в $f$ вместо аргументов $x$ и $\overline x$ можно получить константу.
|proof=
Пусть $(\alpha_1,...,\alpha_n)$, $\alpha_i\in\{0,1\}$, такой набор, что
$f(\alpha_1,...,\alpha_n) = f(\overline \alpha_1,...,\overline\alpha_n)$.
Такой набор обязан существовать в силу несамодвойственности функции $f$.
Рассмотрим функцию $\varphi(x) = f(x^{\alpha_1},...,x^{\alpha_n})$.
Тогда
<math>
\varphi(0) = f(0^{\alpha_1},...,0^{\alpha_n}) =
f({\alpha_1}^0,...,{\alpha_n}^0) =
f(\overline\alpha_1,...,\overline \alpha_n) =
</math>
<math>
=
f(\alpha_1,...,\alpha_n) =
f(1^{\alpha_1},...,1^{\alpha_n}) = \varphi(1).
</math>
Следовательно $\varphi(x)$ {{---}} константа.
}}
{{Пример
|content=
Пусть $f(x,y,z) = x\supset (y\oplus z)$. Это несамодвойственная функция,
поскольку
<math>f(0,1,0) = 0\supset (1\oplus 0) =1= 1\supset (0\oplus 1) =f(1,0,1).</math>
Тогда $\varphi(x) = f(\overline x, x, \overline x)$ {{---}} константа.
Действительно,
<math>
\begin{align}
\varphi(x) = %f(\overline x, x, \overline x) =
\overline x\supset(x\oplus \overline x) =
\overline x\supset 1 = 1.
\end{align}
</math>
}}

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

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

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

СВ: Новая страница: «{{Определение |definition= Пусть $f(x_1,...,x_n)\in P_2$. Двойственной функцией к функции $f$ называется $f^...»