Полином Жегалкина. Пример.

Имеем следующую логическую функцию.

$f = xy\vee \bar{y}\bar{z}$. Преобразовать функцию так, чтобы она содержала две операции.

Вспомним таблицу истинности $\oplus$ и $\wedge$:

$x$ $y$ $x\oplus y$ $xy$
$0$ $0$ $0$ $0$
$0$ $1$ $1$ $0$
$1$ $0$ $1$ $0$
$1$ $1$ $0$ $1$

Составим таблицу истинности:

$x$ $y$ $z$ $\bar{y}$ $\bar{z}$ $xy$ $\bar{y}\bar{z}$ $f$
$0$ $0$ $0$ $1$ $1$ $0$ $1$ $1$
$0$ $0$ $1$ $1$ $0$ $0$ $0$ $0$
$0$ $1$ $0$ $0$ $1$ $0$ $0$ $0$
$0$ $1$ $1$ $0$ $0$ $0$ $0$ $0$
$1$ $0$ $0$ $1$ $1$ $0$ $1$ $1$
$1$ $0$ $1$ $1$ $0$ $0$ $0$ $0$
$1$ $1$ $0$ $0$ $1$ $1$ $0$ $1$
$1$ $1$ $1$ $0$ $0$ $1$ $0$ $1$

Запишем общий вид полинома Жегалкина $f = xy\vee \bar{y}\bar{z} = \overset{0}{a_{123}}xyz\oplus \overset{1}{a_{12}}xy\oplus \overset{0}{a_{13}}xz\oplus \overset{1}{a_{23}}yz\oplus \overset{0}{a_{1}}x\oplus \overset{1}{a_{2}}y\oplus \overset{1}{a_{3}}z\oplus \overset{1}{a_{0}} = xy\oplus yz\oplus y\oplus z\oplus 1 $

$f(0,0,0) = \overset{1}{a_{0}} = 1$

$f(0,0,1) = \overset{1}{a_{3}}\oplus \overset{1}{a_{0}} = 0$

$f(0,1,0) = \overset{1}{a_{2}}\oplus \overset{1}{a_{0}} = 0$

$f(0,1,1) = \overset{1}{a_{23}}\oplus \overset{1}{a_{2}}\oplus \overset{1}{a_{3}}\oplus \overset{1}{a_{0}} = 0$

$f(1,0,0) = \overset{0}{a_{1}}\oplus \overset{1}{a_{0}} = 1$

$f(1,0,1) = \overset{0}{a_{13}}\oplus \overset{0}{a_{1}}\oplus \overset{1}{a_{3}}\oplus \overset{1}{a_{0}} = 0$

$f(1,1,0) = \overset{1}{a_{12}}\oplus \overset{0}{a_{1}}\oplus \overset{1}{a_{2}}\oplus \overset{1}{a_{0}} = 1$

$f(1,1,1) = \overset{0}{a_{123}}\oplus \overset{1}{a_{12}}\oplus \overset{0}{a_{13}}\oplus \overset{1}{a_{23}}\oplus \overset{0}{a_{1}}\oplus \overset{1}{a_{2}}\oplus \overset{1}{a_{3}}\oplus \overset{1}{a_{0}} = 1$