Teorema di consenso

Variabile di input			Valore delle funzioni
$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

In algebra booleana , il teorema del consenso o consenso regola è un'identità booleana (che corrisponde ad un'equivalenza di logica proposizionale ). È una regola di semplificazione delle espressioni booleane, con altre come la regola dell'assorbimento o quella dell'eliminazione.

stati

Il teorema del consenso o la regola del consenso è l'identità:

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

Nella semplificazione delle formule booleane, riduciamo la parte sinistra alla parte destra dalla regola:

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

Il termine è chiamato consenso o risoluzione dei termini e . Il consenso di due congiunzioni di letterali è la congiunzione ottenuta da tutti i letterali che vi compaiono, rimuovendone uno che appare sia negato nell'uno che non negato nell'altro. Nell'identità indicato, se x è un letterale, e se y e z rappresentano congiunzioni di letterali, allora il consenso di e di è buono . $yz$ $xy$ ${\ overline {x}} z$ $xy$ ${\ bar {x}} z$ $yz$

La doppia identità è:

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

Il risolutore è dedotto dalle due disgiunzioni e dalla cosiddetta regola di cut-off o di risoluzione , da qui la semplificazione. $(y \ vee z)$ $(x \ vee y)$ $({\ bar {x}} \ vee z)$

Dimostrazione

L'identità può essere verificata dalla sua tabella di verità (data sopra). Può anche essere dimostrato dagli assiomi dell'algebra booleana :

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

= (neutro e complementare)

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

= (distributività)

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

= (associatività e commutatività)

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

= ( assorbimento , due volte)

xy \ vee {\ bar {x}} z

Consenso e riduzione del consenso

Il consenso di due congiunzioni di letterali è una disgiunzione, questa disgiunzione contiene come primo membro una delle congiunzioni a cui viene aggiunto un letterale e come secondo membro l'altra congiunzione a cui viene aggiunto l'opposto del letterale, vale a dire . Ridurre il consenso è la congiunzione di due parole, senza il letterale e senza i letterali delle prove. Ad esempio, se il consenso è , la sua riduzione lo è . $a$ ${\ bar {a}}$ $a$ ${\ bar {a}}$ $v {\ bar {x}} yz \ vee vw {\ bar {y}} z$ $vw {\ bar {x}} z$

Applicazioni

Con la semplificazione espressioni booleane , l'applicazione ripetitiva della regola del consenso è al centro di calcolo della forma canonica di Blake (a) .

Nella progettazione di circuiti digitali , la semplificazione consensuale di un circuito elimina il rischio di concorrenza .

Storia

Il concetto di consenso fu introdotto da Archie Blake nel 1937 nella sua tesi, la cui recensione di una pagina apparve in Giugno 1938. Il concetto fu riscoperto da Edward W. Samson e Burton E. Mills nel 1954 e pubblicato in un rapporto dell'aeronautica americana. Fu pubblicato da Willard Quine nel 1955. Fu Quine a introdurre il termine "consenso". L'operazione è talvolta chiamata anche "risoluzione" poiché JA Robinson l'ha usata, in una forma più generale, ma per clausole piuttosto che per implicanti, come base del suo " principio di risoluzione " nella dimostrazione dei teoremi.

Riferimenti

(fr) Questo articolo è parzialmente o interamente tratto dall'articolo di Wikipedia in inglese intitolato " Consensus theorem " ( vedere l'elenco degli autori ) .

Brown 2003 , p. 44.
Roth e Kinney 2014 , 2.6 Teoremi di semplificazione p. 46-47 e 3.3 The Consensus Theorem, p. 70 e seguenti.
Brown 2003 , p. 81.
(a) Mohamed Rafiquzzaman, Fondamenti di logica digitale e microcontrollori , Hoboken, NJ, Wiley ,2014, 6 ° ed. , 512 p. ( ISBN 978-1-118-85579-9 e 1-118-85579-5 , leggi online ) , p. 75
(a) Donald E. Knuth , The Art of Computer Programming , Vol. 4A: Algoritmi combinatori, parte 1 , Addison-Wesley ,2011( ISBN 978-0-201-03804-0 e 0-201-03804-8 , presentazione online ) , p. 539; Soluzione dell'esercizio 7.1.1.31, sezione Riferimenti.
(in) Archie Blake Canonical Expression in Boolean Algebra , University of Chicago, Dept. di matematica,1937.
JCC McKinsey, " Archie Blake . Espressioni canoniche in algebra booleana ", J. Symb. Logica , vol. 3, n o 2Giugno 1938, p. 93 ( DOI 10.2307 / 2267634 , JSTOR 2267634 ), accesso libero.
(in) Edward W. Samson e Burton E. Mills, Air Force Cambridge Research Center Technical Report 54-21 aprile 1954.
(in) Willard Quine , " Un modo per semplificare le funzioni di verità " , Amer. Matematica. Mensile , vol. 62, n o 9,1955, p. 627-631 ( DOI 10.2307 / 2307285 , JSTOR 2307285 , Recensioni matematiche MR75886 ).
Quine riconosce l'anteriorità del lavoro di Samson e Mills in una nota a piè di pagina al suo articolo.
(in) J. Alan Robinson , " A Machine-Oriented Logic Based on the Resolution Principle " , Journal of the ACM , vol. 12, n o 1,1965, p. 23-41.

Bibliografia

(en) Frank Markham Brown , Ragionamento booleano: la logica delle equazioni booleane , Mineola, NY, Dover Publications ,2003, 2 ° ed. , 291 p. ( ISBN 978-0-486-42785-0 , leggi online )
(it) Charles H. Roth Jr. e Larry L. Kinney , Fundamentals of Logic Design , Stamford, CT, Cengage Learning,2014, 7 ° ed. ( 1 a ed. 2004), 816 p. ( ISBN 978-1-133-62847-7 , leggi in linea ).