Voir la source de Électronique numérique : logique/Compléments sur la simplification

{{Sommaire|droite}}

=== Simplification par Karnaugh pour plus de quatre variables ===
Les [[w:Table_de_Karnaugh|tableaux de Karnaugh]] permettent d'obtenir les formes disjonctives ou conjonctives simplifiées en regroupant des termes (contenants des 1 ou des 0). Cela fonctionne très bien jusqu'à 4 variables. Que se passe-t-il après ?

Si l'on réalise un tableau de Karnaugh à 5 variables (partie gauche de la figure ci-dessous) on remarque qu'à côté des regroupements traditionnels il en existe qui ne sont plus contigus (flèche rouge sur le dessin). 

{{définition|définition = 
Pour deux cases distinctes, on parle de '''contiguïté géométrique (ou physique)''' si les deux cases qui sont l'une à côté de l'autre. Pour deux cases distinctes, on parle de '''contiguïté logique''' si les deux cases ne diffèrent que par une valeur logique.
}}

Ce qui fait l'intérêt des tableaux de Karnaugh c'est que la contiguïté géométrique est équivalente presque partout
à la contiguïté logique. Il n'y a que sur les bords où ce n'est plus vrai. Tout cela simplifie énormément les techniques de simplifications.

Cette propriété est perdue si l'on dépasse les 4 variables comme cela est montré dans la partie gauche de la figure ci-dessous. Oui les deux rectangles rouges se simplifient car passer de l'un à l'autre se fait par changement d'une seule variable seulement. Ils sont contigus logiquement mais malheureusement pas physiquement. La simplification est donc plus difficile à mettre en œuvre dans ce tableau de Karnaugh, mais pas impossible. On discute de ces tableaux de Karnaugh à cinq variables [[v:Logique_de_base/Tableau_de_Karnaugh2|dans un autre projet]]. 

Une technique plus intéressante consiste à réaliser un tableau de Karnaugh dans l'espace.

<u>'''ATTENTION'''</u> : les parties gauches et droites de cette figure ne correspondent pas à la même fonction logique !

La partie droite de la figure ci-dessus est composée de deux tableaux de Karnaugh superposés, un pour la cinquième variable e = 0 et un pour e = 1. On regroupe ensuite dans l'espace, sur un ou deux tableaux (avec des carrés, des rectangles, des cubes et des parallélépipèdes ayant tous un nombre de cases qui est une puissance de deux. En pratique on peut dessiner les tableaux de Karnaugh les uns à côté des autres et à se les imaginer superposés.

[[File:Karnaugh map KV 4mal4 Gruppe01v.svg|thumb|200px|Exemple de superposition pour six variables]]
Pour six variables, on peut utiliser 4 tableaux de karnaugh superposés (attention à l'ordre !), mais cette technique ne marche plus au-delà de six variables.

Pour éviter cette représentation spatiale (qui nécessite d'être un spécialiste de [[w:Tetris|tetris]] 3D), on utilise la simplification algébrique.

=== Simplification algébrique ===
Ce chapitre utilise les propriétés de l'algèbre de Boole expliquées ici : [[w:Alg%C3%A8bre_de_Boole_%28logique%29|Algèbre de Boole]].

{{définition|définition = Une '''transformation par dualité''' consiste à transformer chaque membre d'une égalité pour obtenir une nouvelle égalité. La transformation consiste à changer tous les 0 en 1, tous les 1 en 0, tous les + en . et tous les . en +. ATTENTION, la transformation par dualité d'une expression ne donne pas une expression égale.}}

La technique pour obtenir une forme disjonctive simplifiée consiste à effectuer les parenthèses et ensuite à appliquer une des règles suivantes :
; Tableau des identités remarquables
{| border cellspacing="0" width="650"
|- style = "background:#b3e2d1;text-align:center"
| Noms ||forme disjonctive||forme conjonctive
|- style="text-align:center"
|élément neutre||a . 1 = a||a + 0 = a
|- style="text-align:center"
|élément absorbant||a . 0 = 0||a + 1 = 1
|- style="text-align:center"
|idempotence||a . a = a||a + a = a
|- style="text-align:center"
|complément||<math>a . \bar{a} = 0</math>||<math>a + \bar{a} = 1</math>
|- style="text-align:center"
|commutativité || a . b = b . a||a + b = b + a
|- style="text-align:center"
|associativité ||(a . b) . c = a . (b . c)||(a + b) + c = a + (b + c)
|- style="text-align:center"
|distributivité||a . (b + c) = a . b + a . c||a + (b . c) = (a + b).(a + c)
|- style="text-align:center"
|Relation diverse||a + (a . b) = a||a . (a + b) = a
|- style="text-align:center"
|Relation diverse||<math>a + (\bar{a} . b) = a + b</math>||<math>a . (\bar{a} + b) = a . b</math>
|- style="text-align:center"
|Relation diverse||<math>a + (\overline{a . b}) = 1</math>||<math>a . (\overline{a + b}) = 0</math>
|- style="text-align:center"
|Relation diverse||<math>a . (\overline{a . b}) = a . \bar{b}</math>||<math>a + (\overline{a + b}) = a + \bar{b}</math>
|- style="text-align:center"
|de Morgan||<math>\overline{a . b} = \bar{a} + \bar{b}</math>||<math>(\overline{a + b}) = \bar{a} . \bar{b}</math>
|- style="text-align:center"
|de Morgan||<math>a . b = \overline{\bar{a} + \bar{b}}</math>||<math>(a + b) = \overline{\bar{a} . \bar{b}}</math>
|- style="text-align:center"
|consensus||<math>a . b + \bar{a} . c + b . c = a . b + \bar{a} . c</math>||<math>(a + b) . (\bar{a} + c) . (b + c) = (a + b) . (\bar{a} + c)</math>
|- style="text-align:center"
|consensus généralisé||<math>a . b + \bar{a} . c + b . c . d = a . b + \bar{a} . c</math>||<math>(a + b) . (\bar{a} + c) . (b + c + d) = (a + b) . (\bar{a} + c)</math>
|}
Au temps des débuts de la logique, ce tableau était à savoir par cœur. Aujourd'hui, il existe des outils informatiques qui permettent de simplifier. Les seules choses à connaître sont peut-être liées à l'inclusion et à la combinaison expliquées plus loin.
{{Début cadre|rouge}}
<u>'''Remarque importante'''</u> : il est possible de passer d'une colonne à l'autre par '''dualité'''. Cela veut dire que seule la moitié du tableau est à connaître ! Le reste s'en déduit tout simplement.
{{fin cadre}}
====Consensus====
Le '''consensus''' mérite que l'on s'y arrête. Simplifier par consensus est très simple à partir du moment où l'on est capable de le détecter. Si ce n'est pas le cas, il vous faudra plusieurs lignes pour le faire.
{{définition|définition = Pour qu'il y ait un consensus entre deux termes il faut que dans ces deux termes une variable apparaisse complémentée dans un terme et pas dans l'autre. '''Le consensus''' est le produit de ce qui reste si l'on enlève la variable en question.
}}
<u>Exemple</u> : <math>a . b + \bar{a} . c</math> il y a un consensus de a qui est b.c

{{définition|définition = Pour qu'il y ait une simplification par consensus, il faut qu'il y ait un consensus et qu'un autre terme contienne le consensus. Ce terme en question doit disparaître.
}}
<u>Exemple</u> : regardez les lignes du tableau ci-dessus pour consensus et consensus généralisé.

{{Début cadre|rouge}}
<u>'''Remarques'''</u> : 
* il ne faut pas confondre le consensus avec la simplification par consensus ! Il peut y avoir un consensus entre deux termes sans qu'il n'y ait de simplification par consensus.
* le consensus ne sert pas qu'à simplifier. Il peut être parfois volontairement ajouté pour éviter les [[w:Glitch|glitch]] mais nous n'aborderons pas ce problème ici.
{{fin cadre}}
====Simplifications algébriques====
Si l'on cherche une forme disjonctive simplifiée on peut procéder de la manière suivante :
* on effectue d'abord toutes les parenthèses pour trouver une forme disjonctive,
* on regroupe tous les termes qui ne diffèrent que d'une variable (combinaison) en ajoutant ces termes simplifiés,
* on retire ensuite tous les termes qui sont inclus dans d'autres termes,
* on cherche les simplifications par consensus.

Les combinaisons peuvent se faire plusieurs fois.

<u>Exemple de combinaison</u> :

<math>a . \bar{b} . \bar{c} +  a . \bar{b} . c = a . \bar{b}</math>

La simplification par combinaison demande  un peu de doigté (non exigé d'un étudiant de L1). Car si quatre termes se regroupent et que vous ne le voyez pas, vous pouvez faire des combinaisons dans le mauvais ordre. C'est pour cela que l'on vous dit d'ajouter les termes simplifiés : il permettront à la fin de retirer les termes initiaux par inclusion.

<u>Exemple d'inclusion</u>

<math>a . \bar{b} . \bar{c} \subset  a . \bar{b} </math>

qui permet de simplifier :

<math>a . \bar{b} . \bar{c} +  a . \bar{b} = a . \bar{b}</math>

Par '''dualité''', j'obtiens aussi :

<math>a + \bar{b} + \bar{c} \subset  a + \bar{b} </math>

qui permet de simplifier :

<math>(a + \bar{b} + \bar{c}) . ( a + \bar{b}) = a + \bar{b}</math>


=== Exercices ===
==== Exercice 1 ====
Utiliser les relations algébriques pour simplifier les équations suivantes et réaliser la synthèse en ET-NON.

<math>y_1 = \bar{a}.b.c + a.c + (a + b).\bar{c}</math>

<math>y_2 = b.c + a.c + a.b + b</math>

<math>y_3 = (a.\bar{b} + c).(a + \bar{b}).c </math>

<math>y_4 = (a.c + b.\bar{c}).(a + \bar{c}).b</math>

<math>y_5 = \bar{a}.b.c + a.c + (a + b).\bar{c}</math>

<math>y_6 = (\bar{a}.b + a.\bar{b}).(\bar{a}.\bar{b} + a.b)</math>

{{Boîte déroulante|titre=Elements de correction de l'exercice 1|contenu=
<math>y_1 = \bar{a}.b.c + a.c + (a + b).\bar{c} = \bar{a}.b.c + a.c + a.\bar{c} + b.\bar{c}</math>

#Une simplification par combinaison donne : <math>y_1 =  \bar{a}.b.c + a + b.\bar{c}</math>
#La distributivité du + par rapport au . donne : <math>y_1 =  (\bar{a}+a).(b+a).(c+a) + b.\bar{c}</math>
#Le premier terme vaut un et si l'on effectue, on trouve : <math>y_1 = b.c + a.c + b.a + a.a + b.\bar{c}</math>
#Simplification par inclusion : <math>y_1 = b.c + a + b.\bar{c}</math>
#Simplification par combinaison : <math>y_1 = a + b</math>

C'est long et fastidieux, mais une meilleure connaissance des relations diverses aurait permi de passer directment le la ligne 1. à la ligne 4.

y2 se simplifie par inclusion seulement pour donner y2 = b + a.c

Pour y3, le premier terme se simplifie par inclusion pour donner : <math>y_3 = (a + \bar{b}).c </math>
}}

==== Exercice 2 ====

Complémenter puis simplifier 

<math>A = a.b + b.c + a.\bar{c}</math>

<math>B = \bar{c}.\bar{d}  + \bar{a}.\bar{b} + c.\bar{d} + a.\bar{b}</math>

{{Sommaire|bas}}

{{Autres projets|v=Logique_de_base}}

[[Catégorie:Électronique numérique : logique (livre)|Compléments sur la simplification]]