Précédent / Suivant / Table des matières

V. Formes canoniques

 

Dans toute la suite on considère une algèbre de boole binaire. Les variables intervenant dans toute expression booléenne sont des variables binaires (élément de B={0,1}). Cette restriction volontaire aux algèbres de boole binaires se justifie par les applications envisagées (arithmétique appliquée, informatique etc.) Mais la plupart des résultats démontrés restent vrais dans le cas des algèbres de boole quelconques.

 

Définition 1 : On appelle monôme canonique construit sur n variables booléennes x₁ x₂ … x_n un monôme où toutes les n variables figurent (sous forme directe ou complémentée). 

 

Proposition 1 : Avec n variables booléennes on peut former 2ⁿ monômes canoniques. La somme de ces 2ⁿ monômes canoniques est égale à 1.

 

Conséquence 1 : Dans une algèbre de boole binaire un monôme canonique vaut 1 pour une seule combinaison des valeurs des variables. Pour toutes les autres combinaisons il vaut 0.

 

Proposition 2 : Tout monôme où figurent p variables parmi n variables  (n≥p) est la somme de 2^n-p monômes canoniques.

 

Conséquence 2 : Dans une algèbre de boole binaire si un monôme m vaut 1 pour une combinaison des valeurs de ses variables alors ce monôme est la somme de tous les monômes canoniques qui valent 1 pour des combinaisons de valeurs des variables où la combinaison initiale des valeurs des variables formant m est conservée.

 

Définition 2 : On appelle polynôme canonique sur n variables booléennes x₁, x₂, … , x_n un polynôme dont tous les monômes sont des monômes canoniques de ces n variables.

 

Proposition 3 : Toute expression booléenne (et par conséquent tout polynôme et toute fonction booléenne) est égale à un polynôme canonique unique sur les variables qui y figurent. Ce polynôme s’appelle forme canonique.

 

Proposition 4 : La forme canonique d’un produit de deux polynômes canoniques est égale à la somme de leurs monômes communs (intersection).
La forme canonique d’une somme de deux polynômes canoniques est égale à la somme de leurs monômes (union).
La forme canonique d’un complément d’une expression canonique est égale à la somme des monômes canoniques qui n’y figurent pas.

 

Conséquence 3 : Dans une algèbre de boole binaire une fonction booléenne vaut 1 si et seulement si un de ses monômes canoniques vaut 1 ; la forme canonique d’une fonction booléenne détermine immédiatement la table de ses valeurs et réciproquement.

 

Remarque 1 : Toute application de Bⁿ dans B est une fonction booléenne.

 

Proposition 5 : Il y a  fonctions booléennes distinctes de n variables.