Разложение Шеннона

В математике разложением Шеннона или декомпозицией Шеннона по переменной $x_i$ называется метод представления булевой функции от $n$ переменных в виде суммы двух подфункций от $(n-1)$ остальных переменных. Хотя этот метод часто приписывают Клоду Шеннону, но Буль доказал его гораздо раньше, а сама возможность такого разложения по любой из переменной непосредственно вытекает из возможности определения любой булевой функции с помощью таблицы истинности.

Разложение

Разложение Шеннона по переменной $x_i$ основано на том, что таблицу истинности для булевой функции от $n$ бинарных переменных можно разбить на две части таким образом, чтобы в первой части оказались только те входные комбинации, в которых переменная $x_i$ всегда принимает значение $1$, а во второй части остались только те входные комбинации, в которых переменная $x_i$ всегда принимает значение $0$ (а её инвертированное значение $\overline{x_i}$ принимает значение $1$). В результате становится справедливым следующее тождество, называемое разложением Шеннона:

$f(x)=x_i\cdot f_{x_i}(x)+\overline{x_i}\cdot f_{\overline{x_i}}(x)=(\overline{x_i}+f_{x_i}(x))\cdot (x_i+f_{\overline{x_i}}(x))$

где $f(x)$ является разлагаемой булевой функцией, $x_i$ и $\overline{x_i}$ являются неинвертированным и инвертированным значением переменной, по которой производится разложение, а $f_{x_i}(x)$ и $f_{\overline{x_i}}(x)$ являются соответственно положительным и отрицательным дополнением для функции $f(x)$ по переменной $x_i$. В разложении Шеннона знаками $\cdot$ и $+$ обозначены операции конъюнкции («И», AND) и дизъюнкции («ИЛИ», OR) соответственно, но тождество остается справедливым и при замене дизъюнкции на строгую дизъюнкцию (сложение по модулю 2, исключающее «ИЛИ», XOR), так как слагаемые никогда не принимают истинное значение одновременно (поскольку положительное дополнение $f_{x_i}(x)$ объединено конъюнкцией с $x_i$, а отрицательное дополнение $f_{\overline{x_i}}(x)$ объединено конъюнкцией с его инверсией $\overline{x_i}$).

Положительное дополнение $f_{x_i}(x)$ определяется той частью таблицы истинности, в которой переменная $x_i$ всегда принимает значение $1$ (а её инвертированное значение $\overline{x_i}$ принимает значение $0$):

$f_{x_i}(x)=f(x_1,\mathrm{...},x_{i-1},1,x_{i+1},\mathrm{...},x_n)$

Отрицательное дополнение $f_{\overline{x_i}}(x)$ определяется оставшейся частью таблицы, в которой переменная $x_i$ всегда принимает значение $0$ (а инвертированное значение $\overline{x_i}$ принимает значение $1$):

$f_{\overline{x_i}}(x)=f(x_1,\mathrm{...},x_{i-1},0,x_{i+1},\mathrm{...},x_n)$

Теорема разложения Шеннона при всей своей очевидности является важной идеей в булевой алгебре для представления булевых функций в виде бинарных диаграмм решений, решения задачи выполнимости булевых формул и реализации множества других техник, относящихся к компьютерной инженерии и формальной верификации цифровых схем.

В статье «The Synthesis of Two-Terminal Switching Circuits» Шеннон описал разложение функции по переменной $x_1$ как:

$f(x_1,x_2,\dots ,x_n)=x_1\cdot f(1,x_2,\dots ,x_n)+\overline{x_1}\cdot f(0,x_2,\dots ,x_n)$

с последующим разложением по двум переменным, и отметил, что разложение может быть продолжено по любому количеству переменных.

Пример разложения

Пусть дана булева функция от трех переменных $x$, $y$ и $z$, записанная в виде совершенной дизъюнктивной нормальной формы, то есть в виде дизъюнкции элементарных конъюнкций, каждая из которых содержит в одинаковом порядке каждую переменную или её дополнение (инверсию):

$f=x\cdot y\cdot z+x\cdot \bar{y}\cdot z+\bar{x}\cdot \bar{y}\cdot z+\bar{x}\cdot y\cdot z+\bar{x}\cdot \bar{y}\cdot \bar{z}$

Для разложения по переменной $x$ эту функцию можно переписать в виде суммы:

$f=x\cdot g_x+\bar{x}\cdot g_{\bar{x}}$

получив разложение булевой функции $f$ по переменной $x$ путём простого применения свойства дистрибутивности для переменной $x$ и её дополнения (инверсии) $x^{\prime }$:

$f=x(y\cdot z+\bar{y}\cdot z)+\bar{x}(\bar{y}\cdot z+y\cdot z+\bar{y}\cdot \bar{z})$

Аналогично выполняется разложение функции $f$ по переменной $y$ или $z$:

$f=y(x\cdot z+\bar{x}\cdot z)+\bar{y}(x\cdot z+\bar{x}\cdot z+\bar{x}\cdot \bar{z})$

$f=z(x\cdot y+x\cdot \bar{y}+\bar{x}\cdot \bar{y}+\bar{x}\cdot \bar{y})+\bar{z}(\bar{x}\cdot \bar{y})$

В свою очередь для каждой из оставшихся функций от меньшего числа переменных можно продолжить разложение по одной из оставшихся переменных.

Обобщение

В качестве переменной при разложении булевой функции могут выступать не только отдельные переменные, входящие в эту функцию, но любое мультиплексирующее условие. Например известноШаблон:Нет АИ разложение по выражению (x > y) и его отрицанию.

См. также

• Булева алгебра
• Математика

Ссылки

• Shannon’s Decomposition Example with multiplexers.
• Optimizing Sequential Cycles Through Shannon Decomposition and Retiming (PDF) Paper on application.