Теорема Буля о расширении

---

Теорема Буля о расширении , часто называемая расширением или разложением Шеннона , представляет собой тождество : , где любая булева функция , является переменной, является дополнением и и с аргументом , установленным равным и соответственно.${\ Displaystyle F = х \ cdot F_ {x} + x '\ cdot F_ {x'}}$${\ Displaystyle F}$${\ Displaystyle х}$${\ Displaystyle х '}$${\ Displaystyle х}$${\ Displaystyle F_ {х}}$${\ Displaystyle F_ {х'}}$${\ Displaystyle F}$${\ Displaystyle х}$${\ Displaystyle 1}$${\ Displaystyle 0}$

Термины и иногда называют положительными и отрицательными кофакторами Шеннона соответственно по отношению к . Это функции, вычисляемые оператором ограничения и (см. оценку (логику) и частичное применение ).${\ Displaystyle F_ {х}}$${\ Displaystyle F_ {х'}}$${\ Displaystyle F}$${\ Displaystyle х}$${\ displaystyle \ operatorname {ограничение} (F, x, 0)}$${\ displaystyle \ operatorname {ограничение} (F, x, 1)}$

Ее назвали «основной теоремой булевой алгебры». ^[1] Помимо своей теоретической важности, он проложил путь к диаграммам бинарных решений (BDD), решателям выполнимости и многим другим методам, относящимся к вычислительной технике и формальной проверке цифровых схем. В таких инженерных контекстах (особенно в BDD) расширение интерпретируется как if-then-else , где переменная является условием, а кофакторы - ветвями ( когда истинно и, соответственно, когда ложно). ^[2]${\ Displaystyle х}$${\ Displaystyle F_ {х}}$${\ Displaystyle х}$${\ Displaystyle F_ {х'}}$${\ Displaystyle х}$

Повторное применение для каждого аргумента приводит к сумме произведений (SoP) канонической формы булевой функции . Например, для этого будет${\ Displaystyle е}$${\ Displaystyle п = 2}$

---