В математике разложением Шеннона или декомпозицией Шеннона по переменной называется метод представления булевой функции от переменных в виде суммы двух подфункций от остальных переменных. Хотя этот метод часто приписывают Клоду Шеннону, но Буль доказал его гораздо раньше, а сама возможность такого разложения по любой из переменной непосредственно вытекает из возможности определения любой булевой функции с помощью таблицы истинности.
Разложение Шеннона по переменной основано на том, что таблицу истинности для булевой функции от бинарных переменных можно разбить на две части таким образом, чтобы в первой части оказались только те входные комбинации, в которых переменная всегда принимает значение , а во второй части остались только те входные комбинации, в которых переменная всегда принимает значение (а её инвертированное значение принимает значение ). В результате становится справедливым следующее тождество, называемое разложением Шеннона:
где является разлагаемой булевой функцией, и являются неинвертированным и инвертированным значением переменной, по которой производится разложение, а и являются соответственно положительным и отрицательным дополнением для функции по переменной . В разложении Шеннона знаками и обозначены операции конъюнкции («И», AND) и дизъюнкции («ИЛИ», OR) соответственно, но тождество остается справедливым и при замене дизъюнкции на строгую дизъюнкцию (сложение по модулю 2, исключающее «ИЛИ», XOR), так как слагаемые никогда не принимают истинное значение одновременно (поскольку положительное дополнение объединено конъюнкцией с , а отрицательное дополнение объединено конъюнкцией с его инверсией ).
Положительное дополнение определяется той частью таблицы истинности, в которой переменная всегда принимает значение (а её инвертированное значение принимает значение ):
Отрицательное дополнение определяется оставшейся частью таблицы, в которой переманная всегда принимает значение (а инвертированное значение принимает значение ):
Теорема разложения Шеннона при всей своей очевидности является важной идеей в булевой алгебре для представления булевых функций в виде бинарных диаграмм решений, решения задачи выполнимости булевых формул и реализации множества других техник, относящихся к компьютерной инженерии и формальной верификации цифровых схем.
В статье «The Synthesis of Two-Terminal Switching Circuits»[1] Шеннон описал разложение функции по переменной как:
с последующим разложением по двум переменным, и отметил, что разложение может быть продолжено по любому количеству переменных.
Пусть дана булева функция от трех переменных , и , записанная в виде совершенной дизъюнктивной нормальной формы, то есть в виде дизъюнкции элементарных конъюнкций, каждая из которых содержит в одинаковом порядке каждую переменную или её дополнение (инверсию):
Для разложения по переменной эту функцию можно переписать в виде суммы:
получив разложение булевой функции по переменной путём простого применения свойства дистрибутивности для переменной и её дополнения (инверсии) :
Аналогично выполняется разложение функции по переменной или :
В свою очередь для каждой из оставшихся функций от меньшего числа переменных можно продолжить разложение по одной из оставшихся переменных.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .