Algbre de Boole

Algbre de Boole

Dfinition

Principe de dualit

Quelques thormes

Rgles sur les galits

Fonctions Boolennes

Numrotation des mintermes et des maxtermes

Proprits des mintermes et des maxtermes

Formes canoniques des fonctions boolennes

Preuves

Exercices

Dfinition :

Soit B un ensemble contenant au moins deux lments nots 0B et 1B muni de trois oprations :

- une opration binaire appele somme, note + - une opration binaire appele produit, note . - une opration unaire appele complmentaire, note

On note donc (B , + , . , ). Il sagit dune algbre de Boole si elle vrifie les 5 axiomes suivant :

1. Commutativit :

b + a = a + b b . a = a . b

2. Associativit :

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

3. 0B est llment neutre pour + 1B est llment neutre pour .

donc :

a + 0B = a a . 1B = a

4. Distributivit :

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

5. et enfin, le complmentaire dun lment a vrifie :

a + = 1B a . = 0B

Dbut de page

Principe de dualit :

Dans une algbre de Boole, tout resultat se prsente sous deux formes duales. Soit P un rsultat, son dual P* sobtient en permutant systmatiquement :

- les symboles + et . - les symboles 0 et 1.

Si un rsultat P est vrai dans une algbre de Boole, il en est de mme pour son dual.

Par exemple :

Soit P le rsultat suivant :

a B , a + a = a , qui est la rgle didempotence

son dual P* est donc :

a B , a . a = a

Dbut de page

Quelques thormes :

1. est lunique lment de B vrifiant a + = 1B et a . = 0B

2. Idempotence :

a + a = a et a . a = a

3. B = 1B et B = 0B

4. a + 1B = 1B et par dualit : a . 0B = 0B

5. = a

6. Absorption :

a + ( a . b ) = a a . ( a + b ) = a

7. Redondance :

ax + y = ax + y + xy

8. Lois de Morgan :

= . ( ) = +

Dbut de page

Preuves :

Nous allons vrifier que ces thormes dcoulent bien des axiomes de structure dune algbre de Boole.

1. Thorme 1: Daprs laxiome 5, pour tout a B, son complmentaire vrifie a + = 0. Il reste vrifier que est lunique lment de B vrifiant ces 2 relations. Supposons donc quil existe un autre lment a de B tel que:

a + a = 1 et a . a = 0

Comme a + a = 1, il vient : . ( a + a ) = . 1 Soit : . a + . a = ( axiomes 3 et 4 ) do : 0 + . a = ( axiome 5 ) et : . a = ( axiome 3 )

Dautre part de a + = 1 , il vient : ( a + ) . a = 1 . a Soit : a . a + . a = a ( axiomes 3 et 4 ) do : 0. . a = a et : . a = a ( axiome 3 )

On a donc : = . a = a , do lunicit de .

2. Thorme 2 : Montrons que a B a + a = a.

Soit: a = 0 + a

=( a . ) + a ( axiomes 3 et 5 ) = ( a + a ) . ( + a ) ( axiome 4 ) = ( a + a ) . 1 ( axiome 5 ) = a + a ( axiome 3 )

Do a = a + a et par dualit a = a . a

3. Thorme 3 : Daprs l axiome 3 , 0 + 1 = 1 et 0 . 1 = 0 Il dcoule alors du thorme 1 que 1 est le complmentaire unique de 0, soit: 1 =

4. Thorme 4 : Montrons que a B a + 1 = 1.

a + 1 = a + ( a + ) ( axiome 5 )

= ( a + a ) + ( axiome 2 ) = a + ( thorme 2 ) = 1

5. Thorme 5 : Montrons que a B = a. Soit a B, son complmentaire vrifie a + = 1 et a . = 0. Par commutativit de " + " et de " . ", il vient : + a = 1 et . a = 0 , a est donc bien le complmentaire de . Par ailleurs, admet pour complmentaire et en vertu de lunicit du complmentaire, on a :

= a

6. Thorme 6 : Montrons que a, x B a + a . x = a. a +a.x = a . 1 + a . x ( axiome 3 )

= a . ( 1 + x ) ( axiome 4 ) = a . 1 ( thorme 4 ) = a ( axiome 3 )

7. Thorme 7 : Montrons que a, x B :

a . x + . y = a . x + . y + x . y

a . x + . y = a . x + . y + a . x . y + . x . y ( thorme 6 )

= a . x + . y + x . y . ( a + ) ( axiome 4 ) = a . x + . y + x . y . 1 ( axiome 5 ) = a . x + . y + x . y ( axiome 3 )

8. Thorme 8 : Montrons que a, b B = . Dune part : ( . )(a + b)=

INCLUDEPICTURE "http://www.iut-info.univ-lille1.fr/projet2002/mathinfo/projet/dossier/images/bbarre.gif" \* MERGEFORMATINET a +

INCLUDEPICTURE "http://www.iut-info.univ-lille1.fr/projet2002/mathinfo/projet/dossier/images/bbarre.gif" \* MERGEFORMATINET b

=( a ) + ( b ) = 0 . + . 0 = 0 + 0 = 0

Dautre par:

INCLUDEPICTURE "http://www.iut-info.univ-lille1.fr/projet2002/mathinfo/projet/dossier/images/bbarre.gif" \* MERGEFORMATINET + a + b = + a + + b ( redondance sur a )

= (

INCLUDEPICTURE "http://www.iut-info.univ-lille1.fr/projet2002/mathinfo/projet/dossier/images/bbarre.gif" \* MERGEFORMATINET + a ) + 1 =1

Il sensuit que . est le complmentaire de a + b, soit:

= .

et par dualit :

= +

Dbut de page

Rgles sur les galits :

0. Soit a = b : alors a + c = b + c et ac = bc

Remarque : Il nexiste pas de rciproque ces rgles.

1. Soit a + c = b + c et ac = bc alors a = b

2. Soit a = b et c = d alors a + c = b + d et ac = bd

3. Si a = b, alors = 4. Si a . b = 1, alors a = 1 et b = 1

De mme, si a + b = 0, alors a = 0 et b = 0

Remarques :

a . b = 0 nquivaut pas a = 0 et b = 0. De mme, a + b = 1 nquivaut pas a = 1 ou b = 1.

Dbut de page

Fonctions Boolennes :

Dfinition :

Soit B une algbre de Boole, une fonction boolenne de n variables boolennes est une combinaison de ces variables au moyen des oprations + ; . ;

Exemple : f (a,b,c) = + bc + est une fonction boolenne.

Dfinition dun minterme :

Un minterme de n variables est un produit de ces n variables ou de leurs complmentaires.

Exemple : Soit 4 variables a, b, c et d, alors (abd) est un minterme. Contrairement ab qui nest pas un minterme puisquil ne contient pas les 4 variables.

Dfinition dun maxterme :

Un maxterme de n variables est une somme de ces n variables ou de leurs complmentaires.

Dbut de page

Quelques thormes:

5. Toute fonction boolenne n variables scrit de manire unique comme une somme de mintermes. Cest ce quon appelle la forme canonique disjonctive.

6. Toute fonction boolenne n variables scrit de manire unique comme un produit de maxtermes. Cest ce quon appelle la forme canonique conjonctive.

Dbut de page

Numrotation des mintermes et des maxtermes :

Soit 3 variables a, b et c :

mintermesmaxtermesnumrotation binairenumrotation dcimale

INCLUDEPICTURE "http://www.iut-info.univ-lille1.fr/projet2002/mathinfo/projet/dossier/images/bgrasbarre.gif" \* MERGEFORMATINET

INCLUDEPICTURE "http://www.iut-info.univ-lille1.fr/projet2002/mathinfo/projet/dossier/images/cgrasbarre.gif" \* MERGEFORMATINET + + 0 0 00

INCLUDEPICTURE "http://www.iut-info.univ-lille1.fr/projet2002/mathinfo/projet/dossier/images/bgrasbarre.gif" \* MERGEFORMATINET c+ + c0 0 11

b + b + 0 1 02

b c+ b + c0 1 13

a

INCLUDEPICTURE "http://www.iut-info.univ-lille1.fr/projet2002/mathinfo/projet/dossier/images/cgrasbarre.gif" \* MERGEFORMATINET a + + 1 0 04

a ca + + c1 0 15

a b a + b + 1 1 06

a b ca + b + c1 1 17

Dbut de page

Proprits des mintermes et des maxtermes :

Soit n variables boolennes a1, a2, ... , an :

7. 1 2 a3 ... an est un minterme Il existe 2n mintermes nots m0, m1, ... , m2n-1

a1 + 2 + a3 + ... + an est un maxterme Il existe 2n maxtermes nots M0, M1, ... , M2n-1

8. m0 + m1 + ... + m2n-1 = 1 La somme de tous les mintermes vaut 1.

De mme, le produit de tous les maxtermes vaut 0 : M0 . M1 . ... . M2n-1 = 0

9. Le produit de 2 mintermes distincts est nul.

Exemple pour n = 2 : m0 . m1 = m0 . m2 = m0 . m3 = m1 . m3 = m1 . m2 = m2 . m3 = 0

De mme la somme de 2 maxtermes distincts est gale 1.

10. Deux sommes de mintermes sont gales si et seulement si les mintermes qui ne sont pas communs aux 2 sommes sont nuls.

De mme 2 produits de maxtermes sont gaux si et seulement si les maxtermes qui ne sont pas communs aux 2 produits valent 1.

Exemple :

Pour i, j et k diffrents : Si mi . mj + mj . mj = mi . mj + mk . mj, alors mj . mj et mk . mj sont nuls, cest dire mj = 0 et mk = 0.

11. Toute fonction boolenne scrit de manire unique comme somme de mintermes tous distincts. La fonction 0 est la somme de 0 mintermes.

Exemple pour n = 3:

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

Or b c + b c = b c, on obtient donc : f(a,b,c) = b c + b

Il sagit de la forme canonique disjonctive.

De mme, toute fonction boolenne scrit de manire unique comme produit de maxtermes tous distincts. La fonction 1 est le produit de 0 maxtermes. Il sagit de la forme canonique conjonctive.

Dbut de page

Formes canoniques des fonctions boolennes :

Soit f une fonction boolenne crite sous sa forme canonique disjonctive, alors est la somme des mintermes qui napparaissent pas dans lexpression de f. En effet, est caractrise par f + = 1 et f . = 0

Exemple :

f(a,b,c) =

INCLUDEPICTURE "http://www.iut-info.univ-lille1.fr/projet2002/mathinfo/projet/dossier/images/bbarre.gif" \* MERGEFORMATINET

INCLUDEPICTURE "http://www.iut-info.univ-lille1.fr/projet2002/mathinfo/projet/dossier/images/cbarre.gif" \* MERGEFORMATINET + a

INCLUDEPICTURE "http://www.iut-info.univ-lille1.fr/projet2002/mathinfo/projet/dossier/images/cbarre.gif" \* MERGEFORMATINET + b +

INCLUDEPICTURE "http://www.iut-info.univ-lille1.fr/projet2002/mathinfo/projet/dossier/images/bbarre.gif" \* MERGEFORMATINET c + b c f(a,b,c) = a b c + a c + a b

De mme, le complmentaire dune fonction f est le produit des maxtermes qui napparaissent pas dans lexpression de f.