Věta o konsensu - Consensus theorem - Wikipedia

Variabilní vstupy			Funkční hodnoty
X	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

v Booleova algebra, věta o shodě nebo pravidlo konsensu^[1] je identita:

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

The shoda nebo rozpouštědlo podmínek ${ displaystyle xy}$ a ${ displaystyle { bar {x}} z}$ je ${ displaystyle yz}$. Jedná se o spojení všech jedinečných literálů výrazů, s výjimkou literálu, který se v jednom výrazu jeví jako nezpracovaný a ve druhém negovaný. Li ${ displaystyle y}$ zahrnuje výraz, který je v ${ displaystyle z}$ (nebo naopak), termín konsensu ${ displaystyle yz}$ je nepravdivé; jinými slovy, neexistuje žádný konsenzuální termín.

Spojka dvojí této rovnice je:

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

Důkaz

${ displaystyle { begin {zarovnané} 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 {zarovnáno}}}$

Shoda

The shoda nebo konsensuální termín dvou spojovacích členů disjunkce je definováno, když jeden člen obsahuje doslovný ${ displaystyle a}$ a druhý doslovný ${ displaystyle { bar {a}}}$, an opozice. Konsenzus je spojení dvou termínů, přičemž oba jsou vynechány ${ displaystyle a}$ a ${ displaystyle { bar {a}}}$a opakované literály. Například shoda z ${ displaystyle { bar {x}} yz}$ a ${ displaystyle w { bar {y}} z}$ je ${ displaystyle w { bar {x}} z}$.^[2] Konsenzus není definován, pokud existuje více než jedna opozice.

Pro konjunktivní dvojí pravidlo, shoda ${ displaystyle y vee z}$ lze odvodit z ${ displaystyle (x vee y)}$ a ${ displaystyle ({ bar {x}} vee z)}$ skrz rozlišení pravidlo odvození. To ukazuje, že LHS je odvozitelný od RHS (pokud A → B pak A → AB; výměna A s RHS a B s (y ∨ z)). RHS lze odvodit z LHS jednoduše prostřednictvím eliminace spojky pravidlo odvození. Protože RHS → LHS a LHS → RHS (v výrokový kalkul ), pak LHS = RHS (v booleovské algebře).

Aplikace

V booleovské algebře je opakovaná shoda jádrem jednoho algoritmu pro výpočet Blake kanonická forma vzorce.^[2]

v digitální logika, včetně konsensuálního výrazu v obvodu, lze vyloučit závodní nebezpečí.^[3]

Dějiny

Koncept konsensu představil Archie Blake v roce 1937, vztahující se k Blake kanonická forma.^[4] To bylo nově objevené Samson a Mills v roce 1954^[5] a tím Quine v roce 1955.^[6] Quine vytvořil termín „konsenzus“. Robinson použil jej pro klauzule v roce 1965 jako základ svého „princip řešení ".^[7][8]

Reference

Další čtení

• Roth, Charles H. Jr. a Kinney, Larry L. (2004, 2010). „Základy logického designu“, 6. vydání, s. 1. 66ff.