Licence CC BY-NC

L'algèbre de Boole

Publié :

Vous allez voir qu’on va ré-exprimer ce qu’on a vu au chapitre précédent sous une forme légèrement différente, mais qui va nous permettre de travailler de manière plus efficace avec ces variables propositionnelles. Vous allez voir que c’est moins compliqué qu’il n’y parait.

L’algèbre de Boole, telle qu’utilisée ici, n’est en fait qu’une façon légèrement différente de formaliser les choses : on se base en fait sur la théorie des ensembles (en travaillant avec un ensemble à deux éléments, B={0,1}\mathbb{B}=\{\mathfrak{ 0,}\mathfrak{ 1\}}), et on rajoute deux opérations (ou plutôt deux lois), qui sont le ++ et le ×\times. L’objet qu’on crée alors s’appelle une « algèbre de Boole à deux éléments » et possède différentes propriétés intéressantes qu’on va exploiter ici.

Propriétés de 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+ba+b. Cette opération est équivalente au connecteur OU, donc a+b=0a+b=0 si a=b=0a=b={0}.
  • La conjonction, a×ba\times b, qu’on peut également écrire aba\cdot b ou encore plus simplement abab. C’est l’équivalent du connecteur ET, donc ab=1a\cdot b={1} si a=b=1a=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 :

Nom Axiome pour ×\times Axiome pour ++
Neutre a1=aa\cdot { 1=a} a+0=aa+{ 0=a}
Inverse aaˉ=0a\cdot\bar{a}=0 a+aˉ=1a+\bar{a}=1
Commutativité ab=baab=ba a+b=b+aa+b=b+a
Distributivité a(b+c)=ab+aca\,(b+c)= ab+ac a+bc=(a+b)(a+c)a+bc=(a+b)\,(a+c)

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

Qu’est-ce qu’on a là ?
  • L’axiome du neutre est assez logique au vu de ce que vous avez appris en math : il existe, pour chacune des deux opérations, une valeur qui ne change pas le résultat. Ces valeurs sont d’ailleurs les mêmes que d’habitude, puisque n’importe quoi multiplié par 1 ou additionné de 0 reste le même.
  • L’axiome suivant (aussi appelé axiome de complémentation) signale la présence d’un inverse. Ça a l’air très compliqué, mais ça nous permet en fait de retrouver quelque chose qu’on a déjà vu : pour tout atome, aa, il existe sa négation, qu’on note ici aˉ\bar{a} (certains notent aussi aa'). Comme on l’a vu au chapitre précédent, 1ˉ=0\bar{1}=0 et 0ˉ=1\bar{0}= 1. Là où c’est moins intuitif, c’est que dans les mathématiques classiques, la multiplication par l’inverse (a1a^{-1} pour la multiplication) donne 1, et l’addition de l’inverse (a-a pour l’addition) donne 0, alors que c’est l’inverse ici.
  • Les troisième et quatrième axiomes, la commutativité et la distributivité, sont assez classiques pour la multiplication, moins pour l’addition (l’addition n’est pas distributive en algèbre classique). Mais ce n’est pas l’addition classique, donc ça tombe bien ^^

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 10{ 1 }\leftrightarrow 0 et +×+ \leftrightarrow \times. Ainsi, si on reprend le premier axiome pour ×\times, aaˉ=0a\cdot\bar{a}=0, on voit qu’on obtient bien l’axiome correspondant pour ++ (son dual) en remplaçant \cdot par ++ et 00 par 11.2

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

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

Nom Propriété de ×\times Propriété de ++
Associativité a(bc)=(ab)ca\,(b\cdot c) = (a\cdot b)\,c a+(b+c)=(a+b)+ca+(b+c)=(a+b)+c
Involution aˉˉ=a\bar{\bar{a}}=a de même
Idempotence aa=aa\cdot a = a a+a=aa+a=a
Élément absorbant a0=0a\cdot{ 0=}0 a+1=1a+{ 1=}1
Loi de De Morgan ab=aˉ+bˉ\overline{ab}=\bar{a}+\bar{b} a+b=aˉbˉ\overline{a+b} = \bar{a}\cdot\bar{b}
Théorème d’absorption a(a+b)=aa\,(a+b)=a a+ab=aa+ab=a
Théorème d’allègement a(aˉ+b)=aba\,(\bar{a}+b)=a\cdot b a+aˉb=a+ba+\bar{a}\cdot b=a+b
Théorème du consensus ab+aˉc+bc=ab+aˉcab+\bar{a}c+bc=ab+\bar{a}c (a+b)(aˉ+c)(b+c)=(a+b)(aˉ+c)(a+b)\,(\bar{a}+c)\,(b+c) = (a+b)\,(\bar{a}+c)

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.


  1. Pour rappel, je suis chimiste de formation, donc ça me fait sourire ;)

  2. Ça va même plus loin que ça, puisque si on réussit à prouver une propriété pour un opérateur, son dual est également prouvé.

  3. Les preuves des différentes propriétés sont disponibles à différents endroits sur internet, par exemple ici (en). Vous pouvez par ailleurs vous amuser à les vérifier en écrivant des tables de vérité, même si certaines sont triviales.

Fonctions booléennes

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:EmGn:e1,,emg1,,gnf:\mathcal{E}^m\rightarrow \mathcal{G}^n: e_1,\ldots,e_m\mapsto g_1,\ldots,g_n

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

Micmaths a déjà consacré un excellent cours aux fonctions, que je vous conseille de relire pour vous rafraîchir la mémoire, le cas échéant :)

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(bc)a\land(b\lor c) est « traduite », dans l’algèbre de Boole, par f(a,b,c)=a(b+c)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)=ab+acf(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(bc)+(aˉ+b).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=m1m2mnf=m_1\cdot m_2 \ldots m_n, avec mim_i la clause disjonctive, c’est-à-dire une disjonction de littéraux (q1+q2++qnq_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=m1+m2+mnf=m_1+m_2\ldots+m_n, mi=q1q2qnm_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:

f(a,b,c)=a(bc)+(aˉ+b)=a(bˉ+cˉ)+aˉˉbˉ(De Morgan)=a(bˉ+cˉ)+abˉ(involution)=abˉ+acˉ+abˉ(distributiviteˊ)=abˉ+acˉ(idempotence)\begin{aligned} f(a,b,c) &= a\cdot\overline{(b\cdot c)}+\overline{(\bar{a}+b)}\\ &= a\,(\bar{b}+\bar{c})+\bar{\bar{a}}\cdot\bar{b} & (\text{De Morgan}) \\ &= a\,(\bar{b}+\bar{c})+a\cdot\bar{b} & (\text{involution}) \\ &=a\cdot\bar{b} + a\cdot\bar{c} +a\cdot\bar{b} & (\text{distributivité}) \\ &=a\cdot\bar{b} + a\cdot\bar{c} & (\text{idempotence}) %\\ \end{aligned}

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 aa, bb et cc et on regarde ce que cette fonction retourne :

aa bb cc f(a,b,c)f(a,b,c)
1 1 1 0
1 1 0 1
1 0 1 1
1 0 0 1
0 1 1 0
0 1 0 0
0 0 1 0
0 0 0 0

Obtenir la FND

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

  1. a=b=1a=b=1 et c=0c=0. Ce premier cas donne la conjonction abcˉ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=1a=1, b=1b=1 et c=0c=0, or 110ˉ=11\cdot 1\cdot \bar{0}=1.
  2. a=1a=1 et b=0b=0, soit c=1c=1 et on a la conjonction abˉca\cdot\bar{b}\cdot c, soit c=0c=0 et on a la conjoinction abˉcˉ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)=abcˉ+abˉc+abˉcˉ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:

f(a,b,c)=abˉ+acˉ=abˉ1+acˉ1(neutre)=abˉ(c+cˉ)+acˉ(b+bˉ)(complmentationeˊ)=abˉc+abˉcˉ+abcˉ+abˉcˉ(distributiviteˊ)=abcˉ+abˉc+abˉcˉ(idempotence)\begin{aligned} f(a,b,c)&=a\cdot\bar{b} + a\cdot\bar{c}\\ &=a\cdot\bar{b}\cdot 1 + a\cdot\bar{c}\cdot {1} & (\text{neutre}) \\ &=a\cdot\bar{b}\,(c+\bar{c}) + a\cdot\bar{c}\,(b+\bar{b}) & (\text{complémentation}) \\ &=a\cdot\bar{b}\cdot c+a\cdot\bar{b}\cdot\bar{c} + a\cdot b\cdot\bar{c} +a\cdot\bar{b}\cdot\bar{c} & (\text{distributivité}) \\ &=a\cdot b\cdot\bar{c}+a\cdot\bar{b}\cdot c+a\cdot\bar{b}\cdot\bar{c}&(\text{idempotence}) \end{aligned}

(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

f(a,b,c)=abc+aˉbc+aˉbcˉ+aˉbˉc+aˉbˉcˉ,\begin{aligned} \overline{f(a,b,c)} = a\cdot b\cdot c+ \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}, \end{aligned}

qui correspond à l’inverse de la fonction f(a,b,c)f(a,b,c). Si on en prend la conjonction, la propriété d’involution assure que f(a,b,c)=f(a,b,c)\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:

f(a,b,c)=abc+aˉbc+aˉbcˉ+aˉbˉc+aˉbˉcˉ=(aˉ+bˉ+cˉ)(a+bˉ+cˉ)(a+bˉ+c)(a+b+cˉ)(a+b+c).\begin{aligned} \overline{\rule{0em}{1.05em}\overline{f(a,b,c)}} &= \overline{a\cdot b\cdot c+ \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+\bar b+\bar c)\,(a+\bar b+\bar c)\,(a+\bar b+c)\,(a+b+\bar c)\,(a+b+c). \end{aligned}

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

Simplifier une forme normale : la méthode de Karnaugh

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,ba, b et cc, on aurait par exemple, le triplet 001{001} (donc a=0,b=0a={0}, b={0} et c=1c={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{001} à 011{011} mais pas à 010{010}. Dès lors, on ordonne le diagramme de telle manière à ce que les deux premières colonnes aient une valeur de a=1a=1, tandis que ce sont les colonnes du milieu qui auront une valeur pour bb égale à 1. Comme ça, on a la série 10,11,01,00{10, 11, 01, 00} pour aa et bb. 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 :

CH2 : Karnaugh maps
Diagrammes de Karnaugh pour 3 variables (dessus) et 4 variables (dessous). Les lignes et colonnes marquées par une variable et une ligne désigne les zones où ces variables valent 1. Le choix est tout à fait arbitraire, on pourrait très bien décider de mettre cc et dd sur les lignes à la place de aa et bb, voir de les inverser. L’important c’est de bien respecter la règle qui dit que le changement d’une cellule à une autre (vers le haut, le bas, la gauche ou la droite) doit s’accompagner d’un et d’un seul changement de valeur.

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.

CH2 : diagramme pour la fonction f
Diagramme de Karnaugh pour la fonction f(a,b,c)f(a,b,c), en accord avec la table de vérité écrite plus haut.

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, ff, multipliée par un atome, pp, nié dans une cellule et non-nié dans l’autre. Dès lors,

fp+fpˉ=f(p+pˉ)=f.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+ff = 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)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).

CH2 : simplification de la FND
Simplification de la FND : 3 cellules sont contiguës. On constate que la cellule correspondante au triplet 100{100} est considérée deux fois.
  1. Pour la simplification des cellules entourées en vert : il s’agit de la formule abˉc+abˉcˉa\cdot\bar{b}\cdot c +a\cdot\bar{b}\cdot\bar{c}, où on voit que c’est cc qui est l’atome nié et non nié. On obtient donc la conjonction abˉa\cdot\bar{b}
  2. Pour la simplification en bleu : abˉcˉ+abcˉ=acˉa\cdot \bar{b}\cdot\bar{c} + a\cdot b\cdot\bar{c} = a\cdot \bar{c}, puisque bb 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)=abˉ+acˉ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 f(a,b,c)\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).

CH2 : simplification de la FNC
Simplification de la FNC : on constate que 4 cellules sont contiguës.
  1. Pour la simplification en rose : aˉbc+aˉbcˉ+aˉbˉc+aˉbˉcˉ=aˉ\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 bb et cc, ce qui permet de tous les simplifier.
  2. Pour la simplification en orange : abc+aˉbc=bca\cdot b\cdot c + \bar{a}\cdot b\cdot c = b\cdot c, puisqu’ici, c’est l’atome aa qui est nié et non-nié.

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

f(a,b,c)=aˉ+bc=a(bˉ+cˉ).\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 aa.

Attention, le diagramme de Karnaugh est cyclique !

Et j’insiste :

Puisque l’ordre est arbitraire (tant qu’on respecte la règle du 1-seul-changement-de-valeur-d’une-cellule-à-une-autre), ce qui signifie qu’un bord du diagramme est en fait le début de l’autre bord, et que ce qu’on considère comme plat est en fait un tore.

Le diagramme de Karnaugh représente en fait un tore (source: Wikipédia).

Il faut donc bien regarder sur les côtés si un plus grand groupement n’est pas possible. ;)

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

CH2 : diagramme de Karnaugh avec cycle
Une autre fonction, cette fois à 4 variables, g(a,b,c,d)g(a,b,c,d), pour varier les plaisirs.

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.

CH2 : groupements possibles
Groupement possibles de variables (évidement, il en manque). Les deux demi-cercles verts (et bleus) sont connectés, et se simplifient ensemble.

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 ?

CH2 : solution du diagramme complexe
Possibilités de groupement. J’avoue que la simplification en orange, il faut la voir. ;)

Groupes de 4 cellules :

  1. En vert : aˉbcdˉ+aˉbˉcdˉ+aˉbcˉdˉ+aˉbˉcˉdˉ=aˉdˉ\bar{a}\cdot b\cdot c\cdot\bar{d}+\bar{a}\cdot \bar{b}\cdot c\cdot\bar{d}+\bar{a}\cdot b\cdot\bar{c}\cdot\bar{d}+\bar{a}\cdot \bar{b}\cdot\bar{c}\cdot\bar{d} = \bar{a}\cdot\bar{d} ;
  2. En bleu : abˉcˉd+aˉbˉcˉd+abˉcˉdˉ+aˉbˉcˉdˉ=bˉcˉa\cdot\bar{b}\cdot\bar{c}\cdot d+\bar{a}\cdot\bar{b}\cdot\bar{c}\cdot d +a\cdot\bar{b}\cdot\bar{c}\cdot\bar{d}+\bar{a}\cdot\bar{b}\cdot\bar{c}\cdot\bar{d}=\bar{b}\cdot\bar{c} ;
  3. En rose : aˉbˉcd+aˉbˉcˉd+aˉbˉcdˉ+aˉbˉcˉdˉ=aˉbˉ\bar{a}\cdot \bar{b}\cdot c\cdot d+\bar{a}\cdot \bar{b}\cdot\bar{c}\cdot d+\bar{a}\cdot \bar{b}\cdot c\cdot \bar{d}+\bar{a}\cdot \bar{b}\cdot \bar c\cdot \bar{d}=\bar{a}\cdot \bar{b} ;
  4. En orange : abˉcdˉ+aˉbˉcdˉ+abˉcˉdˉ+aˉbˉcˉdˉ=bˉdˉa\cdot\bar{b}\cdot c\cdot\bar{d}+\bar{a}\cdot\bar{b}\cdot c\cdot\bar{d}+a\cdot\bar{b}\cdot\bar{c}\cdot\bar{d}+\bar{a}\cdot\bar{b}\cdot\bar{c}\cdot\bar{d}=\bar{b}\cdot\bar{d}.

Une forme disjonctive simplifiée serait donc :

g(a,b,c,d)=aˉdˉ+bˉcˉ+aˉbˉ+bˉdˉg(a,b,c,d)=\bar{a}\cdot\bar{d}+\bar{b}\cdot \bar{c}+\bar{a}\cdot\bar{b}+\bar{b}\cdot\bar{d}.

Pour ce qui est de la forme conjonctive, on groupe les cases de la manière suivante.

CH2 : cycle FNC
Groupement pour la FNC.

On trouve donc que g(a,b,c,d)=ab+bd+acd\overline{g(a,b,c,d)}=\textcolor{blue}{a\cdot b} + \textcolor{green}{b\cdot d}+\textcolor{magenta}{a\cdot c\cdot d}, dès lors, une forme conjonctive simplifiée est :

g(a,b,c,d)=ab+bd+acd=(aˉ+bˉ)(bˉ+dˉ)(aˉ+cˉ+dˉ)g(a,b,c,d) = \overline{a\cdot b + b\cdot d+a\cdot c\cdot d}=(\bar{a}+\bar{b})\,(\bar{b}+\bar{d})\,(\bar{a}+\bar{c}+\bar{d}).

Ce n’est pas des plus simple, mais il faut toujours chercher à faire des groupes avec la plus grande taille possible.

« 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).

CH2 : 7 segments
Afficheur 7 segments et représentation des 10 chiffres (la conversion en binaire de chacun des chiffres est donnée entre parenthèses).

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é.

CH2 : 7 segments : noms
Lettres utilisées pour désigner les segments dans un afficheur 7 segments (dixit Wikipédia).

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 a1a_1, a2a_2, a3a_3 et a4a_4. Par exemple, pour représenter 5, on aura a1=0,a2=1,a3=0a_1={0}, a_2={1}, a_3={0} et a4=1a_4={1}. Et la suite, c’est évidement une petite table de vérité, où on va chercher la fonction G(a1,a2,a3,a4)G(a_1,a_2,a_3,a_4), qui vaudra 1 quand le segment G sera allumé, 0 sinon.

Nombre a1a_1 a2a_2 a3a_3 a4a_4 G(a1,a2,a3,a4)G(a_1,a_2,a_3,a_4)
0 0 0 0 0 0
1 0 0 0 1 0
2 0 0 1 0 1
3 0 0 1 1 1
4 0 1 0 0 1
5 0 1 0 1 1
6 0 1 1 0 1
7 0 1 1 1 0
8 1 0 0 0 1
9 1 0 0 1 1

Oui, mais quand on va réaliser notre table de Karnaugh, quelle valeur mettre pour, par exemple, 1011{1011} (11 en décimal) ? L’afficheur ne peut pas afficher de nombre plus grand que 9, évidement1Eh 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

G(a1,a2,a3,a4)=m(2,3,4,5,6,8,9)+d(10,11,12,13,14,15)=m(0010,0011,0100,0101,0110,1000,1001)+d(1010,1011,1100,1101,1110,1111)\begin{aligned} G(a_1,a_2,a_3,a_4) &= \sum m(2,3,4,5,6,8,9) + \sum d(10,11,12,13,14,15) \\ &= \sum m({0010},{0011},{0100},{0101},{0110},{1000},{1001}) + \sum d({1010},{1011},{1100},{1101},{1110},{1111}) \end{aligned}

m()m() (pour minterms) sont les valeurs pour lesquelles la fonction vaudra 1 et d()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.

CH2 : G(a)
Il y a bien 7 « X » en tout. Attention, pour remplir le diagramme, ce n’est pas dans l’ordre numérique, il faut bien placer les valeurs correspondantes aux bons quadruplets a1a_1, a2a_2, a3a_3, a4a_4.

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. :pirate:

CH2 : G(a) (solution)
Groupements pour simplification de la FND.

Dès lors,

G(a1,a2,a3,a4)=a1+a3aˉ4+aˉ2a3+a2aˉ3.G(a_1,a_2,a_3,a_4)=\textcolor{green}{a_1}+\textcolor{magenta}{a_3\cdot \bar a_4}+\textcolor{blue}{\bar a_2\cdot a_3}+\textcolor{orange}{a_2\cdot \bar a_3}.

Évidement, rien ne vous empêche de faire le travail pour les autres segments. :magicien:

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 2n2^n possibilités pour nn variables). On va voir une seconde méthode légèrement plus simple à expliquer à un ordinateur pour qu’il fasse le taf’. ;)

Néanmoins, si vous voulez vérifier vos résultats, le site http://www.32x8.com/ le permet de manière simple et efficace, et ce jusqu’à 8 variables si vous êtes courageux (par contre il est en anglais).


  1. En fait, certains exploitent les nombres suivant pour afficher les 7 premières lettres de l’alphabet (a, b … f) afin de faire de l’hexadécimal. Mais pour l’exemple, on disait que.

Simplifier une forme normale : la méthode de Quine-Mc Cluskey

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 :

G(a1,a2,a3,a4)=m(2,3,4,5,6,8,9)+d(10,11,12,13,14,15)=m(0010,0011,0100,0101,0110,1000,1001)+d(1010,1011,1100,1101,1110,1111)\begin{aligned} G(a_1,a_2,a_3,a_4) &= \sum m(2,3,4,5,6,8,9) + \sum d(10,11,12,13,14,15) \\ &= \sum m({0010},{0011},{0100},{0101},{0110},{1000},{1001}) + \sum d({1010},{1011},{1100},{1101},{1110},{1111}) \end{aligned}

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 :

G1{m(2)0010m(4)0100m(8)1000G2{m(3)0011m(5)0101m(6)0110m(9)1001d(10)1010d(12)1100G3{d(11)1011d(13)1101d(14)1110G4{m(15)1111\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}
Regroupement des termes de m()m() et d()d() en fonction du nombre de 1 qu’ils contiennent pour G(a1,a2,a3,a4)G(a_1,a_2,a_3,a_4). On dit qu’il s’agit des termes à l’ordre 0.

On va ensuite combiner les termes qui ne varient que d’un chiffre, pour générer l’ordre 1. Par exemple, m(2)m(2) (notation pour minterm 2) peut être combiné avec m(3)m(3), puisque ceux-ci ne varient que d’un chiffre. On écrira ce nouveau terme m(2,3)=001xm(2,3) = 001x (comme dans la méthode de Karnaugh, ces termes peuvent être combinés de telle manière que a4a_4 disparaisse, d’où le xx1). À 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)=001xm(3,2)=001x donnant la même chose que m(2,3)m(2,3), il n’est pas nécessaire de le garder.

Dès lors, on obtient :

G1+G2{m(2,3)001xm(2,6)0x10m(2,10)x010m(4,5)010xm(4,6)01x0m(4,12)x100m(8,9)100xm(8,10)10x0m(8,12)1x00G2+G3{m(3,11)x011m(5,13)x101m(6,14)x110m(9,11)10x1m(9,13)1x01m(10,11)101xm(10,14)1x10m(12,13)110xm(12,14)11x0G3+G4{m(11,15)1x11m(13,15)11x1m(14,15)111x\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}
Termes à l’ordre 1. C’est un peu fastidieux, mais faisable. Tous les termes de l’ordre 0 ont été utilisé.

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 xx soient à la même position, et que, encore une fois, le reste ne diffère que d’un chiffre. Ainsi, m(2,3)=001xm(2,3)=001x peut être combiné avec m(10,11)101xm(10,11)101x puisque le xx 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)=x01xm(2,3,10,11)=x01x. Pareil, notez qu’on obtient la même chose en combinant m(2,10)=x010m(2,10)=x010 avec m(3,11)=x011m(3,11)=x011, d’où m(2,10,3,11)=x01xm(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.

G1+G2+G3{m(2,3,10,11)x01xm(2,6,10,14)xx10m(4,5,12,13)x10xm(4,6,12,14)x1x0m(8,9,10,11)10xxm(8,9,12,13)1x0xm(8,10,12,14)1xx0G2+G3+G4{m(9,11,13,15)1xx1m(10,11,14,15)1x1xm(12,13,14,15)11xx\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}
Termes à l’ordre 2. Énormément de choses se simplifient. Tous les termes de l’ordre 1 ont été utilisés.

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)m(8,9,10,11) avec m(12,13,14,15)m(12,13,14,15) pour obtenir m(8,9,10,11,12,13,14,15)=1xxxm(8,9,10,11,12,13,14,15)=1xxx. On obtient également la même chose en combinant m(8,10,12,14)m(8,10,12,14) avec m(9,11,13,15)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)m(8,9,12,13) et m(10,11,14,15)m(10,11,14,15).

Conclusion de tout ça, on se retrouve avec les termes suivants : m(2,3,10,11)=x01xm(2,3,10,11)=x01x, m(2,6,10,14)=xx10m(2,6,10,14)=xx10, m(4,5,12,13)=x10xm(4,5,12,13)=x10x, m(4,6,12,14)=x1x0m(4,6,12,14)=x1x0 (termes non utilisés de l’ordre 2) et m(8,9,10,11,12,13,14,15)=1xxxm(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)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) !

À noter qu’un implicant (en), c’est une combinaison de minterms d’une fonction booléenne donnée. Par exemple, si on a une fonction f(a,b,c)=ab+bˉc+acf(a,b,c)=a\cdot b+\bar b\cdot c + a\cdot c, alors aba\cdot b ou abca\cdot b\cdot c sont des implicants de ff. Un implicant premier, c’est un implicant qu’on ne peut plus simplifier par les lois de l’algèbre de Boole (qu’on ne peut pas exprimer avec moins de littéraux). Par exemple, aba\cdot b est un implicant premier de ff, par contre abca\cdot b \cdot c ne l’est pas : on peut soit retirer le cc pour obtenir l’implicant premier précédent, soit retirer le bb pour obtenir le troisième des implicant premier de ff, aca\cdot c. Ce que l’étape précédente nous à permis, c’est donc d’obtenir ces fameux implicants premiers (puisqu’on ne peut plus les combiner pour les simplifier).

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()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)=x01xm(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{0010} (2) 0011{0011} (3) 0100{0100} (4) 0101{0101} (5) 0110{0110} (6) 1000{1000} (8) 1001{1001} (9)
m(2,3,10,11)=x01xm(2,3,10,11)=x01x X X
m(2,6,10,14)=xx10m(2,6,10,14)=xx10 X X
m(4,5,12,13)=x10xm(4,5,12,13)=x10x X X
m(4,6,12,14)=x1x0m(4,6,12,14)=x1x0 X X
m(8,9,10,11,12,13,14,15)=1xxxm(8,9,10,11,12,13,14,15)=1xxx X X
Table des implicants premiers pour G(a1,a2,a3,a4)G(a_1,a_2,a_3,a_4). Les croix indiquent ce que les termes générateurs peuvent exprimer. Les croix impliquant des termes essentiels (voir ci-dessous) sont en gras.

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)=1xxxm(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)=x01xm(2,3,10,11)=x01x et que 5 ne peut être exprimé que par m(4,5,12,13)=x10xm(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 xx, et on a donc m(8,9,10,11,12,13,14,15)=a1m(8,9,10,11,12,13,14,15)=a_1, m(2,3,10,11)=aˉ2a3m(2,3,10,11)=\bar a_2 \cdot a_3, m(4,5,12,13)=a2aˉ3m(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)=xx10m(2,6,10,14)=xx10 et m(4,6,12,14)=x1x0m(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)=a3aˉ4m(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)=a2aˉ4m(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.

CH2 : mc 2 pos
Les deux possibilités de simplification pour G(a1,a2,a3,a4)G(a_1,a_2,a_3,a_4): a1+a3aˉ4+aˉ2a3+a2aˉ3\textcolor{green}{a_1}+\textcolor{magenta}{a_3\cdot \bar a_4}+\textcolor{blue}{\bar a_2\cdot a_3}+\textcolor{orange}{a_2\cdot \bar a_3} à gauche, a1+a2aˉ4+aˉ2a3+a2aˉ3\textcolor{green}{a_1}+\textcolor{magenta}{a_2\cdot \bar a_4}+\textcolor{blue}{\bar a_2\cdot a_3}+\textcolor{orange}{a_2\cdot \bar a_3} à droite.

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)=m(0,3,5,6,7,8,9,13,14).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)=x000m(0,8)=x000 X X
m(3,7)=0x11m(3,7)=0x11 X X
m(5,7)=01x1m(5,7)=01x1 X X
m(5,13)=x101m(5,13)=x101 X X
m(6,7)=011xm(6,7)=011x X X
m(6,14)=x110m(6,14)=x110 X X
m(8,9)=100xm(8,9)=100x X X
m(9,13)=1x01m(9,13)=1x01 X X
Tableau des implicants premiers pour Q(a,b,c,d)Q(a,b,c,d). Sont mises en gras les croix qui conduisent à des termes essentiels.

Tout d’abord, on voit que les termes essentiels sont m(0,8)m(0,8), m(3,7)m(3,7) et m(6,14)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)m(6,7) qui n’exprime rien de plus que ces 3 termes essentiels.

Termes générateurs 5 9 13
m(5,7)=01x1m(5,7)=01x1 X
m(5,13)=x101m(5,13)=x101 X X
m(8,9)=100xm(8,9)=100x X
m(9,13)=1x01m(9,13)=1x01 X X
Tableau simplifié des implicants premiers pour Q(a,b,c,d)Q(a,b,c,d).

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 ».

Méthode de la dominance
  1. On peut éliminer une colonne égale ou dominante par rapport à une autre (afin de réduite le nombre de termes).
  2. On peut éliminer une ligne égale ou dominée par rapport à une autre.
  3. On extrait alors les nouveaux termes essentiels, puis on recommence si nécessaire.

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)m(5,7) est dominée par m(5,13)m(5,13) et peut donc être éliminée. De même, m(8,9)m(8,9) est dominée par m(9,13)m(9,13), donc elle disparaît. On obtient alors la table suivante.

Termes générateurs 5 9 13
m(5,13)=x101m(5,13)=x101 X X
m(9,13)=1x01m(9,13)=1x01 X X
Tableau simplifié des implicants premiers pour Q(a,b,c,d)Q(a,b,c,d) après l’application de l’élimination par domination.

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)=bˉcˉdˉ+aˉcd+bcdˉ+bcˉd+acˉd.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

Méthode de Petrick
  1. On nomme chaque ligne (chaque terme) de la table des implicants réduite LiL_i, où ii est le numéro de la ligne (qui correspond donc à un terme redondant).
  2. Chaque colonne est représentée par une disjonction (une somme) de ligne.
  3. La fonction logique totale est représentée par la conjonction (un produit) des lignes.
  4. On distribue ensuite les termes, et on réduit par le théorème d’absorption (pour rappel, a+ab=aa+a\cdot b=a). On obtient donc une conjonction (une somme) de disjonction (un produit) de lignes.
  5. On sélectionne les produits avec le moins de littéraux. S’il y a plusieurs possibilités, on pourra alors choisir parmi ceux-ci.

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)=01x1m(5,7)=01x1 L1=aˉbdL_1=\bar a\cdot b\cdot d X
m(5,13)=x101m(5,13)=x101 L2=bcˉdL_2=b\cdot \bar c\cdot d X X
m(8,9)=100xm(8,9)=100x L3=abˉcˉL_3=a\cdot \bar b\cdot \bar c X
m(9,13)=1x01m(9,13)=1x01 L4=acˉdL_4=a\cdot \bar c\cdot d X X
Tableau simplifié des implicants premiers pour Q(a,b,c,d)Q(a,b,c,d).

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

P=(L1+L2)5(L3+L4)9(L2+L4)13,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 :

P=(L1+L2)(L3+L4)(L2+L4)=(L1L3+L1L4+L2L3+L2L4)(L2+L4)(distributiviteˊ)=L1L3L2+L1L4L2+L2L3L2+L2L4L2+L1L3L4+L1L4L4+L2L3L4+L2L4L4(distributiviteˊ)=L1L2L3+L1L2L4+L2L3+L2L4+L1L3L4+L1L4+L2L3L4(idempotence)=L2L3+L2L4+L1L4(absorption)\begin{aligned} P &= (L_1+L_2)(L_3+L_4)(L_2+L_4)\\ &= (L_1\cdot L_3 + L_1\cdot L_4 + L_2\cdot L_3 + L_2\cdot L_4)(L_2+L_4) & (\text{distributivité}) \\ &= L_1\cdot L_3\cdot L_2 + L_1\cdot L_4\cdot L_2 + L_2\cdot L_3\cdot L_2 + L_2\cdot L_4\cdot L_2 + L_1\cdot L_3\cdot L_4 + L_1\cdot L_4\cdot L_4 + L_2\cdot L_3\cdot L_4 + L_2\cdot L_4\cdot L_4 & (\text{distributivité}) \\ &= L_1\cdot L_2\cdot L_3 + L_1\cdot L_2\cdot L_4 + L_2\cdot L_3 + L_2\cdot L_4+ L_1\cdot L_3\cdot L_4 + L_1\cdot L_4 + L_2\cdot L_3\cdot L_4 & (\text{idempotence})\\ &= L_2\cdot L_3 + L_2\cdot L_4 + L_1\cdot L_4 &(\text{absorption}) \end{aligned}

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

  1. L2L_2 et L3L_3, qui donnent la somme bcˉd+abˉcˉb\cdot \bar c \cdot d + a\cdot\bar b \cdot \bar c, soit 5 littéraux différents (bb et bˉ\bar b sont deux littéraux différents) ;
  2. L2L_2 et L4L_4, qui donnent la somme bcˉd+acˉdb\cdot \bar c \cdot d + a\cdot\bar c \cdot d, soit 4 littéraux différents ;
  3. L1L_1 et L4L_4, qui donnent la somme suivante aˉbd+acˉd\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 L2L_2 et L4L_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.

À nouveau, tout ce travail peut être réalisé en ligne. Parmi le nombre d’implémentations disponibles, je me suis pris d’affection pour celle-ci, qui est une fois encore en anglais et utilise des tirets à la place des xx, mais qui présente bien chacune des étapes !


  1. On peut également mettre un tiret à la place du xx.


Dans ce chapitre, on a donc vu que l’algèbre de Boole permettait d’exprimer les mêmes choses que dans le chapitre précédent, mais sous une forme légèrement différente. On a aussi vu, et c’est très important, que ça nous permettait de simplifier ces fonctions logiques. On peut maintenant continuer notre périple pour aller voir comment on peut faire comprendre ça à une machine.

À tout de suite ;)