Table de vérité et tableaux de Karnaugh

De WikiMéca
Aller à : navigation, rechercher

Table de vérité

Une table de vérité est un tableau qui représente des entrées (en colonne) et ses états binaire et une sortie, également représentée sous forme de colonne, est la résultante des états d'entrée, elle-même exprimée sous forme d'état binaire.

Exemple :

Table de vérité de a.(b + c)
a b c a.(b + c)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

On note les entrées "E" et les sorties "S".

Tableaux de Karnaugh

Un tableau de Karnaugh sert à simplifier des équations logiques ou à trouver l'équation logique correspondant à une table de vérité. La méthode utilisée est graphique et simple. Elle utilise également le Code de Gray ou binaire réfléchi, qui a comme propriété principale de ne faire varier qu'un seul bit entre deux mots successifs.

Construction du tableau

Pour une fonction à 4 variables a, b, c et d :

  • a et b seront placés en colonne,
  • c et d seront placés en ligne,

ce qui donne le tableau suivant :

F a b
0 0 0 1 1 1 1 0
c d 0 0
0 1
1 1
1 0

De ce fait, on se retrouve avec 16 cases vides, correspondant aux 16 combinaisons possible de 4 variables pouvant prendre 2 états.

L'utilisation du binaire réfléchi fait qu'entre deux cases voisines (en ligne ou en colonne) une seule variable change d'état ; on dit de telles cases qu'elles sont adjacentes.

Tableau-karnaugh-cases-adjacentes.PNG

Attention : Les case limitrophes sont adjacentes "par l'extérieur" du tableau. Il faut imaginer que le tableau se referme horizontalement et verticalement.

Exemple : Pour le tableau à 4 variables a,b,c et d, la case 0010 (en bas à gauche) est adjacente à 4 cases correspondant aux états : 0011, 0110, 1010 et 0000 (voir le tableau ci-contre).

Chacune de ces cases correspond à un état obtenu par changement d'un seul bit par rapport à l'état 0010.


Chaque combinaison offre 3 solutions possibles de l'état de sortie de la variable F :

  • 1 si la sortie est vraie
  • 0 si la sortie est fausse
  • X si la sortie est indéterminée, c'est-à-dire que, par exemple, le système ne peut pas fournir cette combinaison.

Voilà ce que peut donner un tableau rempli :

F a b
0 0 0 1 1 1 1 0
c d 0 0 0 0 1 1
0 1 1 1 1 0
1 1 0 X X 1
1 0 1 1 1 0

Résolution du tableau

Les regroupements

Il faut effectuer des regroupements de 1 ou de X , par cases adjacentes, par paquets de 1, 2, 4 ,8, 16....`2^n`. Ces regroupements doivent être des rectangles ou des carrés, et les plus grands possible sachant qu'un élément déjà utilisé peut être repris.

Exemple : avec ce tableau :

F a b
0 0 0 1 1 1 1 0
c d 0 0 0 0 1 1
0 1 1 1 1 1
1 1 0 0 0 1
1 0 0 0 1 1

on peut faire ces 3 regroupement :

F a b
0 0 0 1 1 1 1 0
c d 0 0 0 0 1 1
0 1 1 1 1 1
1 1 0 0 0 1
1 0 0 0 1 1
F a b
0 0 0 1 1 1 1 0
c d 0 0 0 0 1 1
0 1 1 1 1 1
1 1 0 0 0 1
1 0 0 0 1 1
F a b
0 0 0 1 1 1 1 0
c d 0 0 0 0 1 1
0 1 1 1 1 1
1 1 0 0 0 1
1 0 0 0 1 1
Premier regroupement Deuxième regroupement Troisième regroupement

Le suivant est inutile puisqu'il peut être fait par les 2 de gauche au dessus :

F a b
0 0 0 1 1 1 1 0
c d 0 0 0 0 1 1
0 1 1 1 1 1
1 1 0 0 0 1
1 0 0 0 1 1

La résolution des regroupements

Maintenant que l'on a pu, avec différentes regroupements, prendre tous les 1, on essaie de résoudre les regroupements. Pour cela, il faut que les variables participant au regroupement concerné ne changent pas.

  • Premier regroupement :

Dans les 4 cas possibles, la variable a est toujours à 1 et la variable d est toujours à 0
La solution bleue donne : `a . bar d` .

  • Deuxième regroupement :

Dans les 4 cas possibles, la variable c est toujours à 0 et la variable d est toujours à 1
La solution verte donne : `bar c.d`.

  • Troisième regroupement:

Dans les 4 cas possibles, la variable a est toujours à 1 et la variable b est toujours à 0
La solution rouge donne : `a. bar b` .

La solution finale du tableau est :

`F = a.bar d + bar c.d + a.bar b`

En toute logique, cette solution est réduite au maximum.


centre d'intérêt:logique