Tables de Karnaugh

•  Table de vérité : – qui simplifie en général la présentation

d'un problème logique (mathématique, électronique, micro-électronique, fiabilité des systèmes)

• Table de Karnaugh – est dans de nombreux cas un outil de

travail facile à manipuler– comporte donc autant de cases que de

combinaisons possibles de variables qui la composent (2n)

b a F

0 0 1

0 1 0

1 0 1

1 1 1

a \ b 0 1

0 1

āƃ

1

āb1 0

āb

1

ab

Exemple à 3 variables (1)

• La F.N.D est donc   • mais elle peut se simplifier algébriquement sous

la forme   • mais nous voyons que ceci peut encore se

simplifier en   • où nous voyons que les quatre cases adjacents

sont là où b vaut partout 1.

Exemple à 3 variables (2)

• Une autre manière de simplifier :

a \ bc 00 10 01 11

0 1 1 1 1

1 0 1 0 1

Tables de KarnaughChoix des dispositions

• Une difficulté subsiste cependant avec cette technique : comment choisir la meilleure construction du tableau (choix des lettres en colonnes ou en ligne) ?

• => associer la règle de complémentation de l'algèbre de Boole avec le "code Gray"

• Définition: Dans le code de Gray, deux termes successifs ne diffèrent que par un seul bit. Les termes ne différant que par un seul bit sont appelés "adjacents".

• En utilisant le code Gray nous pouvons créer des tables de Karnaugh optimales

Règles de simplification (1)

• R1. Deux 1 sont juxtaposés dans le tableau :

• R2. Quand deux 1 sont aux extrémités du tableau :

• R3. Quand une rangée pleine fait disparaître les deux variables  BA dans ce cas :

Règles de simplification

• R4. Une colonne pleine fait disparaître deux variables DC dans ce cas :

• R5. Quatre cases font disparaître deux variables A et C dans ce cas :

• R6. La même case peut servir à deux réductions :

• /B/D + /DBA /B/D + /DA

• R7. La même case peut servir à deux réductions :

• /D/C/B + /D/CA