Algèbre 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 quot quot et de quot quot 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 ax 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 a b

a b 0 0 0 0 Dautre par a b a b redondance sur a a 1 1 Il sensuit que est le complmentaire de a b soit et par dualit Dbut de page Rgles sur les galits 1 Soit a b alors a c b c et ac bc Remarque Il nexiste pas de rciproque ces rgles 2 Soit a c b c et ac bc alors a b 3 Soit a b et c d alors a c b d et ac bd 4 Si a b alors 5 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 abc 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 ab d 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

6 Toute fonction boolenne n variables scrit de manire unique comme une somme de mintermes Cest ce quon appelle la forme canonique disjonctive 7 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 mintermes maxtermes numrotation binaire numrotation dcimale 0 0 0 0 c c 0 0 1 1 b b 0 1 0 2 b c b c 0 1 1 3 a a 1 0 0 4 a c a c 1 0 1 5 a b a b 1 1 0 6 a b c a b c 1 1 1 7 Dbut de page Proprits des mintermes et des maxtermes Soit n variables boolennes a1 a2 an 8 1 2 a3 an est un minterme Il existe 2n mintermes nots m0 m1 m2 n -1 a1 2 a3 an est un maxterme Il existe 2n maxtermes nots M0 M1 M2 n -1

9 m0 m1 m2 n -1 1 La somme de tous les mintermes vaut 1 De mme le produit de tous les maxtermes vaut 0 M0 M1 M2 n -1 0 10 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 11 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 12 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 fabc b fabc b c b c fabc b c b b c Or b c b c b c on obtient donc fabc 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 fabc a b c b c fabc 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