- Разложение Шеннона
-
В математике, разложением Шеннона или декомпозицией Шеннона по переменной
называется метод представления булевой функции от
переменных в виде суммы двух подфункций от
остальных переменных. Хотя этот метод часто приписывают Клоду Шеннону, но Буль доказал его гораздо раньше, а сама возможность такого разложения по любой из переменной непосредственно вытекает из возможности определения любой булевой функции с помощью таблицы истинности.
Содержание
Разложение
Разложение Шеннона по переменной
основано на том, что таблицу истинности для булевой функции от
бинарных переменных можно разбить на две части таким образом, чтобы в первой части оказались только те входные комбинации, в которых переменная
всегда принимает значение
, а во второй части остались только те входные комбинации, в которых переменная
всегда принимает значение
(а её инвертированное значение
принимает значение
). В результате становится справедливым следующее тождество, называемое разложением Шеннона:
где
является разлагаемой булевой функцией,
и
являются неинвертированным и инвертированным значением переменной, по которой производится разложение, а
и
являются соответственно положительным и отрицательным дополнением для функции
по переменной
. В разложении Шеннона знаками
и
обозначены операции конъюнкции («И», AND) и дизъюнкции («ИЛИ», OR) соответственно, но тождество остается справедливым и при замене дизъюнкции на строгую дизъюнкцию (сложение по модулю 2, исключающее «ИЛИ», XOR), так как слагаемые никогда не принимают истинное значение одновременно (поскольку положительное дополнение
объединено конъюнкцией с
, а отрицательное дополнение
объединено конъюнкцией с его инверсией
).
Положительное дополнение
определяется той частью таблицы истинности, в которой переманная
всегда принимает значение
(а её инвертированное значение
принимает значение
):
Отрицательное дополнение
определяется оставшейся частью таблицы, в которой переманная
всегда принимает значение
(а инвертированное значение
принимает значение
):
Теорема разложения Шеннона при всей своей очевидности является важной идеей в булевой алгебре для представления булевых функций в виде бинарных диаграмм решений, решения задачи выполнимости булевых формул и реализации множества других техник, относящихся к компьютерной инженерии и формальной верификации цифровых схем.
В статье "The Synthesis of Two-Terminal Switching Circuits"[1] Шеннон описал разложение функции по переменной
как:
с последующим разложением по двум переменным, и отметил, что разложение может быть продолжено по любому количеству переменных.
Пример разложения
Пусть дана булева функция от трех переменных
,
и
, записанная в виде совершенной дизъюнктивной нормальной формы, т.е. в виде дизъюнкции элементарных конъюнкций, каждая из которых содержит в одинаковом порядке каждую переменную или её дополнение (инверсию):
Для разложения по переменной
эту функцию можно переписать в виде суммы:
получив разложение булевой функции
по переменной
путем простого применения свойства дистрибутивности для переменной
и её дополнения (инверсии)
:
Аналогично выполняется разложение функции
по переменной
или
:
В свою очередь для каждой из оставшихся функций от меньшего числа переменных можно продолжить разложение по одной из оставшихся переменных.
См. также
References
- ↑ Shannon, Claude E.. «The Synthesis of Two-Terminal Switching Circuits». Bell System Technical Journal 28: 59–98.
Ссылки
- Shannon’s Decomposition Example with multiplexers.
- Optimizing Sequential Cycles Through Shannon Decomposition and Retiming (PDF) Paper on application.
Категория:- Булева алгебра
Wikimedia Foundation. 2010.