Konsensus sætning

Inputvariabel			Funktionens værdi
$x$	$y$	$z$	$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

I boolsk algebra , den konsensus sætning eller konsensus regel er en boolesk identitet (som svarer til en ækvivalens på propositionslogik ). Det er en regel om forenkling af boolske udtryk, med andre som absorptionsreglen eller eliminationsreglen.

Stater

Den konsensus teorem eller konsensus regel er identitet:

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

I forenklingen af boolske formler reducerer vi den venstre del til den højre del med reglen:

xy \ vee {\ bar {x}} z \ vee yz \ rightarrow xy \ vee {\ overline {x}} z

Udtrykket kaldes konsensus eller opløsning af vilkår og . Konsensus om to sammenhænge af bogstaver er den sammenhæng, der fås fra alle bogstaver, der vises i dem, og eliminerer en af dem, der både synes at være negeret i den ene og ikke negeret i den anden. I den angivne identitet, hvis x er en bogstavelig, og hvis y og z repræsenterer sammenhænge af bogstaver, så er konsensus om og af god . $yz$ $xy$ ${\ overline {x}} z$ $xy$ ${\ bar {x}} z$ $yz$

Den dobbelte identitet er:

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

Opløseren udledes af de to adskillelser og af den såkaldte afskærings- eller opløsningsregel , deraf forenklingen. $(y \ vee z)$ $(x \ vee y)$ $({\ bar {x}} \ vee z)$

Demonstration

Identiteten kan verificeres ved hjælp af sandhedstabellen (angivet ovenfor). Det kan også demonstreres ud fra aksiomerne i den boolske algebra :

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

= (neutral og komplement)

xy \ vee {\ bar {x}} z \ vee (x \ vee {\ bar {x}}) yz

= (distribution)

xy \ vee {\ bar {x}} z \ vee xyz \ vee {\ bar {x}} yz

= (associativitet og kommutativitet)

xy \ vee xyz \ vee {\ bar {x}} z \ vee {\ bar {x}} yz

= ( absorption , to gange)

xy \ vee {\ bar {x}} z

Konsensus og konsensusreduktion

Den konsensus af to konjunktioner af litteraler er en disjunktion, denne disjunktion indeholder som første medlem af en af konjunktioner hvortil der tilsættes en bogstavelig og som andet element den anden sammenholdt hvortil der sættes det modsatte af den bogstavelige, nemlig . At reducere konsensus er sammensætningen af to ord, uden bogstavelig og uden øvelse bogstaver. For eksempel, hvis konsensus er , er dens reduktion . $på$ ${\ bar {a}}$ $på$ ${\ bar {a}}$ $v {\ bar {x}} yz \ vee vw {\ bar {y}} z$ $vw {\ bar {x}} z$

Ansøgninger

Ved at forenkle boolske udtryk er den gentagne anvendelse af konsensusreglen kernen i at beregne den kanoniske form for Blake (in) .

I design af digitalt kredsløb eliminerer konsensusforenkling af et kredsløb risikoen for konkurrence .

Historie

Begrebet konsensus blev introduceret af Archie Blake i 1937 i sin afhandling, en gennemgang af en side, som dukkede op i Juni 1938. Konceptet blev genopdaget af Edward W. Samson og Burton E. Mills i 1954 og offentliggjort i en rapport fra det amerikanske luftvåben. Det blev udgivet af Willard Quine i 1955. Det var Quine, der introducerede udtrykket "konsensus". Operationen kaldes også undertiden "løsning", da JA Robinson brugte den i en mere generel form, men til klausuler snarere end til implikanter, som grundlaget for hans " løsningsprincip " som bevis for sætninger.

Referencer

(fr) Denne artikel er helt eller delvist hentet fra den engelske Wikipedia- artikel med titlen " Consensus theorem " ( se listen over forfattere ) .

Brun 2003 , s. 44.
Roth og Kinney 2014 , 2.6 Simplification theorems s. 46-47 og 3.3 Konsensus sætningen, s. 70 og efterfølgende.
Brown 2003 , s. 81.
(i) Mohamed Rafiquzzaman, Fundamentals of Digital Logic og mikrokontrollere , Hoboken, NJ, Wiley ,2014, 6. th ed. , 512 s. ( ISBN 978-1-118-85579-9 og 1-118-85579-5 , læs online ) , s. 75
(i) Donald E. Knuth , The Art of Computer Programming , Vol. 4A: Kombinationsalgoritmer, del 1 , Addison-Wesley ,2011( ISBN 978-0-201-03804-0 og 0-201-03804-8 , online præsentation ) , s. 539; Løsning til øvelse 7.1.1.31, afsnittet Referencer.
(i) Archie Blake Canonical udtryk i boolsk algebra , University of Chicago, Afd af matematik,1937.
JCC McKinsey, “ Archie Blake . Kanoniske udtryk i boolsk algebra ”, J. Symb. Logic , vol. 3, n o 2Juni 1938, s. 93 ( DOI 10.2307 / 2267634 , JSTOR 2267634 ), fri adgang.
(i) Edward W. Samson og Burton E. Mills, Air Force Cambridge Research Centre teknisk rapport 54-21 april 1954.
(i) Willard Quine , " En måde at forenkle sandhedsfunktioner på " , Amer. Matematik. Månedligt , vol. 62, nr . 9,1955, s. 627-631 ( DOI 10.2307 / 2307285 , JSTOR 2307285 , matematiske anmeldelser MR75886 ).
Quine anerkender anterioriteten af Samson og Mills 'arbejde i en fodnote til hans artikel.
(i) J. Alan Robinson , " A Machine-Oriented Logic Baseret på resolutionen Princip " , Journal of the ACM , vol. 12, n o 1,1965, s. 23-41.

Bibliografi

(en) Frank Markham Brown , Boolean Reasoning: The Logic of Boolean Equations , Mineola, NY, Dover Publications ,2003, 2 nd ed. , 291 s. ( ISBN 978-0-486-42785-0 , læs online )
(en) Charles H. Roth Jr. og Larry L. Kinney , Fundamentals of Logic Design , Stamford, CT, Cengage Learning,2014, 7 th ed. ( 1 st ed. 2004), 816 s. ( ISBN 978-1-133-62847-7 , læs online ).