4551
правка
Бинарный граф решений: различия между версиями
Перейти к навигации
Перейти к поиску
→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 22: | Строка 22: | ||
'''Деревья Шеннона''' | '''Деревья Шеннона''' | ||
Пусть f – булева функция на области определения {0,1}<math>^n</math>. Ассоциируем n размерностей с переменными <math>x_0, ..., x_{n-1}</math>. Тогда [[положительный сомножитель|положительным сомножителем]] f относительно <math>x_i</math>, обозначаемым <math>f_{ | Пусть f – булева функция на области определения {0,1}<math>^n</math>. Ассоциируем n размерностей с переменными <math>x_0, ..., x_{n-1}</math>. Тогда [[положительный сомножитель|положительным сомножителем]] f относительно <math>x_i</math>, обозначаемым <math>f_{xi}</math>, является функция на области определения {0,1}<math>^n</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. | ||
Каждая булева функция может быть подвергнута декомпозиции при помощи теоремы расширения Шеннона: | Каждая булева функция может быть подвергнута декомпозиции при помощи теоремы расширения Шеннона: | ||