Двойственные функции

Определение:

Пусть $f(x_1,...,x_n)\in P_2$. Двойственной функцией к функции $f$ называется $f^*(x_1,...,x_n) = \overline f(\overline x_1, ..., \overline x_n)$.

Пример

Пусть $f(x,y,z) = \overline{xy\vee z}$. Тогда [math]\displaystyle{ f^*(x,y,z) = \overline{\overline{\overline x\cdot \overline y\vee \overline z} } = \overline x\cdot \overline y \vee \overline z }[/math].

Пример

Пусть функция $f(x,y,z)$ задана таблицей.

Тогда, чтобы получить двойственную функцию, нужно перевернуть и инвертировать столбец значений:

[math]\displaystyle{ \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]

Рис. 1. Двойственная функция получается в два шага: столбец значений читается снизу вверх (инверсия аргументов), затем инвертируется. Сравните строки [math]\displaystyle{ 000 }[/math] и [math]\displaystyle{ 111 }[/math]: [math]\displaystyle{ f(0,0,0)=1 }[/math] переходит в [math]\displaystyle{ f^*(1,1,1)=0 }[/math].

Определение:

Функция $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)\}.$

Пример

Пусть $f = x\vee y$, $f^* = \overline{\overline x \vee \overline y} = xy$. $f\neq f^*$ и, следовательно, $f^*$ не является самодвойственной.

Пример

Пусть $f$ — функция голосования: [math]\displaystyle{ f(x,y,z) = xy\vee xz\vee yz. }[/math]

[math]\displaystyle{ 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]\displaystyle{ \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]

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

Это верно для любой самодвойственной функции.

Теорема (Принцип двойственности):

Пусть формула $\mathcal U = f(\mathcal U_1,...,\mathcal U_n)$ реализует функцию $F (x_1,...,x_m)$,

где $\mathcal U_i$ — формулы, реализующие [math]\displaystyle{ f_{i}(x_{j_1},...,x_{j_{k_i} }) }[/math], $i=\overline{1,n}$. Пусть [math]\displaystyle{ \mathcal U_i^* }[/math] — формулы реализующие [math]\displaystyle{ f_{i}^* }[/math], $i=\overline{1,n}$. Тогда формула

[math]\displaystyle{ \mathcal U^* = f^*(\mathcal U^*_1,...,\mathcal U^*_n) }[/math] реализует функцию [math]\displaystyle{ F^*(x_1,...,x_m) }[/math].

Доказательство:

[math]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ = \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]\displaystyle{ = \overline f(\overline {f^*}_{1}(x_{i_1},..., x_{i_{k_1} }),..., \overline {f^*}_{n}(x_{j_1},...,x_{j_{k_n} }))= }[/math] [math]\displaystyle{ = 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]\displaystyle{ 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^*)$.

[math]\displaystyle{ \blacksquare }[/math]

Пример

Пусть,

[math]\displaystyle{ F(x,y,z) = (x\equiv y)\supset(y | z)= f(f_1(x,y),f_2(y,z)). }[/math]

[math]\displaystyle{ \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]\displaystyle{ 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].

Следствие:

Пусть $f(x_1,...,x_n)$ задана формулой $\mathcal U$ над множеством функций $\{0,1, \neg, \vee,\wedge\}$. Тогда $f^*(x_1,...,x_n)$ задается формулой, полученной из $\mathcal U$ заменой: нулей на единицы, единиц на нули, конъюнкций на дизъюнкции, дизъюнкций на конъюнкции.

Доказательство:

Пусть $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]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ 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$.

[math]\displaystyle{ \blacksquare }[/math]

Пример

Пусть, $f(x,y,z) = 0\wedge x\wedge \overline y\vee 1\wedge y\wedge \overline z$.

Тогда,

[math]\displaystyle{ \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]

Пример

Пусть, $f(x,y,z) = (\overline{0\vee x})(y\vee \overline x z)$.

Тогда

[math]\displaystyle{ \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]

Теорема:

Класс функций $S$ замкнут.

Доказательство:

Рассмотрим суперпозицию ранга 1 от функций из $S$.

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

[math]\displaystyle{ \blacksquare }[/math]

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

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

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

Лемма (О несамодвойственной функции):

Пусть $f(x_1,...,x_n)\notin S$. Тогда, подставляя в $f$ вместо аргументов $x$ и $\overline x$ можно получить константу.

Доказательство:

Пусть $(\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]\displaystyle{ \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]\displaystyle{ = f(\alpha_1,...,\alpha_n) = f(1^{\alpha_1},...,1^{\alpha_n}) = \varphi(1). }[/math] Следовательно $\varphi(x)$ — константа.

[math]\displaystyle{ \blacksquare }[/math]

Пример

Пусть $f(x,y,z) = x\supset (y\oplus z)$. Это несамодвойственная функция,

поскольку [math]\displaystyle{ 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]\displaystyle{ \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]

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