СВ в 19:52, 24 октября 2026

2026-10-24T19:52:18Z

← Предыдущая		Версия 19:52, 24 октября 2026
Строка 132:		Строка 132:
	По таблице, мы получили формулу, представляющую функцию.		По таблице, мы получили формулу, представляющую функцию.
	}}		}}

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

СВ: Новая страница: «{{Определение |definition=Введем следующее обозначение: $x^{\sigma} = \left\{ \begin{array}{ll} x, & \sigma = 1,\\ \ove...»$

2026-10-24T19:51:53Z

Новая страница: «{{Определение |definition=Введем следующее обозначение: <math> x^{\sigma} = \left\{ \begin{array}{ll} x, & \sigma = 1,\\ \ove...»

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

{{Определение
|definition=Введем следующее обозначение:
<math>
x^{\sigma} = \left\{
\begin{array}{ll}
x, & \sigma = 1,\\
\overline x, & \sigma=0.
\end{array}
\right.
</math>
Также будем говорить $x$ в степени $\sigma$, имея в виду запись $x^{\sigma}$ определенную выше.
Переменную с или без отрицания будем называть литералом.
}}

{{Замечание
|content=Как можно видеть из определения $x^\sigma = 1\qquad\Longleftrightarrow\qquad x=\sigma$.
}}

{{Теорема
|about=разложение функции по параметрам
|statement=Пусть $f(x_1,...,x_n)\in P_2$ и $1\leq m\leq n$. Тогда

<math>
f(x_1,...,x_m,x_{m+1},...,x_n) =
\bigvee_{\substack{(\sigma_1,...,\sigma_m): \sigma_i\in E_2 , i=\overline{1,m}}}
x_1^{\sigma_1} x_2^{\sigma_2} \cdots x_m^{\sigma_m} f(\sigma_1,...,\sigma_m, x_{m+1},...,x_n).
</math>
|proof=Рассмотрим произвольный набор аргументов $(\alpha_1, ..., \alpha_n)$:
$\alpha_i\in E_2 $, $i=\overline{1,n}$. Подставим этот набор в правую часть уравнения:
<math>
\bigvee_{\substack{(\sigma_1,...,\sigma_m):\\ \sigma_i\in E_2 , i=\overline{1,m}}}
\alpha_1^{\sigma_1} \alpha_2^{\sigma_2} \cdots \alpha_m^{\sigma_m} f(\sigma_1,...,\sigma_m,
\alpha_{m+1},...,\alpha_n)=
</math>

Так как $\alpha^{\sigma}=1$ тогда и только тогда, когда $\alpha=\sigma$, то из всех
членов предыдущего выражения останется только один: когда все $\sigma_i$ совпадают с $\alpha_i$.
<math>
=1\cdot 1\cdots 1\cdot f(\alpha_1, ..., \alpha_m, \alpha_{m+1}, ..., \alpha_n) = f(\alpha_1, ..., \alpha_m, \alpha_{m+1}, ..., \alpha_n).
</math>

Таким образом, мы показали, что для произвольного набора значений аргументов функции $f$
левая и правая части формулы совпадают, что и требовалось доказать.
}}

[[Файл:p36-01-decomposition-by-variable.svg|frame|none|900px|alt=Разложение f(x, y) = x·f(1, y) ∨ ¬x·f(0, y): при x = 1 остаётся первое слагаемое и f = 1, при x = 0 — второе и f = y|Рис. 1. Литерал <math>x^\sigma</math> равен <math>1</math> только при <math>x=\sigma</math>, поэтому после подстановки <math>\alpha</math> в сумме остаётся одно ненулевое слагаемое. Для <math>f(x,y)=x\vee y</math>: при <math>x=1</math> получается <math>1</math>, при <math>x=0</math> — <math>y</math>; в обоих случаях это <math>f(x,y)</math>.]]

{{Пример
|content=Пусть <math>f(x,y) = \overline x |(x\supset \overline y)</math>.
Разложим функцию $f$ по переменной $x$.
<math>
f(x,y) = \overline x |(x\supset \overline y) = x f(1,y)\vee \overline x f(0,y) =
</math>
Подставим формулу на место функции $f$.
<math>
= x(0 |(1\supset \overline y))\vee \overline x (1 |(0\supset\overline y))= x
</math>
Последнее равенство следует из того, что $(0 | \alpha)=1$ для любого $\alpha$,
в то время как $(0\supset \beta)=1$ для любого $\beta$ и, следовательно,
<math>(1 |(0\supset\overline y))=(1 | 1)=0</math>.
}}
{{Пример
|content=Пусть $f(x,y,z)=\overline{(x\supset y)\oplus z}$.
Выполним разложение $f$ по переменным $x$ и $z$.
<math>
f(x,y,z) =
\bigvee_{\substack{(\sigma_1,\sigma_3):\\ \sigma_1\in E_2 , \sigma_3\in E_2 }}
x^{\sigma_1}z^{\sigma_3}f(\sigma_1, y, \sigma_3) = \\
=x^0 z^0 f(0,y,0)\vee x^0 z^1 f(0,y,1)\vee x^1 z^0 f(1,y,0)\vee x^1 z^1 f(1,y,1)=
\overline x \overline z \overline{(0\supset y)\oplus 0} \vee \overline x z \overline{(0\supset y)\oplus 1} \vee x \overline z \overline{(1\supset y)\oplus 0}
\vee x z \overline{(1\supset y)\oplus 1}=
</math>
Таким получилось разложение по переменным. Теперь можно
провести преобразования, чтобы упростить результат.
<math>
=
\overline x \overline z \overline{1\oplus 0} \vee
\overline x z \overline{1\oplus 1} \vee
x \overline z \overline{(1\supset y)\oplus 0} \vee
x z \overline{(1\supset y)\oplus 1}= \overline x z \vee
x \overline z \overline{y} \vee
x z y.
</math>
}}

Пусть $f(x_1, ..., x_n)\in P_2$ и $f\neq 0$. Тогда
<math>
f(x_1,...,x_n) = \bigvee_{\substack{(\sigma_1,...,\sigma_n)\in E_2 ^n\\f(\sigma_1,...,\sigma_n)=1}} x_1^{\sigma_1}\cdots x_n^{\sigma_n}.
</math>

{{Замечание
|content=Здесь и далее запись "$f\neq 0$" понимается в смысле эквивалентности формул.
То есть запись "$f\neq 0$" читается "$f$ не является тождественно ложной функцией", а запись "$f\neq 1$" {{---}} "$f$ не является тождественно истинной функцией" .
Аналогично записи "$f = 1$" и "$f = 0$" понимают как "$f$ {{---}} тождественно истинна" и "$f$ {{---}} тождественно ложна".
}}

'''Доказательство.'''
Разложим функцию $f$ по всем ее переменным согласно утверждению.
<math>
f(x_1,...,x_n) = \bigvee_{\substack{(\sigma_1,...,\sigma_n)\in E_2 ^n\\f(\sigma_1,...,\sigma_n)=1}} x_1^{\sigma_1}\cdots x_n^{\sigma_n}\cdot f(\sigma_1,...,\sigma_n) =
\bigvee_{\substack{(\sigma_1,...,\sigma_n)\in E_2 ^n\\f(\sigma_1,...,\sigma_n)=1}} x_1^{\sigma_1}\cdots x_n^{\sigma_n}.
</math>
Поскольку $f\neq 0$, в этом выражении присутствует хотя бы один член.

{{Пример
|content=Пусть функция $f(x,y,z)\in P_2$ задана в виде таблицы:

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

Теперь мы можем построить разложение функции по утверждению

<math>
f(x,y,z) = \bigvee_{\substack{(\sigma_1,\sigma_2,\sigma_3)\\ \sigma_i\in E_2 , i=\overline{1,3}}}
x^{\sigma_1} y^{\sigma_2} z^{\sigma_3}=
x^0 y^1 z^0 \vee x^1 y^0 z^1 \vee x^1 y^1 z^1 =
\overline x y \overline z \vee x \overline y z \vee x y z.
</math>

По таблице, мы получили формулу, представляющую функцию.
}}

Разложение функции по переменным - История изменений

СВ в 19:52, 24 октября 2026

СВ: Новая страница: «{{Определение |definition=Введем следующее обозначение: x^{\sigma} = \left\{ \begin{array}{ll} x, & \sigma = 1,\\ \ove...»

СВ: Новая страница: «{{Определение |definition=Введем следующее обозначение: $x^{\sigma} = \left\{ \begin{array}{ll} x, & \sigma = 1,\\ \ove...»$