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

Simplification par Karnaugh

Les tableaux de Karnaugh permettent d'obtenir les formes disjonctives ou conjonctives simplifiées en regroupant des termes (représentés par 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 on remarque qu’à côté des regroupements traditionnels il en existe qui ne sont plus contigus (flèche sur le dessin). Une technique plus intéressante consiste à réaliser un tableau de Karnaugh dans l'espace.

Il s'agit de réaliser deux tableaux de Karnaugh, 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 une puissance de deux cases.

Pour éviter cela on utilise la simplification algébrique.

Simplification algébrique

Ce chapitre utilise les propriétés de l'algèbre de Boole expliquée ici : ( Algèbre de Boole)

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

Noms	forme disjonctive	forme conjonctive
élément neutre	a . 1 = a	a + 0 = a
élément absorbant	a . 0 = 0	a + 1 = 1
idempotence	a . a = a	a + a = a
complément	$a.{\bar {a}}=0$	$a+{\bar {a}}=1$
commutativité	a . b = b . a	a + b = b + a
associativité	(a . b) . c = a . (b . c)	(a + b) + c = a + (b + c)
distributivité	a . (b + c) = a . b + a . c	a + (b . c) = (a + b).(a + c)
Relation diverse	a + (a . b) = a	a . (a + b) = a
Relation diverse	$a+({\bar {a}}.b)=a+b$	$a.({\bar {a}}+b)=a+b$
Relation diverse	$a+({\overline {a.b}})=1$	$a.({\overline {a+b}})=0$
Relation diverse	$a.({\overline {a.b}})=a.{\bar {b}}$	$a+({\overline {a+b}})=a+{\bar {b}}$
de Morgan	${\overline {a.b}}={\bar {a}}+{\bar {b}}$	$({\overline {a+b}})={\bar {a}}.{\bar {b}}$
de Morgan	$a.b={\overline {{\bar {a}}+{\bar {b}}}}$	$(a+b)={\overline {{\bar {a}}.{\bar {b}}}}$
consensus	$a.b+{\bar {a}}.c+b.c=a.b+{\bar {a}}.c$	$(a+b).({\bar {a}}+c).(b+c)=(a+b).({\bar {a}}+c)$
consensus généralisé	$a.b+{\bar {a}}.c+b.c.d=a.b+{\bar {a}}.c$	$(a+b).({\bar {a}}+c).(b+c+d)=(a+b).({\bar {a}}+c)$

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.

Exemple de combinaison :

$a.{\bar {b}}.{\bar {c}}+a.{\bar {b}}.c=a.{\bar {b}}$

Exemple d'inclusion

$a.{\bar {b}}.{\bar {c}}\subset a.{\bar {b}}$

donne :

$a.{\bar {b}}.{\bar {c}}+a.{\bar {b}}=a.{\bar {b}}$

Exercices

Exercice 1

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

$y_{1}={\bar {a}}.b.c+a.c+(a+b).{\bar {c}}$

$y_{2}=b.c+a.c+a.b+b$

$y_{3}=(a.{\bar {b}}+c).(a+{\bar {b}}).c$

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

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

$y_{6}=({\bar {a}}.b+a.{\bar {b}}).({\bar {a}}.{\bar {b}}+a.b)$

Exercice 2

Complémenter puis simplifier

$A=a.b+b.c+a.{\bar {c}}$

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