Apprendre › Chapitre 3

Tables de vérité et formes canoniques : Σm et ΠM

8 min de lecture · Équipe bitGateLab

Presque tous les problèmes de conception numérique commencent par un énoncé en langage courant (« l'alarme sonne si... ») que l'on convertit en table de vérité. L'étape suivante consiste à tirer de cette table une équation réalisable avec des portes. Vous allez apprendre ici la méthode systématique pour y parvenir : les mintermes et les maxtermes, les formes canoniques en somme de produits et en produit de sommes, et la notation compacte Σm et ΠM qu'utilisent les manuels, les simulateurs et les tableaux de Karnaugh.

Comment ordonner une table de vérité

Avec n variables, il y a 2ⁿ lignes. On les écrit dans l'ordre binaire croissant, la première variable étant le bit de poids fort. Chaque ligne est ainsi identifiée par un nombre décimal : dans une table en A, B et C, la ligne A = 1, B = 0, C = 1 est la ligne 101₂ = 5. C'est ce nombre qui vous servira d'indice de minterme ou de maxterme ; l'ordre des variables a donc son importance : si vous le changez, les numéros changent.

Mintermes et somme de produits

Un minterme est un produit (AND) qui contient toutes les variables, chacune une seule fois, complémentée ou non. On le construit ainsi : la variable qui vaut 1 sur cette ligne s'écrit sans barre et celle qui vaut 0 s'écrit avec une barre. Le minterme vaut 1 uniquement sur sa ligne et 0 sur toutes les autres. On le note m_i, où i est le numéro de la ligne.

Ligne	A	B	C	Minterme	Maxterme
0	0	0	0	m₀ = ABC	M₀ = A + B + C
1	0	0	1	m₁ = ABC	M₁ = A + B + C
2	0	1	0	m₂ = ABC	M₂ = A + B + C
3	0	1	1	m₃ = ABC	M₃ = A + B + C
4	1	0	0	m₄ = ABC	M₄ = A + B + C
5	1	0	1	m₅ = ABC	M₅ = A + B + C
6	1	1	0	m₆ = ABC	M₆ = A + B + C
7	1	1	1	m₇ = ABC	M₇ = A + B + C

Si vous faites la somme (OR) des mintermes de toutes les lignes où la fonction vaut 1, vous obtenez une équation qui vaut 1 exactement sur ces lignes. C'est la somme de produits canonique (SOP, sigle de l'anglais « sum of products »), ou première forme canonique. En notation compacte, on écrit F = Σm(liste des lignes à 1).

Maxtermes et produit de sommes

Un maxterme est une somme (OR) qui contient toutes les variables. La règle est inversée : la variable qui vaut 0 sur la ligne s'écrit sans barre et celle qui vaut 1 s'écrit avec une barre. Un maxterme vaut 0 uniquement sur sa ligne. On le note M_i (avec un M majuscule).

Si vous faites le produit (AND) des maxtermes de toutes les lignes où la fonction vaut 0, vous obtenez une équation qui vaut 0 précisément sur ces lignes et 1 partout ailleurs : le produit de sommes canonique (POS), ou seconde forme canonique. On écrit F = ΠM(liste des lignes à 0).

Le minterme et le maxterme d'une même ligne sont complémentaires : m_i = M_i. Par conséquent, si vous connaissez la liste Σm d'une fonction, la liste ΠM est formée de tous les numéros qui n'y figurent pas.

Exemple 1 : de la table aux deux formes. Une fonction de trois variables vaut 1 sur les lignes 1, 3, 6 et 7.

#	A	B	C	F
0	0	0	0	0
1	0	0	1	1
2	0	1	0	0
3	0	1	1	1
4	1	0	0	0
5	1	0	1	0
6	1	1	0	1
7	1	1	1	1

Notation compacte : F = Σm(1, 3, 6, 7) = ΠM(0, 2, 4, 5).
Somme de produits canonique : F = ABC + ABC + ABC + ABC.
Produit de sommes canonique : F = (A + B + C)(A + B + C)(A + B + C)(A + B + C).
Simplifiez la SOP : ABC + ABC = AC et ABC + ABC = AB. Ainsi, F = AC + AB.

Vérification sur la ligne 5 (A = 1, B = 0, C = 1) : AC = 0 et AB = 0, donc F = 0, comme dans la table.

Quelle forme choisir ?

Les deux formes décrivent la même fonction, mais elles n'ont pas la même taille. Utilisez celle qui a le moins de termes : si la fonction comporte peu de uns, la forme Σm est plus courte ; si elle comporte peu de zéros, c'est la forme ΠM. Avec 8 lignes, une fonction qui compte 2 uns a une SOP de 2 termes et une POS de 6.

La réalisation compte aussi. Une somme de produits se construit avec des portes AND qui attaquent une OR, et cette structure à deux niveaux se convertit directement en NAND-NAND. Un produit de sommes se construit avec des OR qui attaquent une AND, et se convertit en NOR-NOR.

Exemple 2 : de l'énoncé à l'équation. Un réservoir possède trois capteurs de niveau : A (bas), B (moyen) et C (haut). Chaque capteur fournit un 1 lorsque l'eau l'atteint. Un voyant « niveau invalide » doit s'allumer lorsque la combinaison est physiquement impossible : un capteur haut actif alors qu'un capteur plus bas est inactif.

Combinaisons valides (ABC) : 000, 100, 110, 111, c'est-à-dire les lignes 0, 4, 6 et 7.
Le voyant s'allume sur les autres : F = Σm(1, 2, 3, 5).
De façon équivalente : F = ΠM(0, 4, 6, 7).
Simplifiez : m₁ + m₃ = AC, m₁ + m₅ = BC, m₂ + m₃ = AB. En utilisant m₁ et m₃ deux fois (idempotence), F = BC + AB.

Vérifiez : la ligne 1 (001) donne BC = 1 ; la ligne 2 (010) donne AB = 1 ; la ligne 3 (011) donne AB = 1 ; la ligne 5 (101) donne BC = 1. Pour 000, 100, 110 et 111, les deux termes valent 0. On lit « C actif sans B » ou « B actif sans A ».

Le complément d'une fonction

Si F = Σm(1, 3, 6, 7), son complément vaut 1 là où F vaut 0 : F = Σm(0, 2, 4, 5). C'est utile lorsque vous voulez la POS simplifiée : vous simplifiez F en somme de produits, puis vous appliquez De Morgan. Par exemple, F = AC + AB (vérifiez-le sur les lignes 0, 2, 4 et 5), et en complémentant on obtient F = (A + C)(A + B). Si vous développez : AB + AC + BC, et par consensus cela donne AB + AC, le même résultat que dans l'exemple 1.

Pour approfondir ces manipulations, revoyez l'algèbre de Boole ; pour simplifier de manière graphique, poursuivez avec les tableaux de Karnaugh.

Erreurs fréquentes

Inverser la règle des barres : dans les mintermes, c'est le 0 qui porte la barre ; dans les maxtermes, c'est le 1.
Mettre dans ΠM les lignes où la fonction vaut 1. ΠM liste les zéros, Σm liste les uns.
Changer l'ordre des variables entre la table et l'équation. Avec l'ordre C, B, A, la ligne « 5 » n'est plus la même.
Oublier une variable dans un terme canonique. Un minterme de quatre variables a toujours quatre littéraux ; s'il en a moins, il est déjà simplifié et n'est plus canonique.

Essayez dans le simulateur

Le module de table de vérité vous permet de saisir une fonction ligne par ligne et de voir aussitôt ses formes canoniques et l'équation simplifiée ; vous pouvez ainsi contrôler chaque étape de votre travail à la main.

Créez une table à trois entrées et une sortie.
Mettez à 1 les lignes 1, 3, 6 et 7 de l'exemple 1 et laissez les autres à 0.
Observez les expressions Σm et ΠM générées et comparez-les aux vôtres.
Convertissez la table en circuit et changez les entrées pour confirmer que la sortie suit bien la table.
Recommencez avec le problème du réservoir et vérifiez que le voyant ne s'allume que pour les combinaisons impossibles.

Exercices

Écrivez le minterme m₉ et le maxterme M₉ d'une fonction de quatre variables A, B, C, D.
Réponse
9 = 1001. m₉ = ABCD et M₉ = A + B + C + D.
Si F(A, B, C) = Σm(0, 1, 5), écrivez F en notation ΠM.
Réponse
F = ΠM(2, 3, 4, 6, 7).
Trouvez la somme de produits canonique d'une fonction de deux variables qui vaut 1 uniquement lorsque A et B sont égales, et simplifiez-la si c'est possible.
Réponse
F = Σm(0, 3) = AB + AB. Elle ne se réduit pas : c'est la XNOR.
Écrivez le produit de sommes canonique de F(A, B, C) = Σm(1, 2, 3, 4, 5, 6, 7).
Réponse
Elle ne vaut 0 que sur la ligne 0, donc F = ΠM(0) = A + B + C. Une seule OR à trois entrées.