WikiSort.ru - Не сортированное

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

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

См. также

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

Примечания

Ссылки

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