Logique (sciences de l'ingénieur)/Exercices/TD4

Simplification par Karnaugh

Les tableaux de Karnaugh permettent d'obtenir les formes conjonctives simplifiées en regroupant des termes (représentés par des 0).

On peut avoir des regroupements de 2, 4, 8, 16…termes. Ce sont des puissances de 2. Pour obtenir la forme somme de produit simplifiée on regroupe les zéros du tableaux de Karnaugh pour obtenir /y. Puis on applique deux fois De Morgan : ${\bar {y}}=a.c+a.{\bar {b}}.{\bar {d}}+{\bar {a}}.b.{\bar {c}}$

soit :

$y={\overline {a.c+a.{\bar {b}}.{\bar {d}}+{\bar {a}}.b.{\bar {c}}}}$

J'applique une première fois de Morgan :

$y={\overline {(a.c)}}.{\overline {(a.{\bar {b}}.{\bar {d}})}}.{\overline {({\bar {a}}.b.{\bar {c}})}}$

puis une deuxième fois :

$y=({\bar {a}}+{\bar {c}}).({\bar {a}}+b+d).(a+{\bar {b}}+c)$

Sipour une raison quelconque une ou plusieurs combinaisons des entrées ne peut arriver, ce qui se passera en sortie n'a aucune importance pour ces combinaisons. On dit que l’on a des cas indéterminés. Ils sont traités comme dans le TD précédent.

Implantation d’une forme conjonctive

Une forme conjonctive, qu'elle soit simplifiée ou non, s'implante de manière naturelle en une structure OU-ET (les OU d’abord pour finir un ET). Cette forme OU-ET conduit directement, en utilisant De Morgan, à un schéma en OU-NON (NOR). Prenons comme exemple la forme simplifiée du tableau de Karnaugh précédent.

Pour obtenir un schéma en OU-NON (NOR) on part d’une forme conjonctive si possible simplifiée et on fait une schéma en trois couches OU/ET puis on transforme le ET final en OU-NON en faisant glisser les inverseurs de ses entrées. Le schéma obtenu est alors en trois couches mais utilise des portes à nombre d'entrées illimité. Si on limite le nombre d'entrées des OU-NON on ne limite alors plus le nombre de couches à trois. On peut partir d’un schéma trois couches et utiliser les équivalences. Elles sont tellement similaires aux équivalences du TD précédent qu’elles ne sont pas reproduites ici. De même pour les optimisations.

Exercice

Pour chacune des équations ci-dessous, trouver la forme disjonctive simplifiée, réaliser la synthèse trois couches avec des portes 0U-NON.

$y_{1}=a.(b+c)$ avec 3 portes

$y_{2}=a.b+{\bar {c}}$ avec 4 portes

$y_{3}={\bar {a}}.b+a.c$ avec 4 portes

$y_{4}={\bar {a}}.b+a.{\bar {b}}$ avec 5 portes

$y_{5}=(({\bar {a}}+b).(a+c)+b.c).(a+b+c)$ avec 4 portes

$y_{6}={\bar {a}}.b.{\bar {c}}+a.{\bar {b}}.c$ avec 7 portes