Comme nous le verrons dans le chapitre suivant, nous serons parfois amenés à chercher une proposition étant donné sa table de vérité. En effet, parfois la liste des interprétations que l'on souhaite satisfaire nous sera donnée, et nous serons intéressés à trouver une proposition qui leur correspond. Nous allons donc étudier ici une méthode pour concevoir une proposition à partir de sa table de vérité.

Il est parfois simple de trouver une proposition à partir de sa table de vérité. En analysant la table de vérité, on peut souvent chercher à tâtons une proposition qui satisfait les interprétations désirées. De manière assez intuitive, le connecteur et permet d'ajouter des contraintes et le connecteur ou permet de les relaxer.

Cependant, parfois la tâche peut s'avérer complexe. Pour ces cas, nous allons voir une méthode systématique pour trouver une proposition à partir de sa table de vérité. Il s'agit de la méthode des tables de Karnaugh.

Tables de Karnaugh

La méthode des tables de Karnaugh est une méthode graphique qui permet de trouver une proposition à partir d'une table de vérité. La méthode se base sur une représentation en tableau des différentes interprétations. La présentation est légèrement différente de celle la table de vérité, et permet, comme vous allez le découvrir, de simplifier la tâche de recherche d'une proposition. La table de Karnaugh a une apparence différente selon le nombre de variables que l'on souhaite considérer.

Cas à deux variables

Commençons par le cas le plus simple, celui à deux variables. Voici à quoi ressemble une table de Karnaugh pour deux variables A et B :

Une table de Karnaugh est un tableau de cellules, ici au nombre de 4, pour le moment vides. La table de Karnaugh contient aussi des entêtes, avec soit une variable, soit la négation d'une variable.

De manière intéressante, le tableau est conçu afin que chaque cellule soit à l'intersection, pour chaque variable, soit de la variable elle-même, soit de sa négation.

• Ainsi, la cellule en haut à gauche correspond à la combinaison non A et non B.
• À sa droite se trouve la combinaison avec A et non B.
• En bas à gauche se trouve la combinaison avec non A et B.
• Finalement, en bas à droite la combinaison avec A et B.

Remplir la table de Karnaugh

Chaque cellule de la table correspond à une interprétation précise, c'est-à-dire à une valeur de vérité pour chaque variable. Pour savoir la valeur de vérité d'une variable X dans l'interprétation correspondant à une cellule, il suffit de regarder dans quelle ligne et quelle colonne la cellule se trouve. La valeur de vérité d'une variable X dans l'interprétation est de 0 si la cellule est couverte par non X et de 1 si, à l'inverse, la cellule est couverte par X.

• Ainsi, la cellule en haut à gauche correspond à l'interprétation A = 0, B = 0.
• En haut à droite se trouve l'interprétation A = 1, B = 0.
• En bas à gauche se trouve l'interprétation A = 0, B = 1.
• Finalement, en bas à droite l'interprétation A = 1, B = 1.

Il est ainsi relativement simple de remplir une table de Karnaugh à partir d'une table de vérité. Il suffit de reporter la valeur de vérité pour chaque interprétation dans la cellule correspondante.

Zones de la table de Karnaugh

Les tables de Karnaugh sont conçues de manière à ce que les cellules soient regroupées en zones facilement identifiables visuellement. Dans le cas de deux variables, ce sont :

• Les lignes.
• Les colonnes.
• Les cellules individuelles.

Prenons maintenant un instant pour visualiser les différentes zones de la table de Karnaugh. Chaque zone correspond un ensemble de variables ou de négations de variables. Les zones, en fonction de leur taille, peuvent faire intervenir une ou plusieurs variables.

Plus une zone fait intervenir de variables, plus elle est petite. Ainsi, les zones qui ne font intervenir qu'une seule variable ou sa négation recouvrent deux cellules, alors que les zones qui font intervenir deux variables ou leurs négations recouvrent une seule cellule.

Remarquez que les zones de la table de Karnaugh correspondent à des propositions. Chaque zone correspond à une conjonction (et) des variables ou de leurs négations.

Utiliser la table de Karnaugh

Une fois la table de Karnaugh remplie de 0 et de 1, il convient de l'utiliser ! La finalité, on le rappelle, est de former une proposition qui satisfait les interprétations désirées, et uniquement celles-ci. Pour cela, on va procéder de manière itérative, c'est-à-dire en appliquant successivement plusieurs fois la même opération.

L'opération à appliquer de manière répétée est la suivante : on cherche à former des groupes de cellules qui contiennent uniquement des 1, de manière à couvrir des cellules non préalablement couvertes. Les groupes ne sont cependant pas formés de manière arbitraire, ils doivent correspondre à une des zones de la table de Karnaugh telles que décrites plus haut. Ainsi, chaque groupe correspond à une proposition qui est une conjonction des variables ou de leurs négations. Les grands groupes sont préférables aux petits groupes, car ils correspondent à des propositions plus simples.

L'opération de former des groupes de 1 est répétée jusqu'à ce que toutes les cellules contenant des 1 soient couvertes par au moins un groupe.

Une fois les groupes formés, on calcule la proposition finale en formant la disjonction (ou) des propositions correspondant à chaque groupe.

Cas à trois variables

Le principe de fonctionnement des tables de Karnaugh reste le même pour le cas à trois variables, à la différence que la table est plus grande. Voici à quoi ressemble une table de Karnaugh pour trois variables A, B et C :

Il est intéressant de noter que, dans une table de Karnaugh, les cellules adjacentes correspondent à des interprétations qui ne diffèrent que par une seule variable. Ainsi, les cellules sémantiquement proches sont aussi visuellement proches. C'est cette propriété qui permet de facilement identifier des propositions dans la table de Karnaugh.

Zones de la table de Karnaugh

Les zones de la table de Karnaugh pour trois variables sont plus nombreuses que pour deux variables. Voici les différentes zones possibles :

Cas à quatre variables

Finalement, considérons le cas à quatre variables. Fondamentalement, le principe reste le même, bien que la table de Karnaugh soit plus grande. Voici à quoi ressemble une table de Karnaugh pour quatre variables A, B, C et D :

Zones de la table de Karnaugh

Les zones de la table de Karnaugh pour quatre variables sont encore plus nombreuses que pour trois variables. Voici les différentes zones possibles :

Conclusion

Les tables de Karnaugh sont un outil très utile pour simplifier des expressions logiques. Elles permettent de visualiser de manière claire les interprétations qui satisfont une expression logique, et ainsi de former des propositions qui satisfont ces interprétations.

Les tables de Karnaugh ont été présentées ici pour des cas à deux, trois et quatre variables, mais elles peuvent être utilisées pour un nombre quelconque de variables, bien que la praticité de l'outil diminue rapidement avec le nombre de variables à considérer.