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

Переменные входы			Значения функции
х	и	С	$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

В булевой алгебре — теорема консенсуса или правило консенсуса. ^[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$ . ^[2] Консенсус не определен, если существует более одной оппозиции.

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

Приложения [ править ]

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

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

История [ править ]

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

Ссылки [ править ]

^ Фрэнк Маркхэм Браун [ d ] , Булево рассуждение: логика логических уравнений , 2-е издание 2003 г., стр. 44
^ Jump up to: Перейти обратно: ^а ^б Фрэнк Маркхэм Браун, Булево рассуждение: логика булевых уравнений , 2-е издание, 2003 г., стр. 81
^ Рафикуззаман, Мохамед (2014). Основы цифровой логики и микроконтроллеров (6-е изд.). п. 65. ИСБН 1118855795 .
^ «Канонические выражения в булевой алгебре», диссертация, факультет математики, Чикагский университет, 1937, ProQuest 301838818 , рецензия в JCC McKinsey, The Journal of Symbolic Logic 3 :2:93 (июнь 1938 г.) doi : 10.2307/2267634 JSTOR 2267634 . Функция консенсуса обозначается $\sigma$ и определено на стр. 29–31.
^ Эдвард В. Самсон, Бертон Э. Миллс, Кембриджский исследовательский центр ВВС, технический отчет 54-21, апрель 1954 г.
^ Уиллард ван Орман Куайн , «Проблема упрощения функций истинности», American Mathematical Monthly 59 : 521-531, 1952 JSTOR 2308219
^ Джон Алан Робинсон , «Машинно-ориентированная логика, основанная на принципе разрешения», Журнал ACM 12 : 1: 23–41.
^ Дональд Эрвин Кнут , Искусство компьютерного программирования 4A : Комбинаторные алгоритмы , часть 1, с. 539

Дальнейшее чтение [ править ]

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

[1] Фрэнк Маркхэм Браун [ d ] , Булево рассуждение: логика логических уравнений , 2-е издание 2003 г., стр. 44

[brown81-2] Jump up to: Перейти обратно: ^а ^б Фрэнк Маркхэм Браун, Булево рассуждение: логика булевых уравнений , 2-е издание, 2003 г., стр. 81

[3] Рафикуззаман, Мохамед (2014). Основы цифровой логики и микроконтроллеров (6-е изд.). п. 65. ИСБН 1118855795 .

[blake-4] «Канонические выражения в булевой алгебре», диссертация, факультет математики, Чикагский университет, 1937, ProQuest 301838818 , рецензия в JCC McKinsey, The Journal of Symbolic Logic 3 :2:93 (июнь 1938 г.) doi : 10.2307/2267634 JSTOR 2267634 . Функция консенсуса обозначается $\sigma$ и определено на стр. 29–31.

[5] Эдвард В. Самсон, Бертон Э. Миллс, Кембриджский исследовательский центр ВВС, технический отчет 54-21, апрель 1954 г.

[6] Уиллард ван Орман Куайн , «Проблема упрощения функций истинности», American Mathematical Monthly 59 : 521-531, 1952 JSTOR 2308219

[7] Джон Алан Робинсон , «Машинно-ориентированная логика, основанная на принципе разрешения», Журнал ACM 12 : 1: 23–41.

[8] Дональд Эрвин Кнут , Искусство компьютерного программирования 4A : Комбинаторные алгоритмы , часть 1, с. 539

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]