NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 25/07/2022

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                               

     

LOGIQUE

 

Débutants

Logique

OUTILS

 

Glossaire

Logique

 

 

INDEX

 

Logique

Diagramme de Venn

Diagramme de Karnaugh

Intégrammes

 

Sommaire de cette page

>>> Diagramme de Karnaugh

>>> Lecture du tableau

>>> Exemple

>>> Application

>>> Diagramme de Lewis Carroll

 

 

 

 

Diagramme (ou tableau) de KARNAUGH

ou

 Diagramme de VEITCH-KARNAUGH

 

Moyen graphique commode de pour représenter des fonctions logiques. Analyse de toutes les possibilités logiques de plusieurs variables et optimisation des fonctions.

 

Anglais: Karnaugh map

 Voir Biographies de Maurice Karnaugh et de Edward Veitch

 

 

DIAGRAMME DE KARNAUGH 

 

Principe

 

*    Diagramme utilisé en calcul booléen.

*    Représentation schématique des ensembles par des rectangles qui s'emboîtent.

 

Définition

 

*    Méthode de simplification pratique d'une expression booléenne (logique) par utilisation un diagramme rectangulaire donnant la valeur résultat (cœur du tableau) en fonction des valeurs d'entrée (bordures du tableau).

*    Au lieu de décrire toutes les cases du tableau, l'astuce consiste à repérer visuellement les plus grands groupes communs.

*    La représentation logique de ces groupes est en principe plus condensée (optimisée) que l'énumération au cas par cas.

 

 

Diagramme de KARNAUGH

 

Lecture

 

*    Pour caractériser la sortie, il suffit de donner les cas où sa valeur est égale à 1.
Nous avons deux possibilités:

*      Énoncer tous les cas:
 

 

 

Lecture du tableau

 

*    Le tableau ci-dessus indique les valeurs que prend la fonction de sortie S pour les différentes valeurs des variables d'entrée A, B et C.

*      Par exemple: A = 0 et B = 0 et C  = 0  alors S = 0 (cellule en haut à gauche);

*      Si A = 1 et B = 1 et C  = 1  alors S = 1.

*    Pour caractériser la sortie, il suffit de donner les cas où sa valeur est égale à 1.
Nous avons deux possibilités: énoncer tous les cas ou les regrouper.

 

Énoncer tous les cas

 

*    Nous avons remplacé les 1 de la fonction de sortie par les fonctions logiques des cases correspondantes. ABC veut dire A et B et C; un A surmonté d'une barre veut dire Non-A (ou si vous préférez, cas où A = 0).

 

 

*    La fonction de sortie S est à 1 dès que l'une des cellules est à 1. L'une ou l'autre.
Le signe + représente le OU.

 

Regroupement (optimisation)

 

*    Un simple coup d'œil montre des régions complètes où se trouvent des 1.

Voyez comme sur cet exemple simple la fonction de sortie se résume à  S = A ou B. Dès que A ou B est à 1 (ou les deux à la fois), la fonction de sortie est à 1

 


 

 

 

 

 

Exemple

 

*      Expression logique reflétant la table de vérité ci-contre :

F = A.B.nC.nD

+ A.B.nc.D
+ A.B.C.nD
+ A.B.C.D
+ A.nB.nC.D
+ A.nB.nC.nD
+ A.nB.C.D
+ A.nB.C.nD
+ nA.B.C.nD
+ nA.B.nC.nD
+ nA.B.C.nD
+ nA.B.nC.nD

 

F

 

A

nA

 

 

nC

C

C

nC

B

nD

1

1

1

1

D

1

1

0

0

nB

D

1

1

0

0

nD

1

1

1

1

 

Conventions:

A     veut dire que la variable A est vraie et vaut 1.

nA   veut dire que la variable A est fausse et vaut 0.

 

 

Simplification

 

*      Expression logique reflétant toute la partie gauche du tableau

Elle est égale à 1 pour A = 1 quelle que soit la valeur de B, C et D

Soit

Fg = A

*      Expression logique reflétant la ligne haute et la ligne basse

Elle est égale à 1 pour nD = 1 quelle que soit la valeur de A, B et C

Soit

Fl = nD

 

 

*    En résumé F est à 1

lorsque Fg est à 1 ou bien

lorsque Fl est à 1 ou encore

si les deux sont à 1

 

F = Fg + Fl

F = A + nD

 

Cette expression toute simple est égale à celle de la liste des douze termes ci-dessus

 

 

F

 

A

nA

 

 

nC

C

C

nC

B

nD

1

1

1

1

D

1

1

0

0

nB

D

1

1

0

0

nD

1

1

1

1

 

 

 

 

F

 

A

nA

 

 

nC

C

C

nC

B

nD

1

1

1

1

D

1

1

0

0

nB

D

1

1

0

0

nD

1

1

1

1

 

 

Application – Résolution d'un problème

 


 Ma bibliothèque

 

Trouver la composition de ma bibliothèque, sachant que j’ai:

*      52 livres d’histoire dont 27 en anglais,

*      34 livres reliés dont 3 d’histoire en français,

*      46 livres en anglais, la moitié étant brochée,

*      20 livres de littérature en français, et

*      31 livres brochés de littérature.

 

Diagramme de Karnaugh

 

 

 

Broché

Relié

 

 

 

 

Histoire

 

 

 

 

 

Littérature

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Français

Anglais

Français

On ouvre les lignes et colonnes nécessaires:

-         en blanc les quantités selon les rubriques

-         en bleu selon les catégories

 

 

Introduction des données

 

 

Broché

Relié

 

 

 

34

Histoire

52

 

a

27 – a

3

Littérature

 

b

31 – b

 

20 – b

 

 

 

23

23

 

 

 

 

46

 

 

 

Français

Anglais

Français

Par exemple 52 livres d'histoire

-         dont 27 en anglais

-         répartis entre a brochés et 27 – a reliés

 

 

Déductions

 

 

Broché

Relié

 

 

 

34

Histoire

52

22

a

27 – a

3

Littérature

 

b

31 – b

a – 4

20 – b

 

 

22 + b

23

23

11

 

 

22 + b

46

11

 

 

Français

Anglais

Français

Par exemple

-         52 – (a – 27 + a – 3) = 22

-         34 – 23 = 11

 

 

 

 

Broché

Relié

 

 

53 + a

45 + b

34

46 – b

Histoire

52

22

a

27 – a

3

Littérature

27 + b

b

31 – b

a – 4

20 – b

 

 

22 + b

23

23

11

 

79 + b

22 + b

46

11

 

 

Français

Anglais

Français

Par exemple

-         22 + a + b + 31 – b = 53 + a

-         22 + b + 23 = 45 + b

Système d'équations

-         46 – b = 34 => b = 12

-         53 + a = 45 + b = 57 => a = 4

 

 Bilan

 

 

Broché

Relié

 

 

57

34

Histoire

52

22

4

23

3

Littérature

39

12

19

0

8

 

 

 

23

23

 

 

91

34

46

11

 

 

Français

Anglais

Français

 

 

 

 

 Anecdote: une sévère leçon pour débutant!

Alors jeune ingénieur, concepteur de systèmes logiques, et tout imbu de cette belle théorie de l'optimisation avec diagrammes de Karnaugh, je récupère le fruit de mes cogitations. Un magnifique panier (rack) de cartes électroniques juste sorti de production.

Avec mes collaborateurs, nous entamons la mise au point. En ce temps-là (fin des années 1960, les tous débuts des circuits logiques intégrés), les oscilloscopes n'avaient que deux sondes (pas encore d'analyseurs logiques multi-traces).

L'optimisation m'avait conduit à coder tous les états du système sur les combinaisons de huit bits. Mais, problème! Impossible de les observer avec deux sondes seulement. J'ai dû revoir mes circuits pour isoler les états du système sur un seul bit. L'optimisation aux oubliettes. La mise au point fut possible et le système vite admis en service opérationnel. 

 

 

Diagramme de Lewis Carroll

 

Lewis Carroll utilisait des diagrammes de cette sorte pour résoudre ses énigmes (proches des tableaux de Karnaugh ou des diagrammes de Venn).

 

En haut, cas de deux variables. Celles-ci sont notées dans le tableau.

 

En bas, cas de trois variables. 9a se complique un peu.

 

 

Ces diagrammes pouvaient même être ternaires. Par exemple:

*      aucun x n’est A,

*      au moins un x est A,

*      tous les x sont A).

 

Lewis Carroll utilisait ces diagrammes surtout à des fins pédagogiques. Il a écrit un livre intitulé "The Game of Logic" destiné à enseigner la logique aux enfants.

 

Voir le site en anglais:  The Logic Diagrams Of Lewis Carroll

 

 

 

 

Suite

*         Intégrammes

*         Paradoxe de Lewis Carroll

Voir

*         Énigme des 5 hommes, 5 maisons …

*         Énigmes et paradoxes

*         Intelligence artificielle

*         Jeux - Index

*         Logique booléenne

*         Logique formelle

*         Raisonnement

Cette page

http://villemin.gerard.free.fr/LogForm/Karnaugh.htm