Systèmes Logiques - Chapitre III: Algèbre de Boole et Fonctions Logiques

Systèmes logiques

CHAPITRE III

ALGEBRE DE BOOLE ET FONCTIONS LOGIQUES

Les circuits logiques constituent une partie très importante dans les systèmes électroniques.

On distingue deux sortes de circuits logiques :

▪ Circuits combinatoires dans lesquels l’état des signaux de sortie ne dépend que des

signaux d’entrée, les états antérieurs d’entrées n’ont aucun effet sur la sortie.

▪ Circuits séquentiels dans lesquels l’état de sortie dépend des signaux d’entrées et du

temps.

Ces circuits logiques sont caractérisés par des variables binaires, qui effectuent des

transitions entre deux états possibles. Ces deux états sont appelés niveau haut et niveau bas

ou niveau 1 et niveau 0.

La correspondance entre la variable binaire et le signal physique peut être établie de deux

manières :

▪ En logique dite positive, la variable logique 1 correspond à une tension supérieure à

celle du niveau 0. En général c’est cette logique qui est adoptée.

▪ En logique dite négative, la variable logique 1 correspond à une tension inférieure à

celle du niveau 0.

Pour étudier d’une manière systématique, ces variables binaires, on utilise une algèbre

différente de l’algèbre classique, dite algèbre de Boole.

I. Algèbre de Boole

L’algèbre de Boole est un ensemble de variables à deux états (0 et 1) dites aussi booléennes,

muni de trois opérateurs élémentaires :

▪ La multiplication logique ET ; son symbole est (.).

▪ L’addition logique OU ; son symbole est (+).

▪ L’inverse logique NON ; son symbole est (--).

1. Opérateurs de base de l’algèbre de Boole

Opérateur ET : si deux variables logiques A et B sont combinées par la multiplication logique

ET, le résultas s’exprime par : X = A.B

Cela se traduit par l’expression suivante : si A est vraie ET B est vraie alors X est vraie.

La liste complète des valeurs que peut prendre la fonction booléenne X en fonction de toutes

les combinaisons possibles des valeurs A et B peuvent être résumés dans un tableau appelé

table de vérité.

Systèmes logiques

A

0

0

1

1

B

0

1

0

1

X = A.B

0

0

0

1

Opérateur OU : l’addition logique de deux variables A et B donne : X = A+B

Cela se traduit par l’expression suivante : X est vrai si au moins A ou B est vrai.

La table de vérité de l’opérateur OU est la suivante :

A

0

0

1

1

B

0

1

0

1

X = A+B

0

1

1

1

Opérateur inverseur : c’est un opérateur à une seule variable. Le résultat X de l’opérateur

inverseur sur une variable booléenne A donne son complément :

La table de vérité de l’opérateur inverseur est la suivante :

A

0

1

1

0

2. Théorèmes de l’algèbre de Boole

Théorème de commutativité :

A + B = B + A

A.B = B.A

Théorème d’associativité :

A + (B + C) = (A + B) + C = A + B + C

A.(B.C) = (A.B).C = A.B.C

Théorème de distributivité :

A.(B + C) = A.B + A.C

A + (B.C) = (A + B).(A + C)

AX=AX=

Systèmes logiques

Théorème d’idempotence :

A +A = A

A.A = A

Théorème de complémentation :

Théorème des constantes :

A.1 = A

A+0 = A

A+1 = 1

A.0 = 0

Théorème d’absorption :

A+A.B=A

A.(A+B) = A.A + A.B = A + A.B = A(1+B) = A.1 = A

Théorème d’allégement :

Théorème de De Morgan :

A

0

0

1

1

B

0

1

0

1

1

0

0

0

1

0

0

0

1

1

1

0

1

1

1

0

Principe de dualité : chaque théorème vu précédemment se présente sous deux formes duales.

L’énoncé du théorème dual se déduit immédiatement en remplaçant (+) par (.) et (0) par (1)

et réciproquement.

3. Représentation d’une fonction logique

Une fonction logique est une combinaison de variables booléennes reliées par les opérations

ET, OU et NON. Elle peut être représentée par une écriture algébrique ou une table de vérité.

0.1==+AAAABABABAAABAA..0..).(=+=+=+BABABABA..=++=BA+BA.BA.BA+()BABAAABABABAABAA+=+++=++=+1.....

Systèmes logiques

Représentation algébrique : une fonction logique écrite sous forme algébrique peut être

représentée sous différentes formes : somme, produit, somme canonique ou produit

canonique.

▪

Forme somme : une fonction logique est écrite sous la forme de somme, si elle est

constituée de plusieurs termes reliés entre eux par l’opérateur OU (appelée aussi forme

disjonctive). Les fonctions logiques suivantes sont écrites sous forme de somme :

,

▪

Forme produit : une fonction logique est écrite sous la forme de produit, si elle est

constituée de plusieurs facteurs reliés entre eux par l’opérateur ET (appelée aussi forme

conjonctive). Les fonctions logiques suivantes sont écrites sous forme de somme :

,

.

D’après le théorème de De Morgan, nous pouvons affirmer que, si une expression est écrite

sous la forme somme, son inverse sera sous la forme produit et vice versa.

▪

Forme somme canonique : une fonction logique est écrite sous forme de somme

canonique si toutes les variables figurent dans chaque terme et si, dans chacun de ces termes,

toutes les variables sont reliées entre elles par l’opérateur ET. Ces termes se désignet sous le

nom de mintermes.

Exemples :

Soient les fonctions à trois variables A, B, C

Toutes ces fonctions sont écrites sous forme de somme canonique sauf la fonction Z, car son

premier terme n’est pas un minterme (puisque C n’apparaît pas dans ce terme).

▪

Forme produit canonique : une fonction logique est écrite sous forme de produit

canonique si toutes les variables figurent dans chaque produit et si, dans chacun de es

termes, elles sont toutes reliées entre elles par l’opérateur OU. Ces produits se désignent sous

le nom de maxtermes.

Si une expression X est écrite sous forme de somme canonique, d’après le théorème de De

Morgan, son inverse sera sous forme de produit canonique et vice-versa, comme le montre

l’exemple suivant :

Table de vérité d’une fonction logique : une expression logique X(A, B, C…), fonction des

variables A, B, C…, peut être représentée par une table de vérité. Cette table donne les

valeurs que peut prendre X, suivant les différentes combinaisons des variables A, B, C…

BAX+=CBAX.+=BAX.=)).(.(EDCBAX++=CBABAZCBACBACBAYCBACBAX.............+=++=+=()()()CBACBACBACBACBACBACBACBACBAXCBACBACBAX++++++==++=++=......................

Exemple : soit la table de vérité suivante à trois variables A, B et C.

Systèmes logiques

A

0

0

0

0

1

1

1

1

B

0

0

1

1

0

0

1

1

C

0

1

0

1

0

1

0

1

X

0

1

1

0

0

1

0

0

L’expression algébrique de la fonction X est donnée par la somme des mintermes des trois

variables A, B et C relatifs à chaque case de X = 1.

On note qu’une table de vérité donne l’expression de X sous forme de somme canonique.

4. Simplification des expressions logiques

La simplification d’une expression logique consiste à réduire cette expression à sa forme la

plus simple mais équivalente, c-à-d à un nombre minimal de termes et à un nombre minimal

de variable dans chaque terme. Pour cela, nous allons utilisé deux méthodes de

simplification : simplification algébrique et simplification graphique par le diagramme de

Karnaugh.

a. Simplification algébrique : en utilisant les théorèmes de l’algèbre de Boole.

Exemple 1 :

Exemple 2 :

Exemple 3 :

CBACBACBAX......++=()()()CBAXYXYXorXCBBACBABACBACCBACBACBACBAX+=+=++=+=++=++=...............()()()DBAADBDBDABDBAYDDBDDADAAorDDBDBBDABDDADBADAADDBABAY.1......0....................=++=++====+++++=+++=()BABABBAAABBABABAZ+=+=++=++=......

Systèmes logiques

b. Simplification par diagramme de Karnaugh :

▪ Construction du diagramme de Karnaugh : une expression logique ou une table de

vérité peut être représentée sous forme d’un diagramme de Karnaugh. Pour construire ce

diagramme, il faut suivre les règles suivantes :

• Le diagramme de Karnaugh d’une table de vérité ou d’une fonction logique à N

variables est constitué d’un rectangle divisé en 2N cases. Chaque case du diagramme

correspond à l’une des 2N combinaisons possibles des N variables.

• L’ordre des variables en abscisses et en ordonnée est choisi de telle sorte qu’entre

deux cases adjacentes, il n’y a qu’une seule variable qui change de valeur (on codifie le

tableau selon le code de Gray).

Exemple 1 : Chercher les diagrammes de Karnaugh relatifs aux tables de vérité suivantes :

Table de vérité à deux variables

A

0

0

1

1

B

0

1

0

1

X

1

0

0

1

Table de vérité à trois variables

C

0

0

0

0

1

1

1

1

B

0

0

1

1

0

0

1

1

A

0

1

0

1

0

1

0

1

X

1

0

0

0

1

0

1

0

1

0

B

A

0

1

1

1

0

1

0

0

0

0

C

Exemple 2 : Chercher les diagrammes de Karnaugh correspondant à la fonction logique à

quatre variables écrite sous forme de somme canonique suivante :

ABBA.BA.BA.BA.CDCBADCBADCBAX.........++=

Systèmes logiques

0

0

0

0

0

0

0

0

0

0

0

1

0

0

1

1

Exemple 3 : déterminer le diagramme de Karnaugh correspondant à la fonction logique à

trois variables, écrite sous forme de produit canonique suivante :

Comme cette fonction n’est pas écrite sous forme de somme canonique, son inverse

d’après le théorème de De Morgan :

le sera

1

0

1

1

1

0

1

0

C

Les cases à 0 du diagramme de Karnaugh correspondent aux mintermes de la fonction

,

alors que les cases à 1 correspondent à celles de la fonction

.

Exemple 4 : déterminer les diagrammes de Karnaugh relatifs aux fonctions suivantes :

Le diagramme de Karnaugh relatif à X1 est le suivant :

0

0

0

0

1

1

1

0

C

Le terme A.B de la fonction X1 lui correspond deux cases dans le diagramme de Karnaugh,

car si on écrit X1 sous forme de somme canonique, on aura la somme de trois mintermes

suivants :

Avant de déterminer le diagramme de Karnaugh de la fonction X2, il est préférable de mettre

l’expression de cette fonction sous forme de somme de produit de termes. Chaque produit

lui correspond une case ou un groupe de cases dans le diagramme de Karnaugh.

30

BA.BA.BA.BA.DC.DC.DC.DC.()()()CBACBACBAX++++++=..XCBACBACBAX......++=XXBACBAX...1+=()()CBABAX...2+=BA.BA.BA.BA.C()CBACBACBACCBACBABACBAX............1++=++=+=()()CBABACBABACBABAX........2+=++=+=BA.BA.BA.BA.C

Le diagramme de Karnaugh correspondant est alors le suivant :

Systèmes logiques

1

1

0

1

0

0

0

0

C

▪

Simplification par le diagramme de Karnaugh : la méthode de simplification par

diagramme de Karnaugh est la suivante :

• On transpose la table de vérité ou la fonction algébrique dans le diagramme de

Karnaugh.

• On effectue éventuellement des regroupements adjacents de 1, 2, 4, 8… cases de 1

appelées monômes. On cherche à avoir le minimum de regroupements ayant chacun le

maximum de cases possibles.

• Il faut noter que l’adjacence existe pour les extrémités du diagramme de Karnaugh,

car ce dernier se présente comme un cylindre horizontal ou vertical, dans lequel les cases du

haut sont adjacentes aux cases du bas et les cases de droites adjacentes aux cases de gauche.

• Dans un regroupement d’une case contenant 1, on ne peut éliminer aucune variable.

On écrit donc le produit des variables caractérisant cette case du diagramme.

• Dans un regroupement de deux cases contenant 1, on élimine la variable qui change

d’état et l’on conserve le produit des variables qui n’ont pas changé d’état dans le

regroupement, et cela en utilisant la relation

.

• Dans un regroupement de quatre cases contenant 1, on élimine les deux variables qui

changent d’état, et on ne conserve que le produit des variables qui n’ont pas changé d’état

dans le regroupement.

Cette règle se généralise en éliminant N variables dans un regroupement de 2N cases

adjacentes contenant la valeur 1.

• On cherche à faire apparaître dans le diagramme de Karnaugh le minimum de

regroupement de cases de 1, avec un maximum de cases possibles, en remarquant qu’un

même 1 peut faire partie de plusieurs groupes en tenant compte de la relation

.

• Tout regroupement totalement inclus dans un regroupement plus grand est éliminé

car son expression sera simplifiée. On dit qu’il n’est pas un impliquant premier.

• Traduire chaque regroupement de cases de 1 par son expression booléenne.

• L’expression logique simplifiée est la somme logique des expressions booléennes de

chaque regroupement.

Exemple 1 : cas de deux variables

A

0

1

1

0

B

X=

31

BA.BA.BA.BA.CAXAXA=+..AAA=+ABBABA..+

Systèmes logiques

A

1

1

1

0

0