Tableau de Karnaugh

karnaugh table

Table / tableau de Karnaugh

 

Introduction

Ce post a pour but de vous donner quelques informations sur la mise en œuvre et l’utilisation d’une technique de résolution de problème de logique (combinatoire ou autres). Cette technique est appelée Tableau de Karnaugh ou Table de Karnaugh, du nom de son inventeur Maurice Karnaugh.

Une description grossière pourrait statuer que la méthode de Karnaugh permet une résolution graphique, par opposition à une résolution algébrique.

Je ne prétend pas ajouter de la nouveauté concernant l’utilisation de cette technique, bien entendu, mais je sais par expérience qu’une même technique expliquée par différentes sources conviendra à différents auditeurs.
J’espère donc que mon explication personnelle permettra à quelqu’un (voir même plusieurs!) de comprendre et appliquer cette méthode.

 

1 Résumé de la méthode

Voici le plan général de la méthode basée sur les tables de Karnaugh.
Notez bien que certains points de cette procédure sont communs a de nombreuses méthodes de résolution de problème logique.

  1. Déterminer la table de vérité du problème
  2. Déterminer le nombre de variables d’entrée afin de connaître la taille des tableaux,
  3. Déterminer le nombre de variables de sortie afin de définir le nombre de tableaux à effectuer,
  4. Affecter aux différents produits de l’équation non simplifiée une case du tableau en respectant le code de Gray (ou binaire réfléchi),
  5. Introduire la fonction logique dans le tableau en positionnant à « 1 » les cases qui valident la fonction de sortie,
  6. Effectuer les regroupements de cases adjacentes,
  7. Sortir la fonction simplifiée en éliminant la ou les variables d’entrée qui changent d’état.

 

 

2 Détails de la méthode

Cette section décrit en détails les différentes étapes de l’application de la technique des tables de Karnaugh décrites au chapitre précédent.

2.1 Déterminer la table de vérité du problème

Cette étape est commune à bien des méthodes de résolutions, voici en quoi elle consiste.

La table de vérité est en fait un simple résumé des différentes combinaisons de variables d’entrées et de leur résultat (résultat de la fonction), ce résultat est la plupart du temps exprimé sous forme d’une équation. Le nombres de lignes d’une table de vérité est égal a 2 puissance “nombre_de_variables_en_entrée“. Soit pour 4 variables en entrée, une table de vérité de 16 lignes.

  • Exemple :

Table de vérité de la fonction logique ET (AND)

Voici un exemple basé sur une fonction logique bien connue et très largement utilisée dans l’algèbre de Boole ainsi que dans tous les montages électroniques (duquel fait partie le CPU de votre PC par exemple) .

Cette fonction prend deux variables en entrée (A et B ici) et envoie un signal vers son unique sortie (C ici, mais qui est habituellement notée A.B). Cette fonction est VRAI lorsque ses deux entrées valent 1, voici donc la table de vérité de notre fonction ET (AND) :

A    B C (A.B)
0    0 0
0    1 0
1    0 0
1    1 1

Les deux premières colonnes définissent les valeurs possible de A et B, quand à la troisième colonne elle donne les résultats de la fonction ET.

 

2.2 Déterminer le nombre de variables d’entrée afin de connaître la taille des tableaux

Cette partie sert surtout à contrôler le travail en cours et permet d’éviter les aberrations logiques.

Il est très facile d’obtenir la taille (le nombre de cases) du tableau à venir grâce à la formule suivante :

N_cases = 2nombre_de_variables_en_entrée

  • Exemple :

Un problème avec 4 variables (P, L, l et H) en entrée donnera un  tableau de 24 cases (16 cases) tel que :

l.H\P.L 00 01 11 10
00 0 1 1 1
01 1 0 1 0
11 0 0 1 0
10 0 0 1 1

 

2.3 Déterminer le nombre de variables de sortie afin de définir le nombre de tableaux à effectuer

Cette partie est plus utile mais un peu plus complexe aussi que le point 2.2.

En effet grâce a cette réflexion nous allons pouvoir déterminer le nombre de tableaux de Karnaugh nécessaire à la résolution, mais pour cela il est obligatoire d’avoir bien analysé et compris le problème : cela implique dans la majorité des cas de savoir traduire un énoncé littéral en équations mathématiques (équations certes simples mais néanmoins nécessaires!).

Il y aura autant de tableaux de sortie que de variables de sorties.

  • Exemple :

Énoncé du problème
Contrôle de qualité de fabrication de briques
On dispose de 4 critères pour déterminer si une brique est bonne ou non :
– le poids P
– la longueur L
– la largeur l
– la hauteur H

En fonction de ces critères, les briques sont rangées suivant 3 catégories :

A. Poids et au moins deux dimensions correctes,
B. Seul le poids est incorrect, ou le poids est correct et une dimension est correcte au maximum,
C. Le poids est incorrect et 2 dimensions sont correctes au maximum.

 

Traduction du problème

Dans ce problème nous pouvons déduire qu’il y aura 3 variables de sorties : elles correspondent aux 3 catégories A, B et C.
Chacune de ces catégories sera le résultat d’une équation composée des 4 mesures (P, L, l et H).

Cette “traduction” peut-être modélisée comme suit :

brique

Cette partie (commune à tous les problèmes mathématique / logique et autres) est souvent la plus difficile, la suite n’est qu’application de méthode et/ou d’algorithme de résolution…

 

2.4 Affecter aux différents produits de l’équation non simplifiée une case du tableau en respectant le code de Gray (ou binaire réfléchi)

Il s’agit ici de créer la structure de la table de Karnaugh.

En utilisant la table de vérité précédemment créée nous allons remplir les cases correspondantes aux produits des différentes variables. Un exemple sera plus clair :

  • Exemple :

Imaginons une fonction prenant 4 variables en entrées, A, B, C et D (c’est original ça !), pour construire la table de Karnaugh nous allons devoir créer de toute pièce des produits entre ces variables. Ici les produits qui vous paraîtrons les plus simples / évidents (compte tenu du problème ou de la fonction) seront les meilleurs, puisqu’il n’y a ni règle ni obligation.

Je choisi ici de composer les deux produits A.B (A ET B) que je dispose en abscisse et C.D (C ET D) qui seront en ordonné. Il faut ensuite placer les différentes valeurs possibles de ces produits de variables en utilisant le code de gray.
Ce qui donne une table telle que :

C.D\A.B 00 01 11 10
00
01
11
10

 

2.5 Introduire la fonction logique dans la table au en positionnant à « 1 » les cases qui valident la fonction de sortie

Il s’agit maintenant de remplir le tableau de Karnaugh !

En nous basant sur la table de vérité nous allons remplir la table de Karnaugh : Dans cette phase il faut bien entendu veiller à respecter scrupuleusement les valeurs de la table de vérité (qui aura été remplie tout aussi scrupuleusement!)

  • Exemple :

Reprenons l’exemple de la section 2.1, à savoir la fonction ET logique (AND).
Pour rappel en voici la table de vérité :

A B C (A.B)
0 0 0
0 1 0
1 0 0
1 1 1

Remplissons maintenant le tableau de Karnaugh correspondant :
Rappel : N_cases
= 2nombre_de_variables_en_entrée ce qui dans notre cas donnera : 22 cases, c’est-à-dire 4 cases.

Voici la table vide, avec ses 4 cases :

B\A 0 1
0
1

Pour la remplir il nous faut nous reporter à la table de vérité, et prendre chacune des équations décrite dans celle-ci pour reporter le résultat sous forme de 1 (VRAI) et de 0 (FAUX).

  1. Prenons la première ligne de la table de vérité :
    A=0 ; B=0 et le résultat de A.B (prononcer A ET B), nommé ici C, est 0.

    1. Nous cherchons donc dans la table de Karnaugh la case correspondante à cette équation (A=0 ET B=0) : La première case (en haut à gauche) paraît correspondre parfaitement à cette description.
    2. Nous indiquons dans cette case le résultat tiré de la table de vérité. Ce résultat exprimé sous forme d’un 1 ou d’un 0 selon que cette équation est VRAI ou FAUSSE, dans notre cas elles est FAUSSE nous positionnons donc un 0 au croisement de ces ligne :
B\A 0 1
0 0
1

Il ne reste maintenant plus qu’a appliquer ceci au autres cases, ce qui nous donne finalement :

B\A 0 1
0 0 0
1 0 1

 

 2.6 Effectuer les regroupements de cases adjacentes

Nous abordons ici la partie la plus intéressante, pas tellement compliquée mais c’est une mécanique qu’il faut pratiquer quelques fois avant d’être à l’aise.

Selon la terminologie de Karnaugh un regroupement est un ensemble de cases adjacentes. Attention les cases adjacentes peuvent se trouver dans les endroits les plus inattendus, quelques un de ces exemples “inattendus” sont visible au bas de cette page.

Une seule restriction pour ces regroupements : il doit être composé d’un nombre de case égal à une puissance de deux (pas de regroupement de 6 cases par exemple !). En dehors de cette restriction il existe une règle simple à appliquer : Les regroupements doivent contenir le MAXIMUM de “1”, plus le regroupement contiendra de “1” plus l’équation résultante sera simple (aura un nombre de termes faible).

  • Exemple :

Pour cet exemple reprenons le tableau de la section 2.4, et remplissons le avec des valeurs imaginaires (et qui nous arrangent bien cela dit!).

Les regroupements sont ici colorés pour y voir plus clair :

 

2.7 Sortir la fonction simplifiée en éliminant la ou les variables d’entrée qui changent d’état

Comme indiqué dans le titre de cette section la déduction de la ou des équations se fait en se basant, pour chaque regroupement, sur la ou les (selon les cas) variable(s) qui changent d’état. Voyons la procédure pour l’exemple précédent :

  • Nous avons 5 couleurs donc 5 regroupements, prenons-les dans l’ordre :
  1. Le regroupement rose : il ne contient qu’une seule case et donnera donc lieu à une équation très peu simplifiée. Pour ce regroupement nous voyons que toutes les variable restent identiques (et pour cause elles ne bougent pas !), l’équation résultante sera donc composée de 2 termes, tels que :
    (A/.B/) + (C/.D)
    Note : la notation “A/” se lit et se prononce “A barre” elle signifie que la valeur de A est de 0 dans ce cas,  le signe “+” représente la fonction logique “OU”. De plus les parenthèses sont uniquement là pour rendre plus l’équation claire , elles ne sont habituellement pas utilisées dans ce genre de cas.
  2. Le regroupement jaune : il est composé de 4 “1” (4 cases) et donnera donc lieu à une équation assez simplifiée. Pour cette équation nous recherchons les variables qui ne changent pas d’état.
    Ces 4 “1” sont à cheval sur 2 lignes horizontales nous pouvons donc rechercher au sein des variables C et D celle qui ne change pas d’état : sur la première ligne C et D valent “1”, sur la seconde ligne C vaut “1” et D vaut “0”, nous voyons que seul C ne change pas et c’est donc C=1 que nous conservons lors de la construction de notre équation. Ce regroupement est également à cheval sur 2 colonnes, recherchons alors laquelle des variables A ou B reste stable : colonne de gauche A=0 et B=1, colonne de droite A=1 et B=1, ici c’est B qui reste stable, nous le gardons pour composer l’équation suivante :
    C.B
  3. Le regroupement rouge : il est lui aussi composé de 4 cases, et donne l’équation suivante :
    A.B
  4. Le regroupement vert : Ce type de regroupement “à cheval” est quelque fois difficile a trouver, une fois trouve il suffit de lui appliquer les mêmes règles qu’a n’importe quel regroupement, a savoir : rechercher les variables qui ne change pas d’état. Dans ce cas précis nous avons deux variables qui ne change sur ces 4 cases : A et D/ce qui nous donne l’équation suivante : A.D/
  5. Le regroupement marron : De même type que le précédent (vert) donne l’équation suivante :
    B.D/

L’équation finale sera de la forme :

f= ( A/.B/+C/.D ) + C.B + A.B +  A.D/ + B.D/

 

 

3 Conclusion

Comme on peut le voir sur cette page la résolution de problème logique est largement facilitée par la méthode de Karnaugh, mais cette méthode à néanmoins ses limites, il devient par exemple très difficile de gérer des problèmes impliquant plus de 5 variables. En espérant que ce post permettra a quelques uns d’entre vous de mieux comprendre comment appliquer cette méthode.

One thought on “Tableau de Karnaugh

  1. Bruno balhan

    Bonjour, je révise les tables avec mon fils, des années que je n’avais plus joué avec, par contre je crois que l’expression rouge dois s’écrire comme suit:
    A/. B/. C/ .D
    Il n’y a pas de ou !!!!!

    Salutations

Leave a Reply to Bruno balhan Cancel reply

Your email address will not be published. Required fields are marked *

This site supports SyntaxHighlighter via WP SyntaxHighlighter. It can highlight your code.
How to highlight your code: Paste your code in the comment form, select it and then click the language link button below. This will wrap your code in a <pre> tag and format it when submitted.