Разложение функции по переменным

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

Введем следующее обозначение:

[math]\displaystyle{ x^{\sigma} = \left\{ \begin{array}{ll} x, & \sigma = 1,\\ \overline x, & \sigma=0. \end{array} \right. }[/math] Также будем говорить $x$ в степени $\sigma$, имея в виду запись $x^{\sigma}$ определенную выше.

Переменную с или без отрицания будем называть литералом.

Замечание

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

Теорема (разложение функции по параметрам):

Пусть $f(x_1,...,x_n)\in P_2$ и $1\leq m\leq n$. Тогда [math]\displaystyle{ 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]

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

Рассмотрим произвольный набор аргументов $(\alpha_1, ..., \alpha_n)$: $\alpha_i\in E_2 $, $i=\overline{1,n}$. Подставим этот набор в правую часть уравнения: [math]\displaystyle{ \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]\displaystyle{ =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$ левая и правая части формулы совпадают, что и требовалось доказать.

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

Рис. 1. Литерал [math]\displaystyle{ x^\sigma }[/math] равен [math]\displaystyle{ 1 }[/math] только при [math]\displaystyle{ x=\sigma }[/math], поэтому после подстановки [math]\displaystyle{ \alpha }[/math] в сумме остаётся одно ненулевое слагаемое. Для [math]\displaystyle{ f(x,y)=x\vee y }[/math]: при [math]\displaystyle{ x=1 }[/math] получается [math]\displaystyle{ 1 }[/math], при [math]\displaystyle{ x=0 }[/math] — [math]\displaystyle{ y }[/math]; в обоих случаях это [math]\displaystyle{ f(x,y) }[/math].

Пример

Пусть [math]\displaystyle{ f(x,y) = \overline x |(x\supset \overline y) }[/math].

Разложим функцию $f$ по переменной $x$. [math]\displaystyle{ f(x,y) = \overline x |(x\supset \overline y) = x f(1,y)\vee \overline x f(0,y) = }[/math] Подставим формулу на место функции $f$. [math]\displaystyle{ = x(0 |(1\supset \overline y))\vee \overline x (1 |(0\supset\overline y))= x }[/math]

Последнее равенство следует из того, что $(0

Пример

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

Выполним разложение $f$ по переменным $x$ и $z$. [math]\displaystyle{ 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]\displaystyle{ = \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]\displaystyle{ 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]

Замечание

Здесь и далее запись "$f\neq 0$" понимается в смысле эквивалентности формул.

То есть запись "$f\neq 0$" читается "$f$ не является тождественно ложной функцией", а запись "$f\neq 1$" — "$f$ не является тождественно истинной функцией" .

Аналогично записи "$f = 1$" и "$f = 0$" понимают как "$f$ — тождественно истинна" и "$f$ — тождественно ложна".

Доказательство. Разложим функцию $f$ по всем ее переменным согласно утверждению. [math]\displaystyle{ 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$, в этом выражении присутствует хотя бы один член.

Пример

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

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

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