Аноним

Бинарный граф решений: различия между версиями

Материал из WEGA
Строка 26: Строка 26:
<math>f_{xi}( \alpha_0, ... , \alpha_{i-1}, \alpha_i, \alpha_{i+1}, ..., \alpha_{n-1}) = f( \alpha_0, ... ,\alpha_{i-1}, 1, \alpha_{i+1}, ..., \alpha_{n-1}) \, </math>.
<math>f_{xi}( \alpha_0, ... , \alpha_{i-1}, \alpha_i, \alpha_{i+1}, ..., \alpha_{n-1}) = f( \alpha_0, ... ,\alpha_{i-1}, 1, \alpha_{i+1}, ..., \alpha_{n-1}) \, </math>.


Отрицательный сомножитель относительно <math>x_i</math>, обозначаемый <math>f_xi’</math>, определяется точно так же, только на правой стороне вместо 1 стоит 0.
[[Отрицательный сомножитель]] относительно <math>x_i</math>, обозначаемый <math>f_xi’</math>, определяется точно так же, только на правой стороне вместо 1 стоит 0.


Каждая булева функция может быть подвергнута декомпозиции при помощи теоремы расширения Шеннона:
Каждая булева функция может быть подвергнута декомпозиции при помощи теоремы расширения Шеннона:


f(x1, ... , xn) = xi • fxi + x'i fx’i
<math>f(x_1, ... , x_n) = x_i \cdot f_{xi} + x'_i f_{x’i}</math>
 
Это наблюдение можно использовать для представления f в виде дерева Шеннона – полного бинарного дерева [6, приложение B.5] высоты n, в котором каждый путь в вершину-лист определяет полное присваивание n переменным, над которыми определена функция f; а вершина-лист содержит значение 0 или 1 в зависимости от значения, которое f принимает при присваивании.
Это наблюдение можно использовать для представления f в виде дерева Шеннона – полного бинарного дерева [6, приложение B.5] высоты n, в котором каждый путь в вершину-лист определяет полное присваивание n переменным, над которыми определена функция f; а вершина-лист содержит значение 0 или 1 в зависимости от значения, которое f принимает при присваивании.
Дерево Шеннона нельзя назвать достаточно удобным представлением, поскольку высота дерева, представляющего любую булеву функцию на {0,1}<math>^n</math>, равна n, так что дерево имеет 2n листьев. Дерево Шеннона можно уменьшить при помощи слияния изоморфных поддеревьев и пренебрежения вершинами, имеющими идентичных потомков. На первый взгляд, использование сокращенного дерева Шеннона тоже не особенно практично, поскольку оно включает создание на первом этапе полного бинарного дерева. Более того, пока неясно, как можно на сокращенном дереве Шеннона эффективно производить такие операции, как проверка эквивалентности или вычисление конъюнкции функций, представленных в виде сокращенных деревьев Шеннона.
Дерево Шеннона нельзя назвать достаточно удобным представлением, поскольку высота дерева, представляющего любую булеву функцию на {0,1}<math>^n</math>, равна n, так что дерево имеет 2n листьев. Дерево Шеннона можно уменьшить при помощи слияния изоморфных поддеревьев и пренебрежения вершинами, имеющими идентичных потомков. На первый взгляд, использование сокращенного дерева Шеннона тоже не особенно практично, поскольку оно включает создание на первом этапе полного бинарного дерева. Более того, пока неясно, как можно на сокращенном дереве Шеннона эффективно производить такие операции, как проверка эквивалентности или вычисление конъюнкции функций, представленных в виде сокращенных деревьев Шеннона.
4551

правка