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

VI. Simplification

VI-1. Généralités

Dans toute la suite f est une fonction booléenne de n variables.

 

Définition 1 : On appelle support de f et on note supp(f) l’ensemble des points de Bⁿ où f n’est pas nulle.
On représente souvent le support d’une fonction par un diagramme (dit de Veitch ou de Karnaugh). Le diagramme de Karnaugh est un tableau qui traduit le produit des variables par des intersections de lignes et de colonnes et leurs sommes par des réunions de « cellules ». On dit que c’est une représentation graphique de f.

 

Proposition 1 : Soit f et g deux fonctions booléennes de n variables. Alors
 supp(f+g) = supp(f)  supp(g)
 supp(fg) = supp(f) ∩ supp(g)
 supp(f) = supp(g)  f=g

 

Définition 2 : On dit qu’une expression E₁ est inférieure où égale à une expression E₂ si et seulement si E₁+E₂=E₂ On note E₁≤E₂
On dit qu’un monôme m est un monôme premier de f si m≤f et si aucun sous-multiple stricte m₁ de m n’est tel que m₁≤f.
On dit qu’un ensemble M de monômes couvre f si . On dit aussi que M est une couverture de f.

 

Remarque 1 : On peut chercher graphiquement une couverture de f en cherchant un ensemble de monômes inférieurs ou égaux à f et tels que l’union de leurs représentations soit égale à la représentation de f.

 

Définition 3 : On dit qu’une expression polynomiale E₁ est plus simple qu’une autre E₂ si le nombre de signe + et * qui y figurent (et qui est égal au nombre de lettres écrites diminué de 1) est plus petit que le nombre de ceux qui figurent dans E₂.

 

Proposition 2 : Soit f une fonction booléenne et E une expression polynomiale de f. Soit m un monôme figurant dans E ; si m n’est pas premier, il existe une forme polynomiale de f plus simple que E.

 

VI-2. Recherche des formes polynomiales plus simples

 : Les méthodes algébriques
 : Les diagrammes de Veitch et de Karnaugh
 : La méthode de Quine et Mc Cluskey
 : Les méthodes de Harvard
 : La méthode du consensus

 

Méthode du consensus : transforme une expression E comme somme de tous ses monômes premiers.
 : Etape 1 : écrire l’expression sous forme polynomiale E=m₁+m₂+…+m_p
 : Etape 2 : supprimer (loi d’absorption) tout monôme m_i supérieur ou égal à un autre monôme figurant dans le polynôme
 : Etape 3 : additionner le consensus co(m_i, m_j) de tout m_i et m_j à condition que co(m_i, m_j) se soit supérieur ou égal à aucun des deux monômes m_i et m_j.