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

Переменные входы			Значения функций
Икс	y	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 (х \ ви у) ({\ бар {х}} \ ви г) (у \ ви г) = (х \ ви у) ({\ бар {х}} \ ви г)}$

Доказательство [ править ]

${\ displaystyle {\ begin {align} 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} } г \ конец {выровнено}}}$

Консенсус [ править ]

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

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

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

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

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

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

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

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

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

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