Русская Википедия:Разложение Шеннона
В математике разложением Шеннона или декомпозицией Шеннона по переменной <math>x_i</math> называется метод представления булевой функции от <math>n</math> переменных в виде суммы двух подфункций от <math>(n - 1)</math> остальных переменных. Хотя этот метод часто приписывают Клоду Шеннону, но Буль доказал его гораздо раньше, а сама возможность такого разложения по любой из переменной непосредственно вытекает из возможности определения любой булевой функции с помощью таблицы истинности.
Разложение
Разложение Шеннона по переменной <math>x_i</math> основано на том, что таблицу истинности для булевой функции от <math>n</math> бинарных переменных можно разбить на две части таким образом, чтобы в первой части оказались только те входные комбинации, в которых переменная <math>x_i</math> всегда принимает значение <math>1</math>, а во второй части остались только те входные комбинации, в которых переменная <math>x_i</math> всегда принимает значение <math>0</math> (а её инвертированное значение <math>\overline{x_i}</math> принимает значение <math>1</math>). В результате становится справедливым следующее тождество, называемое разложением Шеннона:
- <math>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))</math>
где <math>f(x)</math> является разлагаемой булевой функцией, <math>x_i</math> и <math>\overline{x_i}</math> являются неинвертированным и инвертированным значением переменной, по которой производится разложение, а <math>f_Шаблон:X i(x)</math> и <math>f_{\overline{x_i}}(x)</math> являются соответственно положительным и отрицательным дополнением для функции <math>f(x)</math> по переменной <math>x_i</math>. В разложении Шеннона знаками <math>\cdot</math> и <math>+</math> обозначены операции конъюнкции («И», AND) и дизъюнкции («ИЛИ», OR) соответственно, но тождество остается справедливым и при замене дизъюнкции на строгую дизъюнкцию (сложение по модулю 2, исключающее «ИЛИ», XOR), так как слагаемые никогда не принимают истинное значение одновременно (поскольку положительное дополнение <math>f_Шаблон:X i(x)</math> объединено конъюнкцией с <math>x_i</math>, а отрицательное дополнение <math>f_{\overline{x_i}}(x)</math> объединено конъюнкцией с его инверсией <math>\overline{x_i}</math>).
Положительное дополнение <math>f_Шаблон:X i(x)</math> определяется той частью таблицы истинности, в которой переменная <math>x_i</math> всегда принимает значение <math>1</math> (а её инвертированное значение <math>\overline{x_i}</math> принимает значение <math>0</math>):
- <math>f_Шаблон:X i(x) = f(x_1,...,x_{i-1},1,x_{i+1},...,x_n)</math>
Отрицательное дополнение <math>f_{\overline{x_i}}(x)</math> определяется оставшейся частью таблицы, в которой переменная <math>x_i</math> всегда принимает значение <math>0</math> (а инвертированное значение <math>\overline{x_i}</math> принимает значение <math>1</math>):
- <math>f_{\overline{x_i}}(x) = f(x_1,...,x_{i-1},0,x_{i+1},...,x_n)</math>
Теорема разложения Шеннона при всей своей очевидности является важной идеей в булевой алгебре для представления булевых функций в виде бинарных диаграмм решений, решения задачи выполнимости булевых формул и реализации множества других техник, относящихся к компьютерной инженерии и формальной верификации цифровых схем.
В статье «The Synthesis of Two-Terminal Switching Circuits»[1] Шеннон описал разложение функции по переменной <math>x_1</math> как:
- <math>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)</math>
с последующим разложением по двум переменным, и отметил, что разложение может быть продолжено по любому количеству переменных.
Пример разложения
Пусть дана булева функция от трех переменных <math>x</math>, <math>y</math> и <math>z</math>, записанная в виде совершенной дизъюнктивной нормальной формы, то есть в виде дизъюнкции элементарных конъюнкций, каждая из которых содержит в одинаковом порядке каждую переменную или её дополнение (инверсию):
- <math> 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}</math>
Для разложения по переменной <math>x</math> эту функцию можно переписать в виде суммы:
- <math> f = x \cdot g_x + \overline{x} \cdot g_{\overline{x}}</math>
получив разложение булевой функции <math>f</math> по переменной <math>x</math> путём простого применения свойства дистрибутивности для переменной <math>x</math> и её дополнения (инверсии) <math>x'</math>:
- <math> f = x(y \cdot z + \overline{y} \cdot z) +
\overline{x}(\overline{y} \cdot z + y \cdot z + \overline{y} \cdot \overline{z})</math>
Аналогично выполняется разложение функции <math>f</math> по переменной <math>y</math> или <math>z</math>:
- <math> f = y(x \cdot z + \overline{x} \cdot z) +
\overline{y}(x \cdot z + \overline{x} \cdot z + \overline{x} \cdot \overline{z})</math>
- <math> 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})</math>
В свою очередь для каждой из оставшихся функций от меньшего числа переменных можно продолжить разложение по одной из оставшихся переменных.
Обобщение
В качестве переменной при разложении булевой функции могут выступать не только отдельные переменные, входящие в эту функцию, но любое мультиплексирующее условие. Например известноШаблон:Нет АИ разложение по выражению (x > y) и его отрицанию.
См. также
Примечания
Ссылки
- Shannon’s Decomposition Example with multiplexers.
- Optimizing Sequential Cycles Through Shannon Decomposition and Retiming (PDF) Paper on application.
