Sachant qu'une variable a
ne peut prendre que deux valeurs 1 ou 0,
on peut imaginer des fonctions f0
(a), f1 (a), f2
(a) figurant toutes les combinaisons possibles obtenues avec ces deux valeurs.
Nous voyons dans le tableau (figure
51) qu'il peut exister pour une variable 4 fonctions distinctes.
On a deux fonctions constantes :
f0 = 0 quel que soit a
f3 = 1 quel que soit a
Une fonction OUI : f1 = a
Une fonction NON: f2 =
3. 2. - FONCTIONS DE 2 VARIABLES
Le nombre de fonctions pour deux
variables est de 16 (figure 52).
On retrouve un certain nombre de
fonctions remarquables :
f0 = 0
quelques soient a et b
"fonction constante"
f15 = 1
quelques soient a et b
"fonction constante"
f3 = a
f5 = b
f12 =
fonction NON
f10 =
fonction NON
f1 = ab
fonction ET
f7 = a + b fonction OU INCLUSIF
On appelle f14ou
NAND (de l'anglais NO AND qui signifie NON ET).
On appelle f8ou
NOR (de l'anglais NO OR qui signifie NON OU).
On appelle f6OU EXCLUSIF que l'on note également :
f6 = a Å
b
On appelle f9identité logique que l'on note également :
a ≡
b
ou f9 = a
b
On remarque également les fonctions
:
f2 = a
f4 = b
f11 = a +
f13 =
+ b
3. 3. - SIMPLIFICATIONS ALGÉBRIQUES
3. 3. 1. - MONÔME
Nous avons vu pour deux variables un
certain nombre d'expressions algébriques.
Prenons la fonction f9 = ab + .
Nous dirons que l'expression algébrique ab + est un polynôme composé d'un monôme ab et d'un monôme .
En algèbre de Boole, un monôme est
une expression algébrique constituée du produit de plusieurs variables entre
elles, telles que abc, ab
... etc. Il est à noter qu'en algèbre de Boole
x .
x = x, il n'y a pas d'exposants tels que x2,
x4, cela n'existe pas.
3. 3. 2. - POLYNÔME
Un polynôme sera donc une somme de
monômes ou somme de produits.
3. 3. 3. - MONÔME ADJACENT
On appelle monômes adjacents les
monômes qui ne diffèrent les uns des autres que par une seule variable. Dans
une somme de deux monômes adjacents, la variable qui diffère s'élimine.
Exemple:
3. 3. 4. - RÉDUCTION ALGÉBRIQUE
Une méthode simple de réduction
algébrique est de rechercher les monômes adjacents après avoir mis
l'expression algébrique que l'on cherche à simplifier sous forme d'une somme
de produits ou polynômes que l'on appelle forme canonique. Ensuite, il suffira
de rechercher des simplifications de la même manière que nous avons fait pour
la propriété d'absorption et en utilisant les identités remarquables afin de
faire apparaître des simplifications.
Exemple N° 1:
On peut écrire :
Puisque nous savons que nous pouvons
rajouter xyz déjà présent autant de fois
que nous voulons sans changer la valeur de f.
Exemple N° 2:
Multiplions membre à membre
l'expression :
Multiplions à nouveau membre à
membre l'expression :
La simplification algébrique des équations
Booléennes n'est pas toujours évidente et demande de l'intuition. A l'inverse,
la méthode de Karnaugh permet de mettre en évidence les monômes adjacents à
l'aide d'un tableau sans difficulté.
Cette méthode fonctionne très bien
de 2 à 5 variables, elle devient complexe au-delà.
3. 4. 1. - TABLEAUX DE KARNAUGH
a) - Le tableau
Le tableau de Karnaugh est une forme
particulière de la table de vérité que nous avons utilisée jusqu'ici (table
de vérité figure 53) :
Une table de vérité comprend
autant de colonnes que de variables d'entrée. Elle comprend une ou plusieurs
autres colonnes, celles de la ou des variables de sortie. Toutes les
combinaisons de valeurs que peuvent prendre les variables d'entrée sont explorées
en comptant dans un ordre binaire. La valeur de la ou des variables de sortie
est indiquée en face de la combinaison correspondante.
Le tableau de Karnaugh comprend lui
2ncases, n
étant le nombre de
variables d'entrées de la fonction considérée.
b) - Cas de deux variables
Dans ce cas, le nombre de cases est
2n
= 22 = 4 (figure 54).
L'ordre des variables en abscisse ou
en ordonnée n'a pas d'importance, seul est très important le fait que lorsque
l'on passe d'une case à la case adjacente, une seule variable change.
Exemple:
Représentons la fonction f
= a .
b "fonction ET"
(figure 55).
Nous voyons facilement que l'on a
mis la valeur binaire que peut prendre la sortie à l'intérieur de la case pour
laquelle les variables ont la valeur portée en abscisse et en ordonnée.
f vaut 1 uniquement pour a
= 1 et b = 1
c) - Cas de trois variables
(figure 56).
Alors que pour deux variables, le
tableau était carré, il est maintenant rectangulaire ; en effet, nous
avons représenté les variables bc sur une même colonne.
On peut remarquer que l'ordre de la
quatrième et de la troisième ligne paraît inversé. En réalité, il n'en est
rien. On utilise seulement le code Gray
ou binaire réfléchi
afin de ne faire changer qu'une seule variable à la fois horizontalement ou verticalement.
d) - Cas de quatre variables
(figure 57)
On retrouve un carré qui comporte
24
cases soit :
24 = 16 cases
Nous voyons à nouveau, ce qui est
absolument indispensable, que grâce au code Gray, en passant d'une case à
l'autre horizontalement ou verticalement une seule variable change.
3. 4. 2. - SIMPLIFICATION GRAPHIQUE
a) - Il faut donc maintenant
utiliser le tableau de Karnaugh pour rechercher les monômes adjacents au lieu
de les rechercher algébriquement.
La table de Veitch (figure 58)
comporte en abscisse et en ordonnée les expressions algébriques représentées
pour chaque case. Par exemple : case ac.
La table de Karnaugh (figure 59)
donne, elle, pour chaque case les valeurs que prennent les variables en abscisse
et en ordonnée.
Dans les deux systèmes, on indique
à l'intérieur de chaque case la valeur 1 ou 0 prise par le monôme considéré.
On peut voir facilement que deux monômes
adjacents vont se trouver dans deux cases voisines puisque l'on a dit au départ
que les tableaux de Karnaugh étaient faits de telle sorte qu'on ne change
qu'une variable lorsqu'on change de case.
Il suffira donc pour chaque
combinaison de variables de noter 1 ou 0
dans la case correspondante, selon le résultat trouvé pour la valeur de la
fonction considérée, puis de regrouper les cases adjacentes dont le contenu
est à 1 par groupe de 2, 4 ou 8 ou de 2n termes adjacents.
Exemple (figure 60)
Les regroupements (ici de 2 termes)
sont figurés en rouge, on notera que les cases ab
et abc
sont bien les cases représentant des monômes adjacents. On peut comparer la
table représentée à la surface d'un tore si l'on essaie de rapprocher toutes
les cases des monômes adjacents l'une de l'autre ; ainsi, si les cases
des quatre coins du tableau étaient à 1, on pourrait constituer un groupement
de 4 cases avec elles.
b) - Exemple pour un tableau à 3 variables :
Soit l'expression :S = ac
+ c
+ aliant la variable S aux variables a, b, c.
Établissons la table de vérité
(figure 61)
Simplification par l'algèbre
Simplification par les tableaux de Karnaugh
Reportons les valeurs de
S dans le tableau de Karnaugh (figure 62) :
Réalisons les groupements a
et c.
Nous pouvons écrire :
S = a
+ c
c) - Exemple pour un tableau à quatre variables :
Soit l'expression :S
= abcd + abd + bc liant la variable
S
aux variables a, b, c, d.
Établissons la table de vérité
(figure 63) :
Simplification algébrique
S = abcd + abd + bc
Mettons abd
en facteur :
S = abd (c + 1) + bc
Utilisons l'identité remarquable
(x + 1) = 1 d'où (c + 1) = 1 d'où
l'on peut écrire :
S = abd + bc
Simplification par les tableaux
de Karnaugh
Reportons la valeur de
S
dans le tableau (figure 64).
Réalisons les groupements
abd et bc.
Nous pouvons écrire :
S = abd + bc
d) - Cas de 5 variables
A partir de cinq variables, le problème
se complique un peu. En effet, il n'est pas possible d'obtenir sur une surface
plane un tableau dans lequel une case soit adjacente à 5 autres cases. Il est
toutefois possible d'utiliser la méthode de Karnaugh en faisant deux tableaux (figure 65).
Nous voyons qu'en superposant les
deux tableaux (figure 66), on peut obtenir une case donnée X,
cinq cases adjacentes.
La figure 67 montre un cas ou l'on
pourrait effectuer trois groupements :
Groupement rouge : les quatre coins dans un même plan (tableau pour e = 0)
Groupement vert : deux cases dans le même plan pour e = 1
Groupement bleu : deux cases superposées.
NOTE :
Nous voyons dans cet exemple que le
groupement bleu semble être superflu. Il est nécessaire lorsque l'on utilise
une technologie électrique ou électronique pour des raisons de bon
fonctionnement qu'il y ait regroupement entre les groupements.
Cette condition n'est toutefois pas
obligatoire en pneumatique.
Un groupement ne
peut comprendre que 2n cases, c'est-à-dire 1, 2, 4, 8, 16, 32,... cases.
e) - Cas de 6 variables
On utilise le même principe avec
quatre tableaux pour six variables.
L'exemple de la figure 68 montre
trois groupements :
en vert sur quatre plans
en rouge sur deux plans
en bleu dans le même plan
La figure 69 montre dans l'espace un
exemple de cases adjacentes.
Au-delà de
6 variables, la méthode de Karnaugh n'étant plus valable, on
utilise la méthode dite de Mac Cluskey que nous décrirons ultérieurement afin
de ne pas apporter de confusion avec celle de Karnaugh.
Nous allons
continuer d'approfondir cette leçon par des applications pratiques des tableaux
de Karnaugh sur une autre page afin de ne pas encombrer celle-ci.
Méthode de KARNAUGH
Une fonction OUI : f1 = a 
fonction NON
ou
NAND (de l'anglais NO AND qui signifie NON ET).
ou
NOR (de l'anglais NO OR qui signifie NON OU).
b
... etc. Il est à noter qu'en algèbre de Boole
x .
x = x, il n'y a pas d'exposants tels que x2,
x4, cela n'existe pas.
Cliquez ici pour la leçon suivante ou dans le sommaire prévu à cet effet.
Haut de page
Page suivante