Théorème du consensus

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Consensus (homonymie).
Variable d'entrée Valeur des fonctions
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

En algèbre de Boole, le théorème du consensus ou règle du consensus[1] est un théorème en logique propositionnelle.

Théorème[modifier | modifier le code]

Il consiste en une simplification des termes suivants :

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

Le consensus ou résolvant des termes xy et \bar{x}z est yz.

L'expression duale de cette équation est :

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

Démonstration[modifier | modifier le code]

La table de vérité ci-contre est une démonstration. En voici une autre :

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 cqfd


Applications[modifier | modifier le code]

En algèbre de Boole, le consensus répété est le cœur d'un algorithme pour calculer la forme canonique de Blake (Blake canonical form) d'une formule[2].

En logique digitale, l'inclusion le terme de consensus dans un circuit peut éliminer les dangers dans les situations de compétition (race hazard)[3].

Histoire[modifier | modifier le code]

Le concept de consensus a été introduit par Archie Blake en 1937[4]. Il est redécouvert par Samson et Mills en 1954[5] et par Quine en 1955[6]. Quine invente le terme de "consensus". Robinson l'utilise pour des propositions (clauses) en 1965 comme base de son "principe de résolution"[7],[8].

Références[modifier | modifier le code]

  1. Frank Markham Brown, Boolean Reasoning: The Logic of Boolean Equations, 2nd edition 2003, p. 44
  2. Frank Markham Brown, Boolean Reasoning: The Logic of Boolean Equations, 2nde édition 2003, p. 81
  3. M. Rafiquzzaman, Fundamentals of Digital Logic and Microcontrollers, 6e édition (2014), (ISBN 1118855795), p. 75
  4. "Canonical expressions in Boolean algebra", Dissertation, Dept. of Mathematics, U. of Chicago, 1937, reviewed in J. C. C. McKinsey, The Journal of Symbolic Logic 3:2:93 (Juin 1938) DOI:10.2307/2267634 JSTOR 2267634
  5. Edward W. Samson, Burton E. Mills, Air Force Cambridge Research Center Technical Report 54-21, Avril 1954
  6. W.V. Quine, "The problem of simplifying truth functions", American Mathematical Monthly 59:521-531, 1952 JSTOR 2308219
  7. J. Alan Robinson, "A Machine-Oriented Logic Based on the Resolution Principle", Journal of the ACM 12:1: 23–41.
  8. D.E. Knuth, The Art of Computer Programming 4A: Combinatorial Algorithms, part 1, p. 539

Bibliographie[modifier | modifier le code]

  • (en) Charles H. Roth Jr. et Larry L. Kinney, Fundamentals of Logic Design,‎ , 6e éd. (1re éd. 2004), p. 66 et suivantes.