Un des aspects ennuyeux des expressions logiques est que la correspondance entre expression et fonction logique n’est pas biunivoque: plusieurs expressions différentes peuvent correspondre à une seule et même fonction. De plus, certaines des expressions équivalentes peuvent être plus complexes que d’autres. Lorsque vient le temps d’implémenter avec des portes une fonction logique, il est la plupart du temps plus efficace d’implémenter selon une expression plus simple, voire minimale. On doit donc considérer des approches systématiques et efficaces pour simplifier les expressions logiques.
Quand une expression booléenne est implémentée avec des portes logiques, chaque terme nécessite une porte et chaque variable au sein d’un terme correspond à une entrée de la porte. On appelle littéral une variable qui apparaît dans un terme, sous forme complémentée ou non. Par exemple, l’expression \(F = x^\prime y^\prime z + xz + xy^\prime z\) compte huit littéraux. Si on réduit le nombre de termes, le nombre de littéraux, ou les deux, on obtiendra une expression qui sera plus simple à implémenter avec des portes.
Dans une expression, une variable \(x\) peut apparaître telle quelle $x$ ou complémentée \(x^\prime\). Si on considère les combinaisons possibles de deux variables via un opérateur ET, on a alors quatre possibilités: \(x^\prime y^\prime, x^\prime y, x y^\prime,x y\). Chacun de ces quatre termes s’appelle un minterm.
De façon équivalente (duale, en vérité), \(n\) variables reliées par une fonction OU peuvent donner lieu à \(2^n\) termes distincts, appelés maxterms.
De façon générale, pour \(n\) variables, on aura \(2^n\) minterms ou $2^n$ maxterms différents possibles.
Pour étiqueter les différents minterms ou maxterms, on a établi une convention de numérotation. Le numéro d’étiquette d’un minterm est construit de la façon suivante. Une variable complémentée amène un bit d’étiquette 0, une variable telle quelle amène un bit d’étiquette 1. En ordonnant les bits selon l’ordre alphabétique des variables, on obtient un vecteur de bits qui donnera le numéro à assigner au minterm. Par exemple, le minterm \(x y^\prime z\) donnera l’étiquette 101, donc le numéro de minterm (en équivalent décimal) 5.
La règle pour les maxterms est duale: une étiquette 0 pour une variable telle quelle, et une étiquette 1 pour une variable complémentée. Chaque maxterm est le complément du minterm correspondant (de même numéro), et vice versa.
Dans le tableau 1, on montre les symboles de la forme \(m_j\) pour les minterms et \(M_j\) pour les maxterms, avec \(j\) qui est l’équivalent décimal de la combinaison de bits correspondante.
| $$x$$ | $$y$$ | $$z$$ | Minterm | Symb. | Maxterm | Symb. |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | $$x^\prime y^\prime z^\prime$$ | $$m_0$$ | $$x+ y+ z$$ | $$M_0$$ |
| 0 | 0 | 1 | $$x^\prime y^\prime z$$ | $$m_1$$ | $$x+ y+ z^\prime$$ | $$M_1$$ |
| 0 | 1 | 0 | $$x^\prime y z^\prime$$ | $$m_2$$ | $$x+ y^\prime+ z$$ | $$M_2$$ |
| 0 | 1 | 1 | $$x^\prime y z$$ | $$m_3$$ | $$x+ y^\prime+ z^\prime$$ | $$M_3$$ |
| 1 | 0 | 0 | $$x y^\prime z^\prime$$ | $$m_4$$ | $$x^\prime+ y+ z$$ | $$M_4$$ |
| 1 | 0 | 1 | $$x y^\prime z$$ | $$m_5$$ | $$x^\prime+ y+ z^\prime$$ | $$M_5$$ |
| 1 | 1 | 0 | $$x y z^\prime$$ | $$m_6$$ | $$x^\prime+ y^\prime+ z$$ | $$M_6$$ |
| 1 | 1 | 1 | $$x y z$$ | $$m_7$$ | $$x^\prime + y^\prime+ z^\prime$$ | $$M_7$$ |
Pour la fonction \(F_1\) dont le tableau de vérité est le suivant:
| $$x$$ | $$y$$ | $$z$$ | $$F_1$$ | |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | |
| 0 | 0 | 1 | 0 | |
| 0 | 1 | 0 | 1 | |
| 0 | 1 | 1 | 0 | |
| 1 | 0 | 0 | 1 | |
| 1 | 0 | 1 | 1 | |
| 1 | 1 | 0 | 1 | |
| 1 | 1 | 1 | 1 |
on peut donc écrire
\[F_1 = x ^\prime y z^\prime + x y^\prime z^\prime + x y^\prime z + x y z^\prime + x y z = m_2 + m_4 + m_5 + m_6 + m_7\]puisque ce sont les termes pour lesquels la fonction vaut 1. Cette forme d’expression est une forme canonique appelée somme de produits.
Pour simplifier la notation, on peut écrire de façon plus compacte
\[F_1 = \sum (2, 4, 5, 6, 7)\]où on ne met que les numéros des minterms participant à la somme.
Si on veut exprimer le complément d’une fonction, on peut lire dans le tableau de vérité les combinaisons pour lesquelles la fonction vaut 0. En prenant un minterm pour chaque combinaison où la fonction vaut 0 et en faisant un OU de ces termes, on obtient une expression en somme de produits pour le complément de la fonction. Ainsi, pour la fonction \(F_1^\prime\), on a
\[F_1^\prime = m_0 + m_1 + m_3 = x^\prime y^\prime z^\prime + x^\prime y^\prime z + x^\prime y z\]Si on complémente \(F_1^\prime\), on obtiendra naturellement \(F_1\). En appliquant le théorème de DeMorgan à chaque terme, on trouve
\[F_1 = (x+ y+ z)(x + y + z^\prime)(x + y^\prime + z^\prime) = M_0 \cdot M_1 \cdot M_3\]Cette forme d’expression est aussi une forme canonique appelée produit de sommes.
Pour simplifier la notation, on peut écrire de façon plus compacte
\[F_1 = \prod (0,1,3)\]où on ne met cette fois que les numéros des maxterms participant au produit.
Pour \(n\) variables binaires, on a \(2^n\) minterms différents possibles. Les minterms qui participent à la somme dans l’expression en forme canonique somme de produits sont ceux qui produisent un 1 dans le tableau de vérité de la fonction. Puisque la fonction peut valoir 0 ou 1 pour chaque minterm, le nombre total de fonctions différentes qui peuvent être définies avec \(n\) variables est de \(2^{2^n}\).
Si on veut convertir en forme canonique somme de produits l’expression pour une fonction qui ne serait pas sous cette forme, on commence par faire l’expansion de l’expression en forme somme de produits. Ensuite, on vérifie chaque terme pour voir si toutes les variables en font partie. S’il manque une ou des variables, on peut faire un ET du terme avec une expression du type \(x + x^\prime\) dans laquelle \(x\) est une variable manquante. Ce ET ne change pas la valeur de la fonction puisque \(x + x^\prime = 1\).
Évidemment, on peut toujours trouver la formulation en forme canonique en se basant sur le tableau de vérité.
Si on veut convertir en forme canonique produit de sommes l’expression pour une fonction qui ne serait pas sous cette forme, on commence par faire l’expansion de l’expression en forme produit de sommes. Pour ce faire, on peut avantageusement faire appel à la distributivité de \(+\) sur \(\cdot\) pour ce faire. Ensuite, on vérifie chaque terme pour voir si toutes les variables en font partie. S’il manque une ou des variables, on peut faire un OU du terme avec une expression du type \(x \cdot x^\prime\) dans laquelle \(x\) est une variable manquante. Ce OU ne change pas la valeur de la fonction puisque \(x \cdot x^\prime = 0\).
Prenons notre exemple précédent \(F_1 = \sum (2, 4, 5, 6, 7)\). On sait que \(F_1^\prime = \sum (0,1,3)\). Si on prend le complément de \(F_1^\prime\) par le théorème de DeMorgan, on obtient \(F_1 = (m_0 + m_1 + m_3)^\prime = m_0^\prime \cdot m_1^\prime \cdot m_3^\prime = M_0 \cdot M_1 \cdot M_3 = \prod (0,1,3)\).
En effet, de minterm à maxterm, on a \(m_j^\prime = M_j\). Le maxterm d’indice \(j\) est le complément du minterm de même indice \(j\), et vice versa.
Les expressions canoniques en somme de produits et en produit de sommes ne sont généralement pas simples, car toutes les variables doivent être présentes. Pour l’implémentation, on cherchera des expressions en formes somme de produits ou produit de sommes dans lesquelles les termes pourront être simplifiés. C’est-à-dire que les termes pourront comporter une, deux, trois, etc. variables plutôt qu’obligatoirement toutes les variables. Toujours pour notre fonction exemple, on peut écrire
\[F_1 = x + y z^\prime\]Lorsqu’on implémente une telle fonction avec des portes logiques, il faut une porte ET pour chaque terme produit (qui comporte plus d’une variable) et une porte OU pour faire la somme finale. On obtient une implémentation à deux niveaux.
De façon duale, on peut également obtenir une formulation en produit de sommes qui aboutira à une implémentation à deux niveaux avec une porte OU par terme et une porte ET pour le produit final.