Теорема Булевого разложения - Booles expansion theorem - Wikipedia

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

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

Это было названо «фундаментальной теоремой булевой алгебры».^[1] Помимо теоретической важности, он проложил путь для диаграммы бинарных решений, решатели выполнимости и многие другие техники, относящиеся к компьютерная инженерия и формальная проверка цифровых схем.

Формулировка теоремы

Более явный способ формулировки теоремы:

${\displaystyle f(X_{1},X_{2},\dots ,X_{n})=X_{1}\cdot f(1,X_{2},\dots ,X_{n})+X_{1}'\cdot f(0,X_{2},\dots ,X_{n})}$

Вариации и последствия

XOR-форма

Утверждение также верно, когда дизъюнкция "+" заменяется на XOR оператор:

${\displaystyle f(X_{1},X_{2},\dots ,X_{n})=X_{1}\cdot f(1,X_{2},\dots ,X_{n})\oplus X_{1}'\cdot f(0,X_{2},\dots ,X_{n})}$

Двойная форма

Существует двойная форма расширения Шеннона (которая не имеет связанной формы XOR):

${\displaystyle f(X_{1},X_{2},\dots ,X_{n})=(X_{1}+f(0,X_{2},\dots ,X_{n}))\cdot (X_{1}'+f(1,X_{2},\dots ,X_{n}))}$

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

${\displaystyle {\begin{aligned}f(X_{1},X_{2})&=X_{1}\cdot f(1,X_{2})+X_{1}'\cdot f(0,X_{2})\\&=X_{1}X_{2}\cdot f(1,1)+X_{1}X_{2}'\cdot f(1,0)+X_{1}'X_{2}\cdot f(0,1)+X_{1}'X_{2}'\cdot f(0,0)\end{aligned}}}$

Точно так же применение двойной формы приводит к Произведение сумм (PoS) каноническая форма (с использованием закон распределительности из ${\displaystyle +}$ над ${\displaystyle \cdot }$):

${\displaystyle {\begin{aligned}f(X_{1},X_{2})&=(X_{1}+f(0,X_{2}))\cdot (X_{1}'+f(1,X_{2}))\\&=(X_{1}+X_{2}+f(0,0))\cdot (X_{1}+X_{2}'+f(0,1))\cdot (X_{1}'+X_{2}+f(1,0))\cdot (X_{1}'+X_{2}'+f(1,1))\end{aligned}}}$

Свойства кофакторов

Линейные свойства кофакторов:

Для булевой функции F который состоит из двух логических функций грамм и ЧАС верно следующее:

Если ${\displaystyle F=H'}$ тогда ${\displaystyle F_{x}=H'_{x}}$

Если ${\displaystyle F=G\cdot H}$ тогда ${\displaystyle F_{x}=G_{x}\cdot H_{x}}$

Если ${\displaystyle F=G+H}$ тогда ${\displaystyle F_{x}=G_{x}+H_{x}}$

Если ${\displaystyle F=G\oplus H}$ тогда ${\displaystyle F_{x}=G_{x}\oplus H_{x}}$

Характеристики unate-функций:

Если F это функция unate и...

Если F положительный единый тогда ${\displaystyle F=x\cdot F_{x}+F_{x'}}$

Если F отрицательное соединение, тогда ${\displaystyle F=F_{x}+x'\cdot F_{x'}}$

Операции с кофакторами

Логическая разница:

Логическая разница или логическая производная функции F относительно литерала x определяется как:

${\displaystyle {\frac {\partial F}{\partial x}}=F_{x}\oplus F_{x'}}$

Универсальная количественная оценка:

Универсальная количественная оценка F определяется как:

${\displaystyle \forall xF=F_{x}\cdot F_{x'}}$

Экзистенциальная количественная оценка:

Экзистенциальная количественная оценка F определяется как:

${\displaystyle \exists xF=F_{x}+F_{x'}}$

История

Джордж Буль представил это расширение как свое Предложение II «Расширять или развивать функцию, включающую любое количество логических символов», в своей Законы мысли (1854),^[2] и он «широко применялся Булем и другими логиками девятнадцатого века».^[3]

Клод Шеннон упомянул это разложение среди других булевых тождеств в статье 1948 г.^[4] и показал интерпретации идентичности коммутационной сети. В литературе по компьютерному дизайну и теории переключений личность часто ошибочно приписывается Шеннону.^[3]

Применение к коммутационным схемам

1. Диаграммы двоичных решений следуют из систематического использования этой теоремы
2. Любая логическая функция может быть реализована непосредственно в схема переключения используя иерархию основных мультиплексор повторным применением этой теоремы.

Примечания

1. Пол С. Розенблум, Элементы математической логики, 1950, с. 5
2. Джордж Буль, Исследование законов мышления: на которых основаны математические теории логики и вероятностей, 1854, с. 72 полный текст в Google Книгах
3. Фрэнк Маркхэм Браун, Булевы рассуждения: логика булевых уравнений, 2-е издание, 2003 г., стр. 42
4. Клод Шеннон, «Синтез двухполюсных коммутационных схем», Технический журнал Bell System 28:59–98, полный текст, п. 62

Смотрите также

• Разложение Рида – Мюллера

внешняя ссылка

• Разложение Шеннона Пример с мультиплексорами.
• Оптимизация последовательных циклов с помощью декомпозиции Шеннона и повторной синхронизации (PDF) Бумага по заявке.