4551
правка
Бинарный граф решений: различия между версиями
Перейти к навигации
Перейти к поиску
→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 30: | Строка 30: | ||
Каждая булева функция может быть подвергнута декомпозиции при помощи теоремы расширения Шеннона: | Каждая булева функция может быть подвергнута декомпозиции при помощи теоремы расширения Шеннона: | ||
<math>f(x_1, ... , x_n) = x_i \cdot f_{xi} + x'_i f_{ | <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 принимает при присваивании. | ||