St001214 в 12:05, 25 ноября 2021

2021-11-25T12:05:37Z

← Предыдущая		Версия 12:05, 25 ноября 2021
Строка 229:		Строка 229:
	Действительно, <math>\varphi(x) = \overline x\supset(x\oplus \overline x) = \overline x\supset 1 = 1</math>.		Действительно, <math>\varphi(x) = \overline x\supset(x\oplus \overline x) = \overline x\supset 1 = 1</math>.
	}}		}}

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

СВ: Новая страница: «{{Определение |definition= Функция $f(x_1, ..., x_n)\in P_2$ {{---}} самодвойственная, если $f^*(x_1, ..., x...»$

2021-11-04T13:25:29Z

Новая страница: «{{Определение |definition= Функция <math>f(x_1, ..., x_n)\in P_2</math> {{---}} самодвойственная, если <math>f^*(x_1, ..., x...»

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

{{Определение
|definition=
Функция <math>f(x_1, ..., x_n)\in P_2</math> {{---}} самодвойственная, если <math>f^*(x_1, ..., x_n) = f(x_1, ..., x_n)</math>.
}}
Множество всех самодвойственных функций обозначим за <math>S</math>:
<math>S = \{ f | f(x_1, ..., x_n) \in P_2, f^*(x_1, ..., x_n) = f(x_1, ..., x_n) \}</math>.
{{Пример
|num=1
|content=
Пусть <math>f = x\vee y</math>, <math>f^* = \overline{\overline x \vee \overline y} = xy</math>.

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

Функция голосования {{---}} самодвойственная.
}}
Табличный вид функции голосования:
{|class="wikitable"
! 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
|}

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

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

Пусть <math>\mathcal U_i^*</math> {{---}} формулы реализующие <math>f_{i}^*</math>, <math>i=\overline{1,n}</math>.

Тогда формула <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>

Тогда, по определению двойственной функции <br />
<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}}))
</math>
<math>
= 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)</math> формулой имеет вид <math>\mathcal U^* = f^*(\mathcal U_1^*, ..., \mathcal U_n^*)</math>.
}}
{{Пример
|num=3
|content=
Пусть <math>F(x,y,z) = (x\equiv y)\supset(y~|~z)= f(f_1(x,y),f_2(y,z))</math>, <br />
<math>f^*(x,y) = (x\supset y)^* = \overline{\overline x\supset\overline y}= \overline{x\vee \overline y} = \overline x y</math>, <br />
<math>f_1^*(x,y) = (x\equiv y)^* = \overline{\overline x\equiv \overline y} = \overline{x\equiv y} = x\oplus y</math>, <br />
<math>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>F^*(x,y,z)</math> будет иметь вид
<math>F^*(x,y,z) = f^*(f_1^*(x,y),f_2^*(y,z)) = \overline{(x\oplus y)}\wedge (y\downarrow z)</math>.

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

Тогда <math>f_0^* = \overline{\overline{\overline x}} = \overline x = f_0</math>.

Следовательно, <math>f^* = f_0^*(f_1^*) = f_0(f_1^*) = \neg f_1^*</math>.

Пусть <math>f = f_1\vee f_2</math>. Другими словами, <math>f = f_0(f_1,f_2)</math>, <math>f_0(x,y) = x\vee y</math>.

Тогда <math>f_0^* = \overline{\overline x \vee \overline y} = x\wedge y</math> и
<math>f^* = f_0^*(f_1^*, f_2^*) = f_1^*\wedge f_2^*</math>.

Пусть <math>f = f_1\wedge f_2</math>. Другими словами, <math>f = f_0(f_1,f_2)</math>, <math>f_0(x,y) = x\wedge y</math>.

Тогда <math>f_0^* = \overline{\overline x \wedge \overline y} = x\vee y</math> и <math>f^* = f_0^*(f_1^*, f_2^*) = f_1^*\vee f_2^*</math>.

Пусть <math>f = 0</math>. Тогда <math>f^* = 1</math>.

Пусть <math>f=1</math>. Тогда <math>f^* = 0</math>.

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

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

Тогда
<math>f^*(x,y,z) = \neg((\overline{0\vee \overline x})(\overline y\vee \overline{\overline x}\wedge \overline z))</math>
<math>=\neg(1\wedge x)(\overline y\vee x\wedge \overline z))</math>
<math>=(\overline{1\wedge x})\vee(\overline{\overline y\vee x\wedge \overline z}))</math>
<math>=(\overline{1\wedge x})\vee(y\wedge ( \overline x\vee z)))</math>.
}}

== Замкнутость класса ==

{{Утверждение
|statement=
Класс функций <math>S</math> замкнут.
|proof=
Рассмотрим суперпозицию ранга 1 от функций из <math>S</math>.

a) Пусть <math>f(x_1,...,x_n)\in S</math> и <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) </math>
<math>= \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})</math>
<math>= 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>.

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

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

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

Таким образом, <math>[S] = S</math>.
}}
{{Замечание
|content=
Тождественная функция $f(x)=x$ лежит в классе $S$.

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

Таким образом, $S\neq \varnothing$ и $S\neq P_2$.
}}
{{Лемма
|about=о несамодвойственной функции
|statement=
Пусть <math>f(x_1, ..., x_n) \notin S</math>. Тогда, подставляя в <math>f</math> вместо аргументов переменные <math>x</math> и их отрицание <math>\overline x</math>, можно получить константу.
|proof=
Пусть <math>(\alpha_1,...,\alpha_n)</math>, <math>\alpha_i\in\{0,1\}</math>, такой набор, что <math>f(\alpha_1,...,\alpha_n) = f(\overline \alpha_1,...,\overline\alpha_n)</math>.
Такой набор обязан существовать в силу несамодвойственности функции <math>f</math>.

Рассмотрим функцию <math>\varphi(x) = f(x^{\alpha_1}, ..., x^{\alpha_n})</math>.

Тогда
<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=
Получение константы из несамодвойственной функции

Пусть <math>f(x,y,z) = x\supset (y\oplus z)</math>.

Это несамодвойственная функция, поскольку <math>f(0,1,0) = 0\supset (1\oplus 0) =1= 1\supset (0\oplus 1) =f(1,0,1)</math>.

Тогда <math>\varphi(x) = f(\overline x, x, \overline x)</math> {{---}} константа.

Действительно, <math>\varphi(x) = \overline x\supset(x\oplus \overline x) = \overline x\supset 1 = 1</math>.
}}

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

St001214 в 12:05, 25 ноября 2021

СВ: Новая страница: «{{Определение |definition= Функция f(x_1, ..., x_n)\in P_2 {{---}} самодвойственная, если f^*(x_1, ..., x...»

СВ: Новая страница: «{{Определение |definition= Функция $f(x_1, ..., x_n)\in P_2$ {{---}} самодвойственная, если $f^*(x_1, ..., x...»$