Plan du site  
français  English
pixel
pixel

Articles - Étudiants SUPINFO

Chapter 05 - Study of binary Boolean functions

Ce dernier chapitre sera consacré à l'étude des fonctions définies sur l'algèbre de Boole binaire. Pour cela, on utilisera principalement deux outils, les tables de vérité et les diagrammes de Karnaugh.

Tables de vérité

Après avoir exposé le principe de fonctionnement des tables de vérité, nous verrons comment les utiliser pour déterminer les formes canoniques des fonctions booléennes définies sur l'agèbre binaire.

Présentation

Rappelons pour bien fixer les idées la définition de l'algèbre de Boole binaire.

Il s'agit de l'ensemble B = { 0 , 1 } muni des trois opérations suivantes.

Addition booléenne :

a b a + b
0 0 0
0 1 1
1 0 1
1 1 1

Multiplication booléenne :

a b a . b
0 0 0
0 1 0
1 0 0
1 1 1

Complémentaire :

a a
0 1
1 0

Nous nous intéressons donc aux fonctions booléennes définies sur cette algèbre binaire. Nous les nommerons d'ailleurs fonctions booléennes binaires.

Chaque variable d'une telle fonction ne pouvant prendre que deux valeurs, 0 ou 1, on va pouvoir décrire de manière exhaustive les valeurs des fonctions booléennes. Pour cela, on va récapituler tous les cas possibles dans un tableau appelé table de vérité.

La table de vérité d’une fonction à n variables se présentera ainsi sous la forme d’un tableau à n + 1 colonnes :

  • n colonnes dédiées au valeurs de chacune des variables.

  • La dernière colonne dédiée au résultat de la fonction.

Chaque ligne du tableau présentera une combinaison différente de valeurs pour les variables de la fonction. Il y a deux valeurs possibles, 0 ou 1, pour la première variable, deux valeurs pour la seconde, et de même deux valeurs pour chacune des variables. Ce qui fait 2 × 2 × . . . × 2 = 2 n possibilités et donc lignes dans la table de vérité.

[Note]

Il s’agit en fait du nombre d’arrangements avec répétitions de n éléments de l’ensemble { 0 , 1 } .

Sur chaque ligne figurera ainsi un nombre binaire de n chiffres. Par convention, le nombre décimal correspondant devra être 0 sur la première ligne, 1 sur la seconde,..., 2 n - 1 sur la dernière. Ainsi toutes les tables de vérités auront la même disposition de lignes.

Exemples de fonctions à deux variables

Nous allons dans cette sous-partie donner quelques exemples de fonctions booléennes à deux variables parmi les 16 existantes.

[Note]

On a en effet vu au chapitre précédent que le nombre de fonctions booléennes à n variable est égal à 2 2 n .

On se limitera aux plus importantes dans notre contexte, c'est-à-dire celles les plus utilisées en électronique et informatique.

Fonction AND

Il s'agit tout simplement de l'opération . de l'algèbre :

a b a . b
0 0 0
0 1 0
1 0 0
1 1 1

Fonction OR

Cette fonction correspond à l'opération + de l'agèbre :

a b a + b
0 0 0
0 1 1
1 0 1
1 1 1

Fonction universelle

Il s'agit de la fonction constante égale à 1 :

a b 1
0 0 1
0 1 1
1 0 1
1 1 1

Fonction NAND

Cette fonction notée est définie comme le complémentaire de la fonction AND.

D'après une loi de De Morgan, elle s'exprime comme

a b = a . b = a + b

La table de vérité de cette fonction s'obtient soit à partir de son expression algébrique soit à partir de la table de vérité de la fonction AND :

a b a b
0 0 1
0 1 1
1 0 1
1 1 0
[Note]

Le nom de cette fonction est bien sûr un raccourci de not AND.

Fonction NOR

Cette fonction notée est définie comme le complémentaire de la fonction OR.

D'après une loi de De Morgan, elle s'exprime comme

a b = a + b = a . b

La table de vérité de cette fonction s'obtient soit à partir de son expression algébrique soit à partir de la table de vérité de la fonction OR :

a b a b
0 0 1
0 1 0
1 0 0
1 1 0
[Note]

Le nom de cette fonction est bien sûr un raccourci de not OR.

Fonction XOR

Cette fonction notée est aussi appelée ou exclusif.

Son expression algébrique est

a b = a . b + a . b

Il est facile de voir que sa table de vérité est :

a b a b
0 0 0
0 1 1
1 0 1
1 1 0
[Note]

Cette fonction ne vaut donc 1 que si l'une seule des deux variables est égale à 1. C'est ce qui la différentie de la fonction OR qui elle vaut 1 également quand les deux variables sont égales à 1.

Fonction XNOR

Cette fonction notée est aussi appelée équivalence.

Son expression algébrique est

a b = a . b + a . b

Il est facile de voir que sa table de vérité est :

a b a b
0 0 1
0 1 0
1 0 0
1 1 1
[Note]

Cette fonction ne vaut donc 1 que si les deux variables sont égales. D'où son nom.

A la vue des tables de vérité on constate que la fonction XNOR est la complémentaire de la fonction XOR.

Exemples de fonctions à trois variables

Nous n'allons donner que deux exemples des 256 fonctions booléennes à trois variables existantes.

Fonction majorité

Cette fonction est définie comme suit

f ( a , b , c ) = a . b + b . c + a . c

En voici sa table de vérité :

a b c f ( a , b , c )
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

Pour obtenir cette table, il faut prendre un à un les termes de la fonction et se demander à quelles conditions ils sont égaux à 1.

Par exemple le terme a . b ne vaudra 1 que si à la fois a et b valent 1, peu importe la valeur de c, i.e. pour ( a , b , c ) = ( 1 , 1 , 1 ) et ( a , b , c ) = ( 1 , 1 , 0 ) . Puisque la fonction f s'écrit comme une disjonction elle vaudra également 1 pour ces valeurs des variables (d'après la propriété d'élément absorbant énoncée au chapitre précédent).

On procède ensuite de même pour les deux autres termes de la fonction.

Le lecteur hésitant pourra dans sa table rajouter des colonnes intermédiaires correspondantes aux termes de la fonction. Il s'assurera ainsi un risque d'erreur quasi-nul.

a b c a . b b . c a . c f ( a , b , c )
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 1 0 0 0 0 0
0 1 1 0 1 0 1
1 0 0 0 0 0 0
1 0 1 0 0 1 1
1 1 0 1 0 0 1
1 1 1 1 1 1 1
[Note]

Cette fonction s'appelle majorité car elle ne vaut 1 que quand une majorité de ses variables vaut 1.

Fonction parité

Il s'agit de la fonction

f ( a , b , c ) = a . b . c + a . b . c + a . b . c + a . b . c

Elle a pour table de vérité :

a b c f ( a , b , c )
0 0 0 1
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0
[Note]

Cette fonction porte le nom de parité car elle ne vaut 1 que quand un nombre pair de ses variables vaut 1.

Formes canoniques

Dans cette sous-partie, nous allons présenter une méthode permettant de déterminer les formes canoniques d'une fonction booléenne binaire à partir de sa table de vérité.

Commençons par remarquer que la table de vérité d'un minterme ne contient qu'un seul 1. En effet, pour qu'un minterme soit égal à 1 il faut nécessairement que tous les facteurs de son produit soient égaux à 1. Ce qui n'est le cas que pour une seule combinaison des variables.

[Note]

Si l'un des facteurs du minterme est égal à 0, d'après la définition de la multiplication booléenne le maxterme sera égal lui aussi à 0.

Par exemple, le minterme de trois variables a . b . c vaut 1 uniquement pour a = 1 , b = 1 , c = 1 , i.e. a = 0 , b = 1 , c = 0 . Ce qui donne cette table de vérité :

a b c a . b . c
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 0

De la même façon, un maxterme ne vaudra 0 que si tous les termes de sa somme sont égaux à 0. La table de vérité d'un maxterme ne contient donc qu'un seul 0.

[Note]

Si l'un des termes du maxterme est égal à 1, d'après la définition de l'addition booléenne le minterme sera égal lui aussi à 1.

Par exemple, le maxterme de trois variables a + b + c vaut 0 uniquement pour a = 0 , b = 0 , c = 0 , i.e. a = 1 , b = 0 , c = 1 . Ce qui donne cette table de vérité :

a b c a + b + c
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 1

Nous allons maintenant nous servir des constatations précédentes sur les mintermes et maxtermes pour déterminer les formes canoniques d'une fonction booléenne binaire.

Pour calculer la forme canonique disjonctive d'une fonction f, il faut repérer les lignes de la table de vérité où la valeur de f est 1, associer à chacune d'elles le minterme correspondant et en faire la somme.

Pour obtenir la forme canonique conjonctive d'une fonction f, il faut cette fois repérer les lignes de la table de vérité où la valeur de f est 0, associer à chacune d'elles le maxterme correspondant et en faire le produit.

Voyons cela sur un exemple.

Example 1.1. Obtention des formes canoniques à partir d'une table de vérité

Considérons la fonction

f ( a , b , c ) = a + a . c + b . c

Nous laissons le lecteur vérifier que la table de vérité de cette fonction est :

a b c f ( a , b , c )
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1

Pour déterminer la forme canonique disjonctive de f, il faut donc prendre les mintermes correspondants aux lignes de la table de vérité pour lesquelles la valeur de f est 1. On obtient

f ( a , b , c ) = a . b . c + a . b . c + a . b . c + a . b . c + a . b . c + a . b . c

Pour obtenir la forme canonique conjonctive de f, il faut considérer les lignes de la table de vérité où f vaut 0, et prendre les maxtermes correspondants. Il vient

f ( a , b , c ) = ( a + b + c ) . ( a + b + c )

Diagrammes de Karnaugh

Nous allons dans cette partie définir une autre représentation des fonctions booléennes binaires, les diagrammes de Karnaugh, et s'en servir pour simplifier l'expression des fonctions.

Principe

Dans certains domaines, en particulier en informatique et en électronique, il est très utile de simplifier au maximum l'écriture des fonctions booléennes binaires. En effet, elles modélisent des circuits électroniques et les simplifier revient à réduire le nombre de composants nécessaires à leurs implémentations.

[Note]

Ce sujet sera étudié dans le cours d'architecture des ordinateurs 1CPA, lors de la construction des mémoires.

Par simplifier, on entend écrire la fonction avec le moins de termes possibles, et avec des termes les plus petits possibles.

Le lecteur aura sans doute remarqué que les formes canoniques ne donnent pas l'expression la plus simple d'une fonction. Il va donc falloir procéder autrement que par leurs calculs.

Une première possibilité consiste à utiliser les axiomes et les formules de calcul (idempotence, absorption, etc.) des algèbres de Boole. Cependant, à partir de quatre variables procéder ainsi devient inextricable.

On préfèrera donc utiliser une méthode visuelle basée sur l’utilisation de diagrammes. Ceux-ci portent le nom de leur inventeur, l'américain Maurice Karnaugh (1924-).

Un diagramme de Karnaugh est un moyen simple et efficace pour représenter une fonction booléenne binaire. Il s’agit en fait de la réécriture sous une forme différente de la table de vérité.

Disposition des diagrammes

Le diagramme de Karnaugh d'une fonction booléenne binaire de n variables est un tableau à double entrée dont le nombre de cases intérieures est égal à 2 n .

Chaque case du tableau correspond à une ligne de la table de vérité, et l'on passe d'une case à une case voisine en ne changeant la valeur que d'une seule variable.

A l'intersection d'une ligne et d'une colonne, on indique la valeur de vérité de la fonction que l'on étudie.

Voyons la disposition générale des diagrammes de Karnaugh pour des fonctions possédant de 2 à 5 variables.

Figure 1.1. Allure d'un diagramme de Karnaugh à 2 variables

Allure d'un diagramme de Karnaugh à 2 variables

Figure 1.2. Allure d'un diagramme de Karnaugh à 3 variables

Allure d'un diagramme de Karnaugh à 3 variables

Figure 1.3. Allure d'un diagramme de Karnaugh à 4 variables

Allure d'un diagramme de Karnaugh à 4 variables

Figure 1.4. Allure d'un diagramme de Karnaugh à 5 variables

Allure d'un diagramme de Karnaugh à 5 variables

Simplification d’expressions

Les diagrammes de Karnaugh vont donc nous permettre de donner l’expression la plus simple d’une fonction booléenne binaire.

Pour cela, on va effectuer des regroupements avec tous les 1 présents sur le diagramme.

On va donc constituer des blocs de 1 qui devront vérifier les contraintes suivantes :

  • les cases constituant un bloc doivent être adjacentes.

  • les blocs doivent être de forme rectangulaire.

  • le nombre de cases d'un bloc doit être une puissance de 2.

  • les blocs devront contenir le plus de cases possibles (tout en respectant bien sûr les contraintes ci-dessus).

  • les blocs peuvent se chevaucher.

[Note]

Puisque l'on cherche à faire des blocs les plus grands possibles, on sera parfois amené à utiliser des 1 dans plusieurs blocs. D'où cette possibilité de chevauchement.

[Note]

Il faut bien avoir en tête que la première colonne est adjacente avec la dernière, et que de même la première ligne est adjacente avec la dernière.

Par exemple, ces quatres cases sont en fait adjacentes :

Un diagramme de karnaugh se "referme" donc dans ses deux dimensions. On peut ainsi le qualifier de torique.

Chaque bloc correspondra à une expression de la forme simplifiée de la fonction que l'on cherche à établir. Pour déterminer concrètement cette expression, on regarde quelles sont les variables dont la valeur est fixe pour toutes les cases du bloc. Ce sont elles qui figureront dans l'expression.

In fine, la fonction s'écrira comme la disjonction de chacune de ces expressions.

Voyons cela sur des exemples.

Example 1.2. Simplification d'une fonction de 3 variables

Reprenons la fonction

f ( a , b , c ) = a + a . c + b . c

On a vu (cf. exemple à la fin de la première partie) que la table de vérité de f est :

a b c f ( a , b , c )
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1

Son diagramme de Karnaugh sera donc :

Comme dit précédemment, la table de vérité de f et son diagramme de Karnaugh possèdent bien les mêmes informations, mais sous une forme différente.

Dans ce diagramme on peut manifestement réaliser deux blocs de quatre 1, et l'on ne pourra pas faire mieux :

Regardons la valeur des variables pour les cases du bloc bleu : on a a = 1 et les valeurs de b et c n'importent pas. Ce bloc correspondra donc à l'expression a.

De même pour les cases du bloc rouge on a nécessairement c = 1 , les valeurs de a et b n'important pas. Il vaut donc c.

L'expression simplifiée de f est ainsi

f ( a , b , c ) = a + c

Etudions un second exemple avec cette fois une fonction de 4 variables.

Example 1.3. Simplification d'une fonction de 4 variables

Considérons la fonction de 4 variables dont le diagramme de Karnaugh est le suivant :

Deux blocs de quatre 1 apparaissent naturellement, l'un sur la troisième colonne et l'autre sur la quatrième ligne.

Mais on peut également faire un bloc avec les quatre 1 restants qui sont en fait adjacents. Comme remarqué précédemment, il faut bien imaginer que le diagramme se "referme".

Nous avons donc ces blocs :

Regardons la valeur des variables pour les cases du bloc bleu : on a c = 1 , d = 1 et les valeurs de a et b n'importent pas. Ce bloc correspondra donc à l'expression c.d.

De même pour les cases du bloc rouge on a nécessairement a = 1 et b = 0 , les valeurs de c et d n'important pas. Il vaut donc a. b .

Enfin, pour les cases du bloc vert on a b = 1 et d = 0 , les valeurs de a et c n'important pas. Il vaut donc b. d .

L'expression simplifiée de f est ainsi

f ( a , b , c , d ) = c . d + a . b + b . d

Terminons cette partie, ce chapitre et ce cours par une remarque : il n’y a pas unicité de la forme la plus simplifiée d’une fonction booléenne binaire.

En effet, selon les regroupements que l’on effectuera, on pourra obtenir des formes aussi simples mais d’expressions différentes.

Illustrons ce fait par un exemple.

Example 1.4. Non unicité de la forme simplifiée d'une fonction

Considérons la fonction de 4 variables dont le diagramme de Karnaugh est le suivant :

On peut effectuer les regroupements suivants :

On obtient alors (que le lecteur s'en persuade) cette expression simplifiée :

f ( a , b , c , d ) = c . d + c . d + a . b . c

Cependant, nous aurions pu également effectuer de façon tout aussi optimale ces regroupements :

Ceux-ci conduisent à l'expression simplifiée suivante :

f ( a , b , c , d ) = c . d + c . d + a . b . d

Les deux expressions obtenues sont différentes mais aussi simples l'une que l'autre.


About SUPINFO | Contacts & addresses | Teachers | Press | INVESTOR | Conditions of Use & Copyright | Respect of Privacy
Logo de la société Cisco Logo de la société IBM Logo de la société Sun-Oracle Logo de la société Apple Logo de la société Sybase Logo de la société Novell Logo de la société Intel Logo de la société Accenture Logo de la société SAP Logo de la société Prometric Logo du IT Academy Program par Microsoft

SUPINFO International University is globally operated by EDUCINVEST Belgium - Avenue Louise, 534 - 1050 Brussels
and is accredited in France by Association Ecole Supérieure d'Informatique de Paris (ESI SUPINFO)