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

ПОИСК ПО САЙТУ | о проекте

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

Разложение

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

где является разлагаемой булевой функцией, и являются неинвертированным и инвертированным значением переменной, по которой производится разложение, а и являются соответственно положительным и отрицательным дополнением для функции по переменной . В разложении Шеннона знаками и обозначены операции конъюнкции («И», AND) и дизъюнкции («ИЛИ», OR) соответственно, но тождество остается справедливым и при замене дизъюнкции на строгую дизъюнкцию (сложение по модулю 2, исключающее «ИЛИ», XOR), так как слагаемые никогда не принимают истинное значение одновременно (поскольку положительное дополнение объединено конъюнкцией с , а отрицательное дополнение объединено конъюнкцией с его инверсией ).

Положительное дополнение определяется той частью таблицы истинности, в которой переменная всегда принимает значение (а её инвертированное значение принимает значение ):

Отрицательное дополнение определяется оставшейся частью таблицы, в которой переманная всегда принимает значение (а инвертированное значение принимает значение ):

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

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

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

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

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

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

получив разложение булевой функции по переменной путём простого применения свойства дистрибутивности для переменной и её дополнения (инверсии) :

Аналогично выполняется разложение функции по переменной или :

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

См. также

Примечания

  1. Shannon, Claude E. “The Synthesis of Two-Terminal Switching Circuits”. Bell System Technical Journal. 28: 59—98.

Ссылки

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2025
WikiSort.ru - проект по пересортировке и дополнению контента Википедии