Самодвойственные функции
Множество всех самодвойственных функций обозначим за [math]\displaystyle{ S }[/math]: [math]\displaystyle{ S = \{ f | f(x_1, ..., x_n) \in P_2, f^*(x_1, ..., x_n) = f(x_1, ..., x_n) \} }[/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} }[/math] [math]\displaystyle{ = \overline{\overline x\cdot \overline y} \cdot \overline{\overline x\cdot \overline z} \cdot \overline{\overline y\cdot \overline z} }[/math] [math]\displaystyle{ = (x\vee y)(x\vee z)(y\vee z) }[/math] [math]\displaystyle{ = (x\vee xz\vee xy\vee yz)(y\vee z) }[/math] [math]\displaystyle{ = xy\vee xz \vee xyz \vee xz \vee xy\vee xyz \vee yz \vee yz }[/math] [math]\displaystyle{ = xy \vee xz \vee yz \vee xyz }[/math] [math]\displaystyle{ = xy \vee xz \vee yz = f(x,y,z). }[/math]
Функция голосования — самодвойственная.Табличный вид функции голосования:
| x | y | z | f(x,y,z) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Нижняя половина столбца значений повторяет перевернутую и инвертированную верхнюю. Это верно для любой самодвойственной функции.
Принцип двойственности
где [math]\displaystyle{ \mathcal U_i }[/math] — формулы, реализующие [math]\displaystyle{ f_{i}(x_{j_1},...,x_{j_{k_i}}) }[/math], [math]\displaystyle{ i=\overline{1,n} }[/math].
Пусть [math]\displaystyle{ \mathcal U_i^* }[/math] — формулы реализующие [math]\displaystyle{ f_{i}^* }[/math], [math]\displaystyle{ i=\overline{1,n} }[/math].
Тогда формула [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}})) }[/math] [math]\displaystyle{ = 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) }[/math] формулой имеет вид [math]\displaystyle{ \mathcal U^* = f^*(\mathcal U_1^*, ..., \mathcal U_n^*) }[/math].
[math]\displaystyle{ f^*(x,y) = (x\supset y)^* = \overline{\overline x\supset\overline y}= \overline{x\vee \overline y} = \overline x y }[/math],
[math]\displaystyle{ f_1^*(x,y) = (x\equiv y)^* = \overline{\overline x\equiv \overline y} = \overline{x\equiv y} = x\oplus y }[/math],
[math]\displaystyle{ f_2^*(x,y) = (x~|~ y)^* = \overline{\overline x~|~\overline y} = \overline{x\vee y} = \overline x\wedge \overline y = x\downarrow y }[/math].
Тогда по принципу двойственности [math]\displaystyle{ F^*(x,y,z) }[/math] будет иметь вид [math]\displaystyle{ F^*(x,y,z) = f^*(f_1^*(x,y),f_2^*(y,z)) = \overline{(x\oplus y)}\wedge (y\downarrow z) }[/math].
Действительно, [math]\displaystyle{ F^*(x,y,z) = \neg {((\overline x\equiv \overline y)\supset(\overline y~|~\overline z))} }[/math] [math]\displaystyle{ = \neg (\overline{(x\equiv y)}\vee(y\vee z)) }[/math] [math]\displaystyle{ = \overline{\overline{(x\equiv y)}}\wedge\overline{(y\vee z)} }[/math]
[math]\displaystyle{ = \overline{(x\oplus y)}\wedge (y\downarrow z) }[/math].
Пусть [math]\displaystyle{ f=\neg f_1 }[/math]. Это значит, что [math]\displaystyle{ f = f_0(f_1) }[/math], где [math]\displaystyle{ f_0(x) = \overline x }[/math].
Тогда [math]\displaystyle{ f_0^* = \overline{\overline{\overline x}} = \overline x = f_0 }[/math].
Следовательно, [math]\displaystyle{ f^* = f_0^*(f_1^*) = f_0(f_1^*) = \neg f_1^* }[/math].
Пусть [math]\displaystyle{ f = f_1\vee f_2 }[/math]. Другими словами, [math]\displaystyle{ f = f_0(f_1,f_2) }[/math], [math]\displaystyle{ f_0(x,y) = x\vee y }[/math].
Тогда [math]\displaystyle{ f_0^* = \overline{\overline x \vee \overline y} = x\wedge y }[/math] и [math]\displaystyle{ f^* = f_0^*(f_1^*, f_2^*) = f_1^*\wedge f_2^* }[/math].
Пусть [math]\displaystyle{ f = f_1\wedge f_2 }[/math]. Другими словами, [math]\displaystyle{ f = f_0(f_1,f_2) }[/math], [math]\displaystyle{ f_0(x,y) = x\wedge y }[/math].
Тогда [math]\displaystyle{ f_0^* = \overline{\overline x \wedge \overline y} = x\vee y }[/math] и [math]\displaystyle{ f^* = f_0^*(f_1^*, f_2^*) = f_1^*\vee f_2^* }[/math].
Пусть [math]\displaystyle{ f = 0 }[/math]. Тогда [math]\displaystyle{ f^* = 1 }[/math].
Пусть [math]\displaystyle{ f=1 }[/math]. Тогда [math]\displaystyle{ f^* = 0 }[/math].
Пусть [math]\displaystyle{ f = x }[/math]. Тогда [math]\displaystyle{ f^* = \overline{\overline x}=x = f }[/math].
Тогда, [math]\displaystyle{ f^*(x,y,z) = \overline f(\overline x, \overline y, \overline z) }[/math] [math]\displaystyle{ =\neg(0\wedge \overline x\wedge\overline{\overline y} \vee 1 \wedge \overline y\wedge \overline{ \overline z}) }[/math] [math]\displaystyle{ = \overline{(0\wedge \overline x\wedge y)} \wedge\overline{(1 \wedge \overline y\wedge z)} }[/math]
[math]\displaystyle{ = (1 \vee x \vee \overline y)\wedge (0\vee y \vee \overline z) }[/math].
Тогда [math]\displaystyle{ f^*(x,y,z) = \neg((\overline{0\vee \overline x})(\overline y\vee \overline{\overline x}\wedge \overline z)) }[/math] [math]\displaystyle{ =\neg(1\wedge x)(\overline y\vee x\wedge \overline z)) }[/math] [math]\displaystyle{ =(\overline{1\wedge x})\vee(\overline{\overline y\vee x\wedge \overline z})) }[/math]
[math]\displaystyle{ =(\overline{1\wedge x})\vee(y\wedge ( \overline x\vee z))) }[/math].
Замкнутость класса
Рассмотрим суперпозицию ранга 1 от функций из [math]\displaystyle{ S }[/math].
a) Пусть [math]\displaystyle{ f(x_1,...,x_n)\in S }[/math] и [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) }[/math] [math]\displaystyle{ = \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}) }[/math] [math]\displaystyle{ = 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].
Следовательно [math]\displaystyle{ g(x_1,...,x_{j-1},x_{j+1},...,x_n, y)\in S }[/math].
b) Пусть [math]\displaystyle{ f(x_1,...,x_n)\in S }[/math] и [math]\displaystyle{ h(y_1, ...,y_m)\in S }[/math] и [math]\displaystyle{ g(x_1,...,x_{j-1},x_{j+1},...,x_n, y_1,...,y_m) }[/math] [math]\displaystyle{ =f(x_1,...,x_{j-1},h(y_1,...,y_{m}),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_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].
Получаем, что [math]\displaystyle{ g(x_1,...,x_{j-1},x_{j+1},...,x_n, y_1,...,y_m)\in S }[/math].
Таким образом, [math]\displaystyle{ [S] = S }[/math].
Конъюнкция $f(x) = x \wedge y$ не лежит в $S$.
Таким образом, $S\neq \varnothing$ и $S\neq P_2$.
Пусть [math]\displaystyle{ (\alpha_1,...,\alpha_n) }[/math], [math]\displaystyle{ \alpha_i\in\{0,1\} }[/math], такой набор, что [math]\displaystyle{ f(\alpha_1,...,\alpha_n) = f(\overline \alpha_1,...,\overline\alpha_n) }[/math]. Такой набор обязан существовать в силу несамодвойственности функции [math]\displaystyle{ f }[/math].
Рассмотрим функцию [math]\displaystyle{ \varphi(x) = f(x^{\alpha_1}, ..., x^{\alpha_n}) }[/math].
Тогда [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{ f(x,y,z) = x\supset (y\oplus z) }[/math].
Это несамодвойственная функция, поскольку [math]\displaystyle{ f(0,1,0) = 0\supset (1\oplus 0) =1= 1\supset (0\oplus 1) =f(1,0,1) }[/math].
Тогда [math]\displaystyle{ \varphi(x) = f(\overline x, x, \overline x) }[/math] — константа.
Действительно, [math]\displaystyle{ \varphi(x) = \overline x\supset(x\oplus \overline x) = \overline x\supset 1 = 1 }[/math].