Теорема консенсуса

Переменные входы			Значения функций
х	и	С	$xy\vee {\bar {x}}z\vee yz$	$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

Карно Карта АБ ∨ А С ∨ до нашей эры . Отсутствие красного прямоугольника не приводит к изменению покрытой области.

В булевой алгебре — теорема консенсуса или правило консенсуса. это личность:

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

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

Конъюнктивно- двойственное этому уравнению:

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

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

${\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}}$

Консенсус

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

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

Приложения

В булевой алгебре повторный консенсус является основой одного алгоритма вычисления канонической формы Блейка формулы.

В цифровой логике включение в схему консенсусного термина может устранить опасность гонки .

История

Понятие консенсуса было введено Арчи Блейком в 1937 году и связано с канонической формой Блейка . Он был заново открыт Самсоном и Миллсом в 1954 году. и Куайна в 1955 году. Куайн ввел термин «консенсус». Робинсон использовал его в статьях 1965 года как основу своего « принципа разрешения ».

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

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