L'algèbre de Boole

Dans l’introduction, on a parlé d’ensemble et de lois. Ça, c’est pour que les matheux soient contents … Mais de quoi on parle ?

Déjà, on parle d’ensemble, ce qui signifie que toute opération sur un élément de cet ensemble doit être un élément de cet ensemble (pas forcément le même). Ici, on travaille avec un ensemble composé de deux éléments, donc le choix est assez restreint.

Mais quelles sont ces opérations ?

• La disjonction, $a+b$. Cette opération est équivalente au connecteur OU, donc $a+b=0$ si $a=b={0}$.
• La conjonction, $a\times b$, qu’on peut également écrire $a\cdot b$ ou encore plus simplement $ab$. C’est l’équivalent du connecteur ET, donc $a\cdot b={1}$ si $a=b={1}$.

Et mine de rien, le fait qu’on utilise ces deux opérations et la théorie des ensembles veut dire qu’on a déjà un certain nombre d’axiomes (de règles) associés :

Ici, $a$, $b$ et $c$ sont des variables propositionnelles telles qu’on les a rencontrées au chapitre précédent, on parle également d’atome¹ dans le cadre de l’algèbre de Boole.

Bref, on a des règles légèrement différentes de ce qu’on a l’habitude de voir, mais qui sont néanmoins logiques au vu de ce qu’on a vu au chapitre précédent. Par ailleurs, ces règles sont définies d’une manière particulière, au vu d’une propriété intéressante de l’algèbre de Boole, la dualité : si on définit une règle pour un des deux opérateurs, on peut obtenir la règle pour l’autre opérateur en interchangeant ${ 1 }\leftrightarrow 0$ et $+ \leftrightarrow \times$. Ainsi, si on reprend le premier axiome pour $\times$, $a\cdot\bar{a}=0$, on voit qu’on obtient bien l’axiome correspondant pour $+$ (son dual) en remplaçant $\cdot$ par $+$ et $0$ par $1$.²

À noter qu’on nomme littéral un atome ou son opposé. Ainsi, $\bar{a}+b$ est une disjonction de deux littéraux, $\bar{a}$ et $b$.

De là, on tire un certain nombre de propriétés³:

Ces propriétés vont se révéler utiles lorsqu’on va travailler, juste en dessous, sur des fonctions booléennes. Par ailleurs, vous pouvez facilement vérifier que ces propriétés respectent la dualité exprimée ci-dessus.

Pour la faire courte, une fonction, c’est une application qui fait correspondre un ensemble à un autre, c’est-à-dire qui, à un objet mathématique dans un ensemble de départ, en fait correspondre un autre dans l’ensemble d’arrivée :

$f:\mathcal{E}^m\rightarrow \mathcal{G}^n: e_1,\ldots,e_m\mapsto g_1,\ldots,g_n$

qui signifie que la fonction $f$ est une application qui fait correspondre à un ensemble de $m$ éléments (un $m$-uplet) de l’ensemble $\mathcal{E}$ à un ensemble de $n$ éléments de l’ensemble $\mathcal{G}$. Dans le cas qui nous occupe, on va travailler avec des fonctions de $\mathbb{B}^n\rightarrow\mathbb{B}$, donc des fonctions de $n$ variables en entrées et qui donne un résultat unique (0 ou 1).

Encore une fois, un mot très compliqué pour désigner ce qu’on a déjà rencontré dans le chapitre précédent sous le terme de formule. Une fonction booléenne, c’est donc une série d’atomes liés entre eux par des opérations vues plus haut. Par exemple, la formule $a\land(b\lor c)$ est « traduite », dans l’algèbre de Boole, par $f(a,b,c)=a\,(b+c)$. De par les axiomes qu’on a vu plus haut, on sait déjà que c’est équivalent à $f(a,b,c)=a\cdot b + a\cdot c$.

Mais on peut complexifier les choses et travailler sur des fonctions booléennes beaucoup plus complexes (la complexité n’ayant pour limite que votre imagination), telles que

$f(a,b,c) = a\cdot\overline{(b\cdot c)}+\overline{(\bar{a}+b)}.$

Une telle fonction, bien que tout à fait correcte, peut être réécrite sous deux formes :

• Forme normale conjonctive (FNC) : la fonction est exprimée sous forme d’une conjonction de formes disjonctives : $f=m_1\cdot m_2 \ldots m_n$, avec $m_i$ la clause disjonctive, c’est-à-dire une disjonction de littéraux ($q_1+q_2+\ldots+q_n$). Si tous les atomes sont présents (sous forme de littéraux) dans chacune des formes disjonctives, on parle de forme normale (ou canonique).
• Forme normale disjonctive (FND) : la fonction est exprimée sous la forme d’une disjonction de formes conjonctives (donc $f=m_1+m_2\ldots+m_n$, $m_i=q_1\cdot q_2\ldots q_n$).

Pour obtenir de telles formes, il est nécessaire de faire porter la complémentation sur les variables (en utilisant la loi de De Morgan si nécessaire), puis d’utiliser la distributivité de $\times$ sur $+$ (pour une forme disjonctive) où de $+$ sur $\times$ (pour une forme conjonctive).

Dans le cas de la fonction donnée plus haut, on aurait:

où la dernière ligne est bien une forme disjonctive, mais pas canonique (on obtient en fait la fonction simplifiée, comme on le verra plus loin). On voit qu’il est normalement nécessaire de se servir des différentes propriétés pour arriver à une expression qui est relativement plus simple à traiter.

Obtention des formes normales

Il existe cependant un moyen d’obtenir les FND ou FNC facilement en travaillant sur la table de vérité. On s’intéresse aux différents cas pour $a$, $b$ et $c$ et on regarde ce que cette fonction retourne :

Obtenir la FND

Pour la FND, on s’intéresse aux cas pour lesquels la fonction vaut ${1}$ et pour lesquels on écrit la conjonction des littéraux (qu’on appelle des minterms) correspondante :

1. $a=b=1$ et $c=0$. Ce premier cas donne la conjonction $a\cdot b\cdot\bar{c}$, et la table de vérité de la fonction nous dis que celle-ci donne 1 pour résultat lorsque $a=1$, $b=1$ et $c=0$, or $1\cdot 1\cdot \bar{0}=1$.
2. $a=1$ et $b=0$, soit $c=1$ et on a la conjonction $a\cdot\bar{b}\cdot c$, soit $c=0$ et on a la conjoinction $a\cdot\bar{b}\cdot\bar{c}$.

La forme normale disjonctive (FND) est obtenue en prenant la disjonction de ces différentes conjonctions, donc $f(a,b,c)=a\cdot b\cdot\bar{c}+a\cdot\bar{b}\cdot c+a\cdot\bar{b}\cdot\bar{c}$. On aurait ceci dit pu l’obtenir comme suis:

(mais c’est quand même plus facile avec la table de vérité)

Obtenir la FNC

On s’intéresse aux cas où la fonction vaut 0 (qu’on appelle des maxterms) , et de la même manière, on note les différentes conjonctions correspondantes. On obtient alors

qui correspond à l’inverse de la fonction $f(a,b,c)$. Si on en prend la conjonction, la propriété d’involution assure que $\overline{\rule{0em}{1.05em}\overline{f(a,b,c)}} = f(a,b,c)$, mais la loi de De Morgan nous permet alors d’obtenir:

… Qui est bien la forme normale conjonctive (FNC).

Obtenir la forme normale est certes pratique, mais le but final est en fait de simplifier cette forme, afin d’avoir le moins d’opérations possibles à faire. On a vu plus haut qu’il était en fait possible, à l’aide des différentes propriétés, de simplifier une fonction booléenne, néanmoins, il existe une manière de faire plus simple, basée sur les diagrammes de Karnaugh (ou tables de Karnaugh), qui a le bon goût d’être une méthode graphique.

La méthode

Tout d’abord, il faut savoir comment construire ces fameux diagrammes de Karnaugh : il s’agit d’une autre manière de représenter la table de vérité ci-dessus.

1. Pour trois variables, un diagramme contient 8 cellules (16 cellules pour 4 variables).
2. Chacune de ces cases correspond à une série de valeur pour les différentes variables : ainsi, pour 3 variables, $a, b$ et $c$, on aurait par exemple, le triplet ${001}$ (donc $a={0}, b={0}$ et $c={1}$).
3. La règle est que quand on passe d’une case de ce diagramme à une autre, seule une variable peut changer de valeur (la numération suit un code de Gray). Ainsi, on peut passer de ${001}$ à ${011}$ mais pas à ${010}$. Dès lors, on ordonne le diagramme de telle manière à ce que les deux premières colonnes aient une valeur de $a=1$, tandis que ce sont les colonnes du milieu qui auront une valeur pour $b$ égale à 1. Comme ça, on a la série ${10, 11, 01, 00}$ pour $a$ et $b$. On fait de même pour les lignes (c’est tout à fait arbitraire).
4. De manière évidente, un triplet ou quadruplet donné ne peut se retrouver que dans une seule cellule.

On obtient par exemple les diagrammes suivants :

Il suffit alors de remplir ce diagramme en plaçant 1 aux endroits où la fonction vaut 1, 0 ailleurs. Il suffit de reprendre la table de vérité et de mettre ce qu’il faut au bon endroit. Dans le cas de notre fonction, on obtient le diagramme suivant.

La règle de simplification est assez simple : si deux cellules contenant la même valeur sont contiguës, c’est qu’elles peuvent être simplifiées. En effet, ces deux cellules contiennent forcément une même série de littéraux, $f$, multipliée par un atome, $p$, nié dans une cellule et non-nié dans l’autre. Dès lors,

$f\cdot p + f\cdot\bar{p} = f\,(p+\bar{p}) = f.$

Ce qui signifie qu’on élimine les atomes qui varient d’une cellule à l’autre, ou encore qu’on ne conserve que les littéraux qui ne changent pas. De la même manière, on peut simplifier 4 cellules contiguës (en ligne, en colonne ou en « carré «) d’un coup, voir également 8 cellules contiguës, si elles sont présentes (2 lignes ou 2 colonnes dans un diagramme 4x4, du coup). On peut considérer plusieurs fois une même cellule, puisque $f = f + f$ par idempotence.

Simplifier la FND

Pour obtenir une fonction disjonctive simplifiée, on travaille sur les endroits du diagramme où la fonction vaut 1.

Dès lors, dans le cas de $f(a,b,c)$, on constate que les deux cellules de la première colonne valent 1 (entourées en vert), ainsi que les deux premières cellules de la deuxième ligne (entourées en bleu).

1. Pour la simplification des cellules entourées en vert : il s’agit de la formule $a\cdot\bar{b}\cdot c +a\cdot\bar{b}\cdot\bar{c}$, où on voit que c’est $c$ qui est l’atome nié et non nié. On obtient donc la conjonction $a\cdot\bar{b}$
2. Pour la simplification en bleu : $a\cdot \bar{b}\cdot\bar{c} + a\cdot b\cdot\bar{c} = a\cdot \bar{c}$, puisque $b$ est l’atome nié et non-nié dans ce cas.

On obtient dès lors la forme disjonctive simplifiée suivante : $f(a,b,c)=a\cdot\bar{b}+a\cdot \bar{c}$, comme prévu.

Simplifier la FNC

On travaille sur la partie du diagramme où la fonction vaut 0, ce qui permet en fait d’obtenir une forme simplifiée pour $\overline{f(a,b,c)}$ sous forme disjonctive, puis forme conjonctive simplifiée par la loi de De Morgan, ainsi qu’expliqué plus haut.

Au niveau de notre exemple, on constate qu’on a une série de 4 cellules contiguës (en rose), et deux cellules contiguës à la première ligne, en deuxième et troisième colonne (en orange).

1. Pour la simplification en rose : $\bar{a}\cdot b\cdot c + \bar{a}\cdot b\cdot\bar{c}+\bar{a}\cdot \bar{b}\cdot c+\bar{a}\cdot\bar{b}\cdot\bar{c}=\bar{a}$, car on voit que sont niés et non-niés les atomes $b$ et $c$, ce qui permet de tous les simplifier.
2. Pour la simplification en orange : $a\cdot b\cdot c + \bar{a}\cdot b\cdot c = b\cdot c$, puisqu’ici, c’est l’atome $a$ qui est nié et non-nié.

On obtient alors $\overline{f(a,b,c)} = \bar{a} +b\cdot c$, ce qui permet d’obtenir une forme conjonctive simplifiée comme suit :

$\overline{\overline{f(a,b,c)}} = \overline{\bar{a}+b\cdot c} = a\,(\bar{b}+\bar{c}).$

À noter qu’on aurait pu l’obtenir à partir de la forme disjonctive simplifiée en mettant en évidence $a$.

Attention, le diagramme de Karnaugh est cyclique !

Et j’insiste :

Voyons ça sur un second exemple : soit une fonction $g(a,b,c,d)$ qui donnerait le diagramme de Karnaugh suivant.

Le nombre de possibilité pour former des groupes de 2 ou 4 cellules est considérablement accru à cause de ça. Par exemple, on peut très bien proposer les groupements suivants.

Du coup, la stratégie va être :

1. D’abord tenter de faire des groupes de 8, puis de 4 et puis de 2 cellules (et attention à ce qui se passe sur les bords, donc).
2. Pas besoin de former un groupe si toutes les cases en questions appartiennent déjà à d’autres groupes.

Sachant cela, quelle serait la forme disjonctive et conjonctive réduite correspondante au diagramme donné plus haut ?

« Don’t cares » ?

Un autre cas intéressant à traiter, c’est le cas où on ne s’intéresse pas au résultat pour certaines valeurs. L’exemple classique, c’est l’afficheur 7 segments, qui permet d’afficher les nombres sur une calculette ou un réveil digital (ou un écran du même type).

Chaque « segment » est une LED qu’on allume ou éteint en fonction du chiffre qu’on souhaite afficher. Ces segments sont désignés par des lettres, par facilité.

Il s’agit d’un bon exemple, puisqu’on pourrait par exemple se demander, en fonction du nombre à afficher, s’il est nécessaire d’allumer, disons, le segment G. On voit dans l’image ci-dessus que pour représenter les nombres de 0 à 9, 4 bits sont nécessaires, appelons-les $a_1$, $a_2$, $a_3$ et $a_4$. Par exemple, pour représenter 5, on aura $a_1={0}, a_2={1}, a_3={0}$ et $a_4={1}$. Et la suite, c’est évidement une petite table de vérité, où on va chercher la fonction $G(a_1,a_2,a_3,a_4)$, qui vaudra 1 quand le segment G sera allumé, 0 sinon.

Oui, mais quand on va réaliser notre table de Karnaugh, quelle valeur mettre pour, par exemple, ${1011}$ (11 en décimal) ? L’afficheur ne peut pas afficher de nombre plus grand que 9, évidement¹ … Eh bien on s’en fout (c’est un comportement indéterminé, qui ne devrait pas arriver), on met un don’t care, qu’on va symboliser par un « X ».

Notez qu’on écrit également cette fonction

où $m()$ (pour minterms) sont les valeurs pour lesquelles la fonction vaudra 1 et $d()$ (pour don’t care) sont les valeurs qui ne nous intéressent pas. L’écrire en binaire (dessous) ou en décimal (dessus) revient évidement au même. Les termes qui ne sont pas cités (0, 1 et 7) sont ceux pour lesquels la fonction vaut 0.

On a donc le diagramme suivant.

L’avantage des « X », c’est qu’ils peuvent valoir 0 ou 1, au choix. Voilà qui ouvre évidement plus de possibilités de simplifications ! Je vous laisse réfléchir au résultat.

Conclusion

La méthode de Karnaugh est relativement simple à mettre en place et fonctionne bien … Pour peu que le nombre de variables soit faible (puisqu’il y a $2^n$ possibilités pour $n$ variables). On va voir une seconde méthode légèrement plus simple à expliquer à un ordinateur pour qu’il fasse le taf’.

Présentation de l’algorithme

La méthode de Quine-Mc Cluskey se déroule en deux temps : la recherche de termes dit « générateurs » et l’élimination des termes redondants (suivi éventuellement de la méthode de Petrick pour choisir entre termes). C’est un algorithme taillé pour être traduit en code informatique, mais dont l’explication n’est pas très compliquée (son application est par contre un peu fastidieuse). Voyons ça sur un exemple.

Reprenons la fonction pour le segment G et voyons comment générer sa forme simplifiée. Pour rappel :

Première étape

Nous allons commencer par regrouper les minterms (et les valeurs « X ») en fonction du nombre de 1 qu’ils contiennent. Par facilité, on va aussi les classer par ordre croissant à l’intérieur de chaque groupe :

$\begin{array}{l} G_1 \begin{cases} m(2) &0010\\ m(4)&0100\\ m(8)&1000\\ \end{cases}\\ G_2 \begin{cases} m(3)&0011\\ m(5)&0101\\ m(6)&0110\\ m(9)&1001\\ d(10)&1010\\ d(12)&1100\\ \end{cases}\\ G_3 \begin{cases} d(11)&1011\\ d(13)&1101\\ d(14)&1110\\ \end{cases}\\ G_4 \begin{cases} m(15)&1111\\ \end{cases}\\ \end{array}$

On va ensuite combiner les termes qui ne varient que d’un chiffre, pour générer l’ordre 1. Par exemple, $m(2)$ (notation pour minterm 2) peut être combiné avec $m(3)$, puisque ceux-ci ne varient que d’un chiffre. On écrira ce nouveau terme $m(2,3) = 001x$ (comme dans la méthode de Karnaugh, ces termes peuvent être combinés de telle manière que $a_4$ disparaisse, d’où le $x$¹). À noter qu’une fois qu’un terme est utilisé, il est marqué comme tel (mais peut être réutilisé si nécessaire). L’avantage d’avoir trié en fonction du nombre de 1, c’est que les termes du groupe 1 ne peuvent être combinés qu’avec les termes du groupe 2, ceux du groupe 2 uniquement avec ceux du groupe 3, et ainsi de suite. En effet, on élimine les termes redondants, et $m(3,2)=001x$ donnant la même chose que $m(2,3)$, il n’est pas nécessaire de le garder.

Dès lors, on obtient :

$\begin{array}{l} G_1+G_2 \begin{cases} m(2,3) & 001x\\ m(2,6) & 0x10\\ m(2,10)&x010\\ m(4,5) & 010x\\ m(4,6) &01x0\\ m(4,12)&x100\\ m(8,9)&100x\\ m(8,10)&10x0\\ m(8,12)&1x00\\ \end{cases}\\ G_2+G_3 \begin{cases} m(3,11) & x011\\ m(5,13)& x101\\ m(6,14)& x110\\ m(9,11)& 10x1\\ m(9,13)& 1x01\\ m(10,11) & 101x\\ m(10,14) & 1x10\\ m(12,13) & 110x\\ m(12,14) & 11x0 \end{cases}\\ G_3+G_4 \begin{cases} m(11,15) & 1x11\\ m(13,15) & 11x1\\ m(14,15) & 111x\\ \end{cases}\\ \end{array}$

Pour générer l’ordre 2, on regroupe les termes (encore une fois, avec ceux du groupe suivant) de telle manière à ce que les $x$ soient à la même position, et que, encore une fois, le reste ne diffère que d’un chiffre. Ainsi, $m(2,3)=001x$ peut être combiné avec $m(10,11)101x$ puisque le $x$ est en dernière position dans les deux cas et le chiffre qui varie est le premier. On aura donc $m(2,3,10,11)=x01x$. Pareil, notez qu’on obtient la même chose en combinant $m(2,10)=x010$ avec $m(3,11)=x011$, d’où $m(2,10,3,11)=x01x$. Une fois encore, comme ce terme est redondant, on l’élimine. Notez que des termes redondants contiennent à chaque fois les mêmes minterms de base (ici : 2, 3, 10 et 11), il suffit donc de garder la combinaison dans l’ordre croissant et d’éliminer toutes les autres. Les autres termes de l’ordre 2 ne peuvent pas être combinés.

$\begin{array}{l} G_1+G_2+G_3 \begin{cases} m(2,3,10,11)&x01x\\ m(2,6,10,14)&xx10\\ m(4,5,12,13)&x10x\\ m(4,6,12,14)&x1x0\\ m(8,9,10,11)&10xx\\ m(8,9,12,13)&1x0x\\ m(8,10,12,14) &1xx0\\ \end{cases}\\ G_2+G_3+G_4\begin{cases} m(9,11,13,15) & 1xx1\\ m(10,11,14,15) & 1x1x\\ m(12,13,14,15) & 11xx\\ \end{cases}\\ \end{array}$

Finalement, on refait l’étape une troisième fois (et dernière fois, comme il n’y a que 4 variables). Dans ce cas-ci, on peut grouper $m(8,9,10,11)$ avec $m(12,13,14,15)$ pour obtenir $m(8,9,10,11,12,13,14,15)=1xxx$. On obtient également la même chose en combinant $m(8,10,12,14)$ avec $m(9,11,13,15)$, donc pas besoin de le retenir. Et finalement, on obtient encore une fois la même chose avec $m(8,9,12,13)$ et $m(10,11,14,15)$.

Conclusion de tout ça, on se retrouve avec les termes suivants : $m(2,3,10,11)=x01x$, $m(2,6,10,14)=xx10$, $m(4,5,12,13)=x10x$, $m(4,6,12,14)=x1x0$ (termes non utilisés de l’ordre 2) et $m(8,9,10,11,12,13,14,15)=1xxx$. Il s’agit des termes générateurs (ou implicants premiers), la première étape de l’algorithme est complète. On peut constater que le terme $m(8,9,10,11,12,13,14,15)$ avait déjà été obtenu par la méthode de Karnaugh plus haut. En effet, et même si c’est pas forcément visible, la méthode employée reste la même (par contre, elle est plus facile à expliquer à un ordinateur) !

Deuxième étape

La deuxième étape d’élimination des termes redondants passe par la réalisation d’une table des implicants (ou monômes) premiers.

On réalise un tableau où les entrées des lignes sont composées des termes générateurs, et les entrées des colonnes sont composées des minterms (on élimine cette fois les membres de $d()$, puisqu’ils ne sont pas importants). On remplit alors le tableau en indiquant si le terme générateur peut exprimer le minterm. Par exemple, dans le cas de $m(2,3,10,11)=x01x$, celui-ci permet d’exprimer 2 et 3 (10 et 11 ne nous intéressent pas).

Dans ce cas, on obtient :

Termes générateurs	${0010}$ (2)	${0011}$ (3)	${0100}$ (4)	${0101}$ (5)	${0110}$ (6)	${1000}$ (8)	${1001}$ (9)
$m(2,3,10,11)=x01x$	X	X
$m(2,6,10,14)=xx10$	X				X
$m(4,5,12,13)=x10x$			X	X
$m(4,6,12,14)=x1x0$			X		X
$m(8,9,10,11,12,13,14,15)=1xxx$						X	X

La première chose à faire, c’est de regarder quels sont les termes essentiels, en regardant quelles sont les colonnes dans lesquelles il n’y a qu’une seule croix. Ici, on voit que le terme $m(8,9,10,11,12,13,14,15)=1xxx$ est le seul permettant d’exprimer 8 et 9, il est donc essentiel. On voit également que 3 ne peut être exprimé que par $m(2,3,10,11)=x01x$ et que 5 ne peut être exprimé que par $m(4,5,12,13)=x10x$, qui sont donc essentiels. Pour les traduire en fonction booléenne, on ne considère que les termes qui ne sont pas $x$, et on a donc $m(8,9,10,11,12,13,14,15)=a_1$, $m(2,3,10,11)=\bar a_2 \cdot a_3$, $m(4,5,12,13)=a_2\cdot \bar a_3$. Il s’agit bien d’éléments de notre fonction simplifiée obtenue par Karnaugh.

Le « problème », c’est que aucun de ces 3 termes essentiels ne permet d’exprimer 6, pour lequel il faut choisir entre $m(2,6,10,14)=xx10$ et $m(4,6,12,14)=x1x0$, dont l’un des deux est redondant. On pourrait choisir au hasard (et tomber dans ce cas-ci sur la bonne réponse quoiqu’il arrive), mais une méthode plus sûre est d’utiliser soit la réduction par domination, soit la méthode de Petrick (en), qui seront expliquées plus bas.

Ici, on peut en fait éliminer n’importe laquelle des deux lignes. Si on élimine la deuxième, on voit qu’on tombe sur $m(2,6,10,14)=a_3\cdot \bar a_4$, qui est bien le dernier terme manquant à notre fonction simplifiée telle qu’obtenue par Karnaugh. Sinon, on peut éliminer la première ligne, qui permet d’obtenir $m(4,6,12,14)=a_2\cdot \bar a_4$, qui est également possible. En effet, si on regarde le diagramme de Karnaugh, on voit qu’il y a deux possibilités.

Un autre exemple pour bien comprendre la deuxième étape de l’algorithme

Intéressons-nous maintenant à la fonction suivante (qui n’a probablement pas d’intérêt autre que didactique):

$Q(a,b,c,d)=\sum m(0,3,5,6,7,8,9,13,14).$

dont je vous épargne la recherche des termes générateurs (en fait ça s’arrête à l’ordre 1) pour vous donner tout de suite la table des implicants premiers.

Termes générateurs	0	3	5	6	7	8	9	13	14
$m(0,8)=x000$	X					X
$m(3,7)=0x11$		X			X
$m(5,7)=01x1$			X		X
$m(5,13)=x101$			X					X
$m(6,7)=011x$				X	X
$m(6,14)=x110$				X					X
$m(8,9)=100x$						X	X
$m(9,13)=1x01$							X	X

Tout d’abord, on voit que les termes essentiels sont $m(0,8)$, $m(3,7)$ et $m(6,14)$, car ils sont les seuls à pouvoir exprimer 0, 3 et 14, respectivement.

On peut obtenir une table réduite en enlevant les termes essentiels et en éliminant les colonnes correspondantes (ainsi que les colonnes pour 6, 7 et 8, qui sont déjà couverts par ces termes essentiels). Ici, on peut également enlever le terme $m(6,7)$ qui n’exprime rien de plus que ces 3 termes essentiels.

Termes générateurs	5	9	13
$m(5,7)=01x1$	X
$m(5,13)=x101$	X		X
$m(8,9)=100x$		X
$m(9,13)=1x01$		X	X

Voyons maintenant comment faire le choix parmi touts ces termes redondants.

Par dominance

La règle de dominance est ainsi énoncée : « une colonne (ou ligne) est dominante relativement à une autre colonne (ou rangée) si elle contient toutes les “x” de l’autre, et au moins un “x” en plus ».

Ici, aucune colonne n’égale ou ne domine une autre (elles contiennent le même nombre de « X » plus au moins 1). Par contre, on a de la domination dans les lignes : $m(5,7)$ est dominée par $m(5,13)$ et peut donc être éliminée. De même, $m(8,9)$ est dominée par $m(9,13)$, donc elle disparaît. On obtient alors la table suivante.

Termes générateurs	5	9	13
$m(5,13)=x101$	X		X
$m(9,13)=1x01$		X	X

On voit alors que les deux termes restants sont essentiels, puisqu’ils permettent d’exprimer 5 et 9, respectivement. La fonction simplifiée est donc :

$Q(a,b,c,d)=\bar b\cdot \bar c \cdot \bar d + \bar a \cdot c \cdot d + b\cdot c \cdot \bar d + b \cdot \bar c \cdot d+a\cdot \bar c \cdot d.$

Par la méthode de Petrick

On repart donc de la table simplifiée des implicants premiers, dans laquelle ont été rajoutés les numéros de lignes (étape 1) :

Termes générateurs	Conjonction	5	9	13
$m(5,7)=01x1$	$L_1=\bar a\cdot b\cdot d$	X
$m(5,13)=x101$	$L_2=b\cdot \bar c\cdot d$	X		X
$m(8,9)=100x$	$L_3=a\cdot \bar b\cdot \bar c$		X
$m(9,13)=1x01$	$L_4=a\cdot \bar c\cdot d$		X	X

On voit que la fonction qu’on obtient (étape 2 et 3) est :

$P = \underbrace{(L_1+L_2)}_{5}\cdot \underbrace{(L_3+L_4)}_{9}\cdot\underbrace{(L_2+L_4)}_{13},$

qui exprime simplement que la fonction finale doit être composée de tout les minterms restant (5, 9 et 13), d’où la conjonction, tandis que les disjonctions pour chacun de ceux-ci exprime qu’on peut choisir parmi les termes.

On la simplifie (étape 4) comme suit :

On a donc 3 combinaisons possibles (étape 5) :

1. $L_2$ et $L_3$, qui donnent la somme $b\cdot \bar c \cdot d + a\cdot\bar b \cdot \bar c$, soit 5 littéraux différents ($b$ et $\bar b$ sont deux littéraux différents) ;
2. $L_2$ et $L_4$, qui donnent la somme $b\cdot \bar c \cdot d + a\cdot\bar c \cdot d$, soit 4 littéraux différents ;
3. $L_1$ et $L_4$, qui donnent la somme suivante $\bar a\cdot b\cdot d + a\cdot\bar c \cdot d$, soit 5 littéraux différents.

On voit donc bien que c’est $L_2$ et $L_4$ qui doivent être sélectionnées, ce qui était ce qu’on avait obtenu avec la réduction par dominance, et donc la fonction booléenne simplifiée est la même.

Conclusion

Encore une fois, cet algorithme n’est qu’une variation de la méthode de Karnaugh, mais est plus simple à expliquer à un ordinateur afin qu’il simplifie les fonctions booléennes pour nous. Une version encore plus efficace existe ceci dit, nommée Espresso (en), exploitée par le programme du même nom et dont un certain nombre d’implémentations existent.