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

В математике разложением Шеннона или декомпозицией Шеннона по переменной $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},...,x_{i-1},1,x_{i+1},...,x_{n})$

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

$f_{\overline {x_{i}}}(x)=f(x_{1},...,x_{i-1},0,x_{i+1},...,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 {\overline {y}}\cdot z+{\overline {x}}\cdot {\overline {y}}\cdot z+{\overline {x}}\cdot y\cdot z+{\overline {x}}\cdot {\overline {y}}\cdot {\overline {z}}$

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

$f=x\cdot g_{x}+{\overline {x}}\cdot g_{\overline {x}}$

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

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

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

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

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

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

Обобщение

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

См. также

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

Ссылки

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