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

В математике разложением Шеннона или декомпозицией Шеннона по переменной $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»^[1] Шеннон описал разложение функции по переменной $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}})

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

Обобщение

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

См. также

Примечания

↑ Shannon, Claude E. The Synthesis of Two-Terminal Switching Circuits (англ.) // Bell System Technical Journal^[англ.] : journal. — Vol. 28. — P. 59—98.

Ссылки

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

[1] Shannon, Claude E. The Synthesis of Two-Terminal Switching Circuits (англ.) // Bell System Technical Journal^[англ.] : journal. — Vol. 28. — P. 59—98.

[1]