Разложение Шеннона

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Разложение[править | править исходный текст]

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

f(x) = x_i \cdot f_{{x_i}}(x) + \overline{x_i} \cdot f_{\overline{x_i}}(x)

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

Положительное дополнение f_{{x_i}}(x) определяется той частью таблицы истинности, в которой переманная x_i всегда принимает значение 1 (а её инвертированное значение \overline{x_i} принимает значение 0):

f_{{x_i}}(x) = f(x_1,...,x_{i-1},1,x_{i+1},...,x_n)

Отрицательное дополнение f_{\overline{x_i}}(x) определяется оставшейся частью таблицы, в которой переманная x_i всегда принимает значение 0 (а инвертированное значение \overline{x_i} принимает значение 1):

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] Шеннон описал разложение функции по переменной x_1 как:

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)

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

Пример разложения[править | править исходный текст]

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

 f = xyz + xy'z + x'y'z + x'yz + x'y'z' \,

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

 f = xg_x + x'g_{x'} \,

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

 f = x(yz + y'z) + x'(y'z + yz + y'z') \,

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

 f = y(xz + x'z) + y'(xz + x'z + x'z') \,
 f = z(xy + xy' + x'y' + x'y) + z'(x'y') \,

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

См. также[править | править исходный текст]

References[править | править исходный текст]

  1. Shannon, Claude E.. «The Synthesis of Two-Terminal Switching Circuits». Bell System Technical Journal 28: 59–98.

Ссылки[править | править исходный текст]