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

Перейти к навигации Перейти к поиску
Строка 22: Строка 22:
'''Деревья Шеннона'''
'''Деревья Шеннона'''


Пусть 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>, которая задается следующим образом
Пусть 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>, которая задается следующим образом


fxi(α0, ... ,αi-1, ai, αi+1, …, αn-1) = f(α0, ... ,αi-1, 1, αi+1, …, αn-1).
<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>.


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


Каждая булева функция может быть подвергнута декомпозиции при помощи теоремы расширения Шеннона:
Каждая булева функция может быть подвергнута декомпозиции при помощи теоремы расширения Шеннона:
Источник — http://pco.iis.nsk.su/wega/index.php/Бинарный_граф_решений