Теорема консенсуса - Consensus theorem

Переменные входы			Значения функций
Икс	у	z	${\displaystyle xy\vee {\bar {x}}z\vee yz}$	${\displaystyle xy\vee {\bar {x}}z}$
0	0	0	0	0
0	0	1	1	1
0	1	0	0	0
0	1	1	1	1
1	0	0	0	0
1	0	1	0	0
1	1	0	1	1
1	1	1	1	1

В Булева алгебра, то теорема о консенсусе или же правило консенсуса^[1] это личность:

${\displaystyle xy\vee {\bar {x}}z\vee yz=xy\vee {\bar {x}}z}$

В консенсус или же противовоспалительное средство условий ${\displaystyle xy}$ и ${\displaystyle {\bar {x}}z}$ является ${\displaystyle yz}$. Это соединение всех уникальных литералов терминов, за исключением литерала, который в одном термине не вводится, а в другом - отрицается. Если ${\displaystyle y}$ включает термин, который отрицается в ${\displaystyle z}$ (или наоборот), термин консенсуса ${\displaystyle yz}$ ложно; Другими словами, нет единого мнения.

Конъюнктив двойной этого уравнения:

${\displaystyle (x\vee y)({\bar {x}}\vee z)(y\vee z)=(x\vee y)({\bar {x}}\vee z)}$

Доказательство

${\displaystyle {\begin{aligned}xy\vee {\bar {x}}z\vee yz&=xy\vee {\bar {x}}z\vee (x\vee {\bar {x}})yz\\&=xy\vee {\bar {x}}z\vee xyz\vee {\bar {x}}yz\\&=(xy\vee xyz)\vee ({\bar {x}}z\vee {\bar {x}}yz)\\&=xy(1\vee z)\vee {\bar {x}}z(1\vee y)\\&=xy\vee {\bar {x}}z\end{aligned}}}$

Консенсус

В консенсус или же согласованный срок двух конъюнктивных членов дизъюнкции определяется, когда один член содержит буквальный ${\displaystyle a}$ а другой буквальный ${\displaystyle {\bar {a}}}$, оппозиция. Консенсус - это соединение двух терминов, исключая оба ${\displaystyle a}$ и ${\displaystyle {\bar {a}}}$, и повторяющиеся литералы. Например, консенсус ${\displaystyle {\bar {x}}yz}$ и ${\displaystyle w{\bar {y}}z}$ является ${\displaystyle w{\bar {x}}z}$.^[2] Консенсус не определен, если есть более одной оппозиции.

Для конъюнктивного двойственного правила консенсус ${\displaystyle y\vee z}$ может быть получено из ${\displaystyle (x\vee y)}$ и ${\displaystyle ({\bar {x}}\vee z)}$ сквозь разрешающая способность правило вывода. Это показывает, что LHS выводится из RHS (если А → B тогда А → AB; замена А с RHS и B с (у ∨ z)). RHS можно получить из LHS просто через устранение соединения правило вывода. Поскольку RHS → LHS и LHS → RHS (в пропозициональное исчисление ), то LHS = RHS (в булевой алгебре).

Приложения

В булевой алгебре повторяющийся консенсус - это ядро ​​одного алгоритма вычисления Каноническая форма Блейка формулы.^[2]

В цифровая логика, включение в схему согласованного члена может устранить гоночные опасности.^[3]

История

Концепция консенсуса была введена Арчи Блейком в 1937 году в связи с Каноническая форма Блейка.^[4] Он был вновь открыт Самсоном и Миллсом в 1954 году.^[5] и по Куайн в 1955 г.^[6] Куайн ввел термин «консенсус». Робинсон использовал его для статей 1965 г. как основу своего "принцип разрешения ".^[7][8]

Рекомендации

1. Фрэнк Маркхэм Браун, Булевы рассуждения: логика булевых уравнений, 2-е издание 2003 г., стр. 44
2. Фрэнк Маркхэм Браун, Булевы рассуждения: логика булевых уравнений, 2-е издание 2003 г., стр. 81 год
3. М. Рафикзаман, Основы цифровой логики и микроконтроллеров, 6-е издание (2014 г.), ISBN  1118855795, п. 75
4. «Канонические выражения в булевой алгебре», диссертация, факультет математики, Чикагский университет, 1937 г., обзор в J. C. C. McKinsey, Журнал символической логики 3: 2: 93 (июнь 1938) Дои:10.2307/2267634 JSTOR  2267634
5. Эдвард В. Самсон, Бертон Э. Миллс, Кембриджский исследовательский центр ВВС, технический отчет 54-21, апрель 1954 г.
6. Уиллард ван Орман Куайн, «Проблема упрощения функций истинности», Американский математический ежемесячный журнал 59:521-531, 1952 JSTOR  2308219
7. Джон Алан Робинсон, "Машинно-ориентированная логика, основанная на принципе разрешения", Журнал ACM 12:1: 23–41.
8. Дональд Эрвин Кнут, Искусство программирования 4А: Комбинаторные алгоритмы, часть 1, с. 539

дальнейшее чтение

• Рот, Чарльз Х. младший и Кинни, Ларри Л. (2004, 2010). «Основы логического проектирования», 6-е изд., С. 66ff.