|
|
| Строка 79: |
Строка 79: |
| [[Файл: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>.]] | | [[Файл: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>
| |
| }}
| |
|
| |
|
| Конспект: [[Дискретная математика]] | | Конспект: [[Дискретная математика]] |
