Méthode des consensus
La méthode des consensus (Willard Van Orman Quine, 1952[1]) est une méthode de calcul booléen. C'est une méthode programmable permettant de simplifier une fonction logique quelconque de plusieurs variables. Elle s'applique indifféremment aux fonctions présentées sous forme canonique, ou sous forme de somme de termes plus ou moins réduits.
Principe de la méthode
La méthode permet de réécrire une fonction booléenne f à simplifier comme somme de tous ses termes les plus simples possibles. Cette somme est dite base première de la fonction. C'est la somme de ses termes ou monômes premiers, un terme étant premier s'il ne peut être combiné avec aucun autre pour donner un terme plus simple.
Elle suppose la fonction logique à simplifier exprimée soit sous forme tabulaire, soit sous la forme d'une somme de monômes.
Pour cela, on utilise itérativement la relation :
a'b + ac = a'bc' + a'bc + abc + ab'c= a'b + bc + ac
Dans cette relation, bc = C(a'b, ac) est dit consensus des termes a'b et ac, qui ne diffèrent explicitement que par une variable, ici a. Dans tous les autres cas, le consensus est nul.
- Son nom est justifié par le fait que si l'on admet deux thèses a'b et ac s'opposant sur un point principal a, leurs synthèse comporte une thèse transversale non-contradictoire, ou consensus, équivalant à bc.
Quand un nouveau consensus est facteur d'un terme présent, il l'absorbe, comme dans :
a'bc + abcd = a'bc + abcd + bcd = a'bc + bcd.
Finalement, la méthode des consensus est complétée par l'élimination, dans la base première, des termes jugés redondants -- au sens de la simplicité recherchée dans l'écriture de f.
Cas des fonctions partiellement définies
C'est par exemple le cas de fonctions logiques devant traiter des chiffres décimaux codés sur 4 bits.
Pour les fonctions f partiellement définies, on définit
- inf(f) comme la fonction totalement définie regroupant les 1 de f,
- sup(f) = inf(f')', comme la fonction totalement définie formée des points p où f(p) diffère de 0.
Alors, la méthode des consensus consiste à trouver les termes premiers de sup(f), pour un maximum de possibilités ; et l'étape de couverture à chercher les sommes de termes premiers de cette base suffisant à couvrir les points de inf(f).
Exemple
A la relation a'b'c'+a'b'c =a'b', associons la convention que dans le cube B³, le segment unissant (000) et (001) se note (00*), et que l'union du segment (00*) et du segment (10*) produit une face(*0*)ou b'.
Soit f =(*00)+(01*)+(*11)+(110) = b'c'+a'b+bc+abc', où la première expression définit l'ensemble des "1" comme une collection d'objets (points, segments, faces...) de l'hypercube associé, et la seconde expression comme un polynôme booléen.
Construction de la base première
On part de f = b'c'+a'b+bc+abc', qu'on fait évoluer en faisant apparaître progressivement tous les consensus possibles, tout en réduisant les formules par absorption.
Partons du premier terme.
- C(b'c'+a'b) = a'c'; C(b'c', bc) = 0; C(b'c',abc')= ac'. Donc f = (b'c'+a'b+bc+abc')+ a'c'+ ac' = b'c' + a'b + bc + a'c'+ ac', car ac' absorbe abc'.
- C(a'b, bc)= 0 = C(a'b, a'c'), mais C(a'b, ac') = bc'. Donc f = b'c'+a'b+bc+a'c'+ac'+bc'.
- C(bc, bc') = b, qui absorbe tous les termes en b, et f = b'c'+a'c'+ ac'+ b.
- C(a'c', ac')= c', qui absorbe b'c', a'c', ac'. Finalement :
f = b+c'.
Géométriquement, dans le cube B³, les trois segments initiaux et le point initial se regroupent progressivement en 2 faces.
En machine, on représenterait f par la table suivante, regroupant les seuls "1", et où "*" indique une variable absente (réduite ou biforme). Cette table est généralement plus courte que la table de vérité.
| a | b | c | |
|---|---|---|---|
| * | 0 | 0 | |
| 0 | 1 | * | |
| * | 1 | 1 | |
| 1 | 1 | 0 |
Couverture
On conclut en cherchant dans la base première des sous-ensembles de termes les plus simples possibles, qui réalisent tous les points ou "1" de la fonction. Dans notre exemple, b = (*1*) et c' = (**0) sont nécessaires et suffisants.
- b =(*1*) est nécessaire pour (01*) et (*11), et suffisant pour (01*),(*11),(110);
- c'=(**0) est nécessaire pour (*00) et suffisant pour (*00) et (110).
Intérêt
L'utilisation des diagrammes de Karnaugh permet difficilement de dépasser 6 variables. La présente méthode, étant programmable, va bien au-delà, en acceptant une fonction définie sous la forme de somme de termes n'utilisant pas forcément toujours les mêmes variables : elle est donc plus souple que la Méthode de Quine-Mc Cluskey.
Notes et références
- the problem of simplifying truth functions