Plan du site  
français  English
pixel
pixel

Articles - Étudiants SUPINFO

Chapitre 04 - Axiomatique des algèbres de Boole. Fonctions booléennes

Le premier but de ce chapitre va être de définir une axiomatique dite de Boole englobant en particulier logique des propositions et opérations sur les ensembles. Nous étudierons ensuite les fonctions booléennes, c’est-à-dire les fonctions définies sur une telle algèbre de Boole.

Axiomatique des algèbres de Boole

Nous allons dans cette première partie étudier la notion d'algèbre de Boole puis énoncer les principaux théorèmes que l'on peut démontrer à partir des axiomes.

Contexte

Le lecteur attentif aux premiers chapitres de ce cours ne pourra qu’avoir remarqué des analogies entre logique des propositions et opérations sur les ensembles. Mettons les en évidence à l'aide d'un petit tableau récapitulatif :

Logique des propositions Opérations sur les ensembles
P A
Q B
F
V E
¬ C E
=

Dans les deux cas, après définition des opérateurs de base, on a pu démontrer des résultats plus sophistiqués comme par exemple des formules de De Morgan :

Logique des propositions Opérations sur les ensembles
¬ ( P Q ) ( ¬ P ) ( ¬ Q ) C E ( A B ) = C E ( A ) C E ( B )
¬ ( P Q ) ( ¬ P ) ( ¬ Q ) C E ( A B ) = C E ( A ) C E ( B )

Le lecteur ne peut que constater de très fortes similitudes entre ces formules, elles sont même formellement identiques.

La théorie des algèbres de Boole va permettre de formaliser ces analogies. On va englober ces deux exemples dans un cadre plus général.

Les résultats présentés dans les modules précédents n’apparaîtront plus alors que comme des cas particuliers.

[Note]

Cette démarche de généralisation est celle de tout scientifique.

Axiomes

La définition des algèbres de Boole requiert dix axiomes, cela explique sa longueur. Voyons cela en détail.

[Note]

Rappelons que des axiomes sont des propositions que l'on considère comme vraies et qui permettent d'élaborer une théorie. Par définition un axiome est donc indémontrable.

Ce concept doit être assez familier au lecteur, puisqu'il manipule des axiomes en géométrie, ceux dûs à Euclide, depuis ses années au collège.

Définition

On considère un ensemble E muni de :

  • Deux opérations binaires + et .

  • Une opération unaire notée a a

  • Deux éléments particuliers 0 et 1

On dira qu’un tel ensemble est une algèbre de Boole si pour tout triplet ( a , b , c ) d’éléments de E, les dix axiomes suivants sont vérifiés.

Commutativité :

  1. a + b = b + a

  2. a . b = b . a

Associativité :

  1. ( a + b ) + c = a + ( b + c )

  2. ( a . b ) . c = a . ( b . c )

Éléments neutres :

  1. a + 0 = a

  2. a . 1 = a

Complémentaire :

  1. a + a = 1

  2. a . a = 0

Distributivité :

  1. a . ( b + c ) = a . b + a . c

  2. a + ( b . c ) = ( a + b ) . ( a + c )

[Note]

0 et 1 ne sont que des notations et ne représentent pas les nombres réels bien connus.

De même + et . ne désignent pas l’addition et la multiplication réelle. Ceci dit, pour alléger notre discours nous utiliserons tout de même les termes addition et multiplication pour désigner ces deux opérations.

L'opération unaire sera elle appelée complémentaire.

Nous constatons ce que l'on appelle un principe de dualité. Les axiomes 2, 4, 6, 8 et 10 sont ainsi obtenus à partir des axiomes 1, 3, 5, 7, 9 en permutant d’une part + et . , et d’autre part 0 et 1.

Plus généralement, nous admettrons que dès qu’un résultat est démontré, son dual l’est également, dual au sens de ces permutations.

Exemples d’algèbres de Boole

Nous allons maintenant donner trois exemples concrets d'algèbres de Boole, deux d'entre eux étant bien connus du lecteur puisqu'ils ont fait l'objet des deux premiers chapitres de ce cours.

Algèbre de Boole des propositions

L’ensemble des propositions mathématiques muni des opérations de disjonction, de conjonction et de négation, ainsi que des éléments Faux et Vrai, est une algèbre de Boole.

Pour démontrer cela, il suffit de vérifier que les dix axiomes sont satisfaits.

On pose :

+
.
¬
0 F
1 V

Les dix axiomes s'écrivent alors :

a + b = b + a P Q = Q P
a . b = b . a P Q = Q P
( a + b ) + c = a + ( b + c ) ( P Q ) R = P ( Q R )
( a . b ) . c = a . ( b . c ) ( P Q ) R = P ( Q R )
a + 0 = a P Faux = P
a . 1 = a P Vrai = P
a + a = 1 P P ¯ = Vrai
a . a = 0 P P ¯ = Faux
a . ( b + c ) = a . b + a . c P ( Q R ) = ( P Q ) ( P R )
a + ( b . c ) = ( a + b ) . ( a + c ) P ( Q R ) = ( P Q ) ( P R )

Nous renvoyons le lecteur au premier chapitre du cours pour la vérification de ces axiomes.

Algèbre de Boole des parties d’un ensemble

L’ensemble des parties d’un ensemble non vide E muni des opérations de réunion, d’intersection et de complémentation, ainsi que des éléments et E est une algèbre de Boole.

Là aussi la démonstration de ce fait passe par la vérification des dix axiomes.

On pose :

+
.
C E
0
1 E

Dans ce contexte les dix axiomes s'écrivent :

a + b = b + a A B = B A
a . b = b . a A B = B A
( a + b ) + c = a + ( b + c ) ( A B ) C = A ( B C )
( a . b ) . c = a . ( b . c ) ( A B ) C = A ( B C )
a + 0 = a A = A
a . 1 = a A E = A
a + a = 1 A A ¯ = E
a . a = 0 A A ¯ =
a . ( b + c ) = a . b + a . c A ( B C ) = ( A B ) ( A C )
a + ( b . c ) = ( a + b ) . ( a + c ) A ( B C ) = ( A B ) ( A C )

La vérification de ces axiomes a été effectuée dans le second chapitre de ce cours.

Algèbre de Boole binaire

Considérons l'ensemble B = { 0 , 1 } .

Nous allons définir sur B une opération binaire appelée addition booléenne que l'on notera +.

Dans la mesure où B ne comporte que deux éléments, il suffit d'envisager toutes les valeurs possibles pour chacun des deux opérandes et de donner le résultat correspondant :

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

De la même façon, définissons sur B une opération binaire appelée multiplication booléenne notée . :

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

On définit également une opération unaire par :

a a
0 1
1 0

Muni de ces opérations, l'ensemble B est une algèbre de Boole dite binaire.

La vérification des axiomes est immédiate, elle est laissée au lecteur en exercice. Il suffit à chaque fois d'étudier tous les cas possibles.

[Note]

C'est bien sûr cette algèbre qui est la plus couramment utilisée en électronique et informatique. Nous consacrerons d'aileurs le dernier chapitre de ce cours à l'étude de ses spécificités.

Théorèmes fondamentaux

Nous allons présenter ici quelques résultats significatifs des algèbres de Boole.

Propriétés de l'application unaire

Soit E une algèbre de Boole et a un élément de E.

L'application unaire de l'algèbre est involutive, i.e. a = a .

De plus, 0 = 1 et 1 = 0 .

Idempotence

Soit E une algèbre de Boole et a un élément de E.

On a a + a = a et a . a = a .

Élément absorbant

Soit E une algèbre de Boole et a un élément de E.

On a a + 1 = 1 et a . 0 = 0 .

Absorption

Soit E une algèbre de Boole et a, b des éléments de E.

On a a + a . b = a et a . ( a + b ) = a .

Lois de De Morgan

Soit E une algèbre de Boole et a, b des éléments de E.

On a a + b = a . b et a . b = a + b .

[Note]

Les preuves de ces théorèmes seront effectuées lors de la séance d'exercices correspondant à ce chapitre.

Fonctions booléennes

Cette seconde partie sera consacrée à l'étude des fonctions définies sur une algèbre de Boole.

Définition

Commençons par définir la notion de fonction booléeenne.

Définition

Soit E une algèbre de Boole.

Une fonction booléenne f de n variables booléennes est une application de E n dans E qui à tout n-uplet d’éléments de E fait correspondre un élément de E construit à l’aide des opérations de l’algèbre.

[Note]

Par E n on désigne l'ensemble des n-uplet d’éléments de E.

De façon savante, un n-uplet d’éléments de E est un arrangement avec répétitions de n éléments de E.

Donnons de suite quelques exemples.

Example 1.1. Des fonctions booléennes

Une fonction booléenne à 3 variables :

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

Une fonction booléenne à 4 variables :

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

Mintermes et maxtermes

Dans cette sous-partie nous allons nous intéresser à des fonctions booléennes bien particulières, les mintermes et les maxtermes.

Mintermes

Définition

Un minterme de n variables booléennes est une fonction booléenne de n variables constituée d'un produit de n facteurs, chaque facteur correspondant à une variable donnée ou à son complémentaire.

Un exemple nous aidera à bien comprendre cette notion.

Example 1.2. Mintermes

Les fonctions f ( a , b , c , d ) = a . b . c . d et g ( a , b , c , d ) = a . b . c . d sont des mintermes de 4 variables.

La fonction h ( a , b , c , d ) = a . b . c n'est pas un minterme de 4 variables car elle ne comporte bien sûr que 3 variables.


Enonçons deux petits résultats concernant les mintermes.

Propriétés

Soit n un entier naturel non nul.

La somme de tous les mintermes de n variables vaut 1.

Le produit de deux mintermes différents de n variables est égal à 0.

Démonstration

La première assertion peut par exemple se démontrer par récurrence. Nous laissons le lecteur réfléchir à la question.

Pour la seconde, il suffit de remarquer que si deux mintermes sont différents il y aura au moins dans le produit des deux une vraiable et son complémentaire. Ce qui prouve le résultat d'après l'axiome 8.

Maxtermes

Définition

Un maxterme de n variables booléennes est une fonction booléenne de n variables constituée d'une somme de n termes, chaque terme correspondant à une variable donnée ou à son complémentaire.

Donnons de suite un exemple.

Example 1.3. Maxtermes

Les fonctions f ( a , b , c , d ) = a + b + c + d et g ( a , b , c , d ) = a + b + c + d sont des maxtermes de 4 variables.


[Note]

D'après les lois de De Morgan, le complémentaire d'un minterme est un maxterme et réciproquement. Par exemple, le complémentaire de a . b . c . d est a + b + c + d .

Les maxtermes vérifient les résultats suivants.

Propriétés

Soit n un entier naturel non nul.

Le produit de tous les maxtermes de n variables vaut 0.

La somme de deux maxtermes différents de n variables est égal à 1.

Démonstration

Ces deux résultats s'obtiennent à partir de ceux de la sous-partie précédente en appliquant le principe de dualité.

Numérotation des mintermes et maxtermes

On peut calculer très facilement le nombre de mintermes et de maxtermes possédant n variables.

Propriété

Soit n un entier naturel non nul.

Il y a 2 n mintermes et 2 n maxtermes de n variables booléennes.

Démonstration

Calculons le nombre de mintermes, le raisonnement sera le même pour le nombre de maxtermes.

Pour le premier facteur on a deux possibilités, soit il est égal à la première variable soit à son complémentaire.

De la même façon le deuxième facteur sera soit égal à la deuxième variable soit à son complémentaire.

Et ainsi de suite.

On a donc deux possibilités pour chacun des n facteurs. Le principe multiplicatif, voir troisième chapitre de ce cours, permet alors de conclure qu'il y a 2 n mintermes à n variables.

Puisque nous connaissons leur nombre, nous allons pouvoir maintenant numéroter les mintermes et les maxtermes.

Numérotation des mintermes et maxtermes

Soit n un entier naturel non nul.

A chaque minterme de n variables booléennes on associe un nombre binaire de n chiffres, avec pour 1 i n , le i-ième chiffre valant 1 si la i-ième variable est présente dans le minterme et 0 sinon. La conversion de ce nombre binaire en décimal donnera le numéro du minterme correspondant.

Il en est de même pour les maxtermes.

Présentons le cas des mintermes et maxtermes de 3 variables en exemple.

Example 1.4. Numérotation des mintermes et maxtermes de 3 variables

Le petit tableau suivant présente la numérotation des mintermes et maxtermes de 3 variables en suivant le principe exposé précédemment :

Mintermes Maxtermes Binaire associé Numéro
a . b . c a + b + c 000 0
a . b . c a + b + c 001 1
a . b . c a + b + c 010 2
a . b . c a + b + c 011 3
a . b . c a + b + c 100 4
a . b . c a + b + c 101 5
a . b . c a + b + c 110 6
a . b . c a + b + c 111 7

[Note]

Rappelons que pour convertir un nombre binaire a n a n - 1 ... a 1 a 0 , avec pour 0 i n , a i { 0 , 1 } , en nombre décimal il suffit de calculer i = 0 n a i 2 i .

Voir le cours d'architecture des ordinateurs 1CPA pour de nombreuses précisions à ce sujet.

On peut ensuite utiliser la numérotation précédente pour noter de façon plus synthétique les mintermes et maxtermes.

Notation des mintermes et maxtermes

Les 2 n mintermes de n variables seront notés m 0 , m 1 ,..., m 2 n - 1 .

Les 2 n maxtermes de n variables seront notés M 0 , M 1 ,..., M 2 n - 1 .

[Note]

Lorsque l’on fera référence à un minterme ou un maxterme avec ces notations, il faudra s'assurer que dans le contexte il n'y a pas de doutes sur le nombre de variables.

Formes canoniques

On va ici exprimer n'importe quelle fonction booléenne à l'aide uniquement de mintermes ou de maxtermes. On obtiendra alors des formes dites canoniques.

[Note]

Citons (pour une fois) partiellement le Wiktionnaire pour rappeler ce qu'est une forme canonique : forme [...] à laquelle se ramènent toutes les expressions d’un certain type, ce qui permet de les distinguer et de les classifier.

Forme canonique disjonctive

La première forme canonique concerne l'expression d'une fonction booléenne à l'aide de mintermes.

Théorème

Toute fonction booléenne f de n variables peut s’écrire de façon unique comme une somme de mintermes de ces n variables. Cette décomposition est appelée forme canonique disjonctive de f.

Nous admettrons ce résultat, sa démonstration étant un peu technique, en particulier l'unicité.

Voyons maintenant comment en pratique obtenir la forme canonique disjonctive d'une fonction f. On aura besoin de plusieurs étapes :

  1. Développer, si besoin est, l'expression de la fonction f.

  2. Multiplier les termes incomplets (i.e. ceux contenant moins de n variables) par la somme de chaque variable manquante et de son complémentaire. Par exemple, si un terme ne contient pas la variable c, le mutiplier par c + c .

  3. Développer à nouveau, cette fois-ci chacun des termes obtenus contiendra nécessairement les n variables.

  4. Supprimer les éventuelles redondance (deux fois le même terme) en utilisant la propriété d'idempotence a + a = a .

[Note]

L'étape 2 ne modifie pas la valeur de la fonction puisque l'on a toujours a + a = 1 d'après l'axiome 7.

Explicitons tout cela sur un exemple.

Example 1.5. Calcul d'une forme canonique disjonctive

On considère la fonction

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

Pas besoin de la développer, elle l'est déjà.

On constate qu'il manque la variable a dans le premier terme, on multiplie donc celui-ci par a + a . De même, il manque les variables a et c dans le troisième terme, il faut donc le multiplier par a + a et c + c .

On obtient

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

D'où en développant

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

On constate que le terme a . b . c est présent deux fois, on l'éliminer une fois d'après la propriété d'idempotence.

Finalement, on obtient notre forme canonique disjonctive

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

Que l'on peut écrire également en utilisant les notations de la sous-partie 2.2.3

f ( a , b , c ) = m 0 + m 2 + m 3 + m 4 + m 6 + m 7

Forme canonique conjonctive

Etudions à présent la seconde forme canonique, elle va nous permettre d'exprimer une fonction booléenne à l'aide de maxtermes.

Théorème

Toute fonction booléenne f de n variables peut s’écrire de façon unique comme un produit de maxtermes de ces n variables. Cette décomposition est appelée forme canonique conjonctive de f.

Là encore nous ne démontrerons pas ce résultat.

Concentrons nous sur la démarche à suivre pour obtenir concrètement la forme canonique conjonctive d'une fonction f. Il faudra suivre ces étapes :

  1. Calculer le complémentaire de f, i.e. f , en utilisant en particulier les lois de De Morgan.

  2. Calculer la forme canonique disjonctive de f .

  3. Prendre le complémentaire de la forme canonique disjonctive de f .

[Note]

Le complémentaire de f est bien égal à f puisque l'application unaire de l'agèbre est involutive (voir sous-partie 1.4).

De plus, le complémentaire de la forme canonique disjonctive de f sera bien la forme canonique conjonctive de f car le complémentaire d'un minterme est un maxterme (cf. sous-partie 2.2.2).

Voyons cela en pratique.

Example 1.6. Calcul d'une forme canonique conjonctive

Considérons à nouveau la fonction

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

Calculons tout d'abord son complémentaire. En utilisant les lois de De Morgan, on obtient

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

On doit ensuite calculer la forme canonique disjonctive de f , et donc appliquer la méthode présentée dans la sous-partie précédente.

Développons l'expression de f

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

D'après l'axiome 8, tous les termes contenant le produit b. b valent 0. On peut donc simplifier l'expression de f en

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

Il manque la variable a dans le second terme, il faut ainsi multiplier celui-ci par a + a . D'où

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

Développons de nouveau

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

On peut alors simplifier l'expression en utilisant la propriété d'idempotence. Nous obtenons donc comme forme canonique disjonctive de f

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

Il ne nous reste plus qu'à prendre de nouveau le complémentaire pour obtenir la forme canonique conjonctive de f

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

Que l'on peut écrire également en utilisant les notations de la sous-partie 2.2.3

f ( a , b , c ) = M 2 + M 6

[Note]

Nous admettrons que la somme du nombre de maxtermes dans la forme canonique conjonctive et du nombre de mintermes dans la forme canonique disjonctive d'une fonction booléenne de n variables est égale à 2 n . Cette remarque sert en pratique à vérifier la cohérence des résultats obtenus pour les formes canoniques.

Pour la fonction des exemples précédents, on avait ainsi 6 mintermes et 2 maxtermes, ce qui fait bien un total de 2 3 . Cela ne veut bien sûr pas dire que nos formes canoniques sont justes, mais au moins elles ne sont pas grossièrement fausses.

Numérotation des fonctions booléennes

Grâce aux formes canoniques, on va pouvoir aisément évaluer le nombre de fonctions booléennes de n variables.

Propriété

Soit n un entier naturel non nul.

Il y a 2 2 n fonctions booléennes de n variables.

Démonstration

Rappelons tout d'abord que la forme canonique disjonctive d'une fonction booléenne est unique. Dénombrer les fonctions booléennes ou les formes canoniques disjonctives conduit donc au même résultat.

Considérons une forme canonique disjonctive.

Le premier minterme m 0 y appartient ou non, ce qui fait deux possibilités.

Il en est de même pour m 1 et plus généralement pour tous les mintermes.

On a donc deux possibilités pour chacun des 2 n mintermes. Le principe multiplicatif, voir troisième chapitre de ce cours, permet alors de conclure qu'il y a 2 2 n formes canoniques disjonctives pour les fonctions booléennes de n variables. Q.E.D.

Numérotons à présent les fonctions booléennes en se servant de leurs formes canoniques disjonctives.

Numérotation des fonctions booléennes

Soit n un entier naturel non nul.

A chaque fonction de n variables booléennes on associe un nombre binaire de 2 n chiffres, avec pour 1 i 2 n , le i-ième chiffre valant 1 si le i-ième minterme est présent dans la forme canonique disjonctive de la fonction et 0 sinon. La conversion de ce nombre binaire en décimal donnera le numéro de la fonction correspondante.

Reprenons la fonction des exemples précédents et déterminons son numéro.

Example 1.7. Numéro d'une fonction booléenne

Nous avons vu dans la sous-partie 2.3.1 que la forme canonique disjonctive de la fonction

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

est

f ( a , b , c ) = m 0 + m 2 + m 3 + m 4 + m 6 + m 7

Le nombre binaire associé à cette fonction est donc 10111011. La conversion de ce binaire en décimal est 187.

La fonction f est donc la 187-ème fonction booléenne à 3 variables.


A propos de SUPINFO | Contacts & adresses | Enseigner à SUPINFO | Presse | Conditions d'utilisation & Copyright | Respect de la vie privée | Investir
Logo de la société Cisco, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société IBM, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sun-Oracle, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Apple, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sybase, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Novell, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Intel, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Accenture, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société SAP, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Prometric, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo du IT Academy Program par Microsoft, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management

SUPINFO International University
Ecole d'Informatique - IT School
École Supérieure d'Informatique de Paris, leader en France
La Grande Ecole de l'informatique, du numérique et du management
Fondée en 1965, reconnue par l'État. Titre Bac+5 certifié au niveau I.
SUPINFO International University is globally operated by EDUCINVEST Belgium - Avenue Louise, 534 - 1050 Brussels