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

Разложение

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

${\displaystyle 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))}$

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

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

${\displaystyle f_{x_{i}}(x)=f(x_{1},...,x_{i-1},1,x_{i+1},...,x_{n})}$

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

${\displaystyle f_{\overline {x_{i}}}(x)=f(x_{1},...,x_{i-1},0,x_{i+1},...,x_{n})}$

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

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

${\displaystyle 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})}$

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

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

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

${\displaystyle 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}}}$

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

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

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

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

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

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

${\displaystyle 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}})}$

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

Обобщение

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

См. также

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

Примечания

Ссылки

• Example with multiplexers.
• Paper on application.