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

IV. Polynômes booléens, Fonctions booléennes

 

IV-1. Polynômes booléens

 

Définition 1 : Un monôme booléen est une constante ou une expression de la forme a₁a₂ a₃ … a_k où a_i représente soit la variable a_i soit le complément de la variable a_i. Un polynôme booléen est un monôme ou une somme finie de monômes.

 

Proposition 1 : (Règles de simplification des polynômes)
 xx’=0  et  xx=x              (simplification des monômes)
 x+xy=x                          (suppression ou adjonction de monômes dans un polynôme)
 xy+xy’=x                       (regroupement : cas particulier de la règle du consensus)
xy+y’z= xy+y’z+xz        (règle du consensus)

 

Définition 2 : Etant donnés deux monômes m₁ et m₂ on dit qu’ils admettent un consensus si toutes leurs lettres communes ont même forme (directe ou complémentée) sauf exactement une qui se présente sous forme contraire dans les deux monômes ; soit v cette variable. Le consensus de m₁ et m₂ est alors le produit de toutes les variables figurant dans m₁ ou m₂ sauf v, sous la forme où elles sont écrites dans ces monômes.

 

Proposition 2 : (Règle pratique)
Soient m₁ et m₂ deux monômes admettant un consensus co(m₁ , m₂) alors  m₁+m₂=m₁+m₂+co(m₁ , m₂)

IV-2. Expressions et fonctions booléennes

Définition 3 : On appelle expression booléenne à n variables v₁, v₂, …, v_n l’écriture d’un élément de l’algèbre de boole avec les symboles « v₁ », « v₂ », …, « v_n », les signes +, _* et ’ et un parenthésage adéquat.

 

Définition 4 : Soit B une algèbre de Boole et f une application de Bⁿ dans B
                                               f :        Bⁿ        →      B

                                                         (v₁, v₂, …, v_n) → f(v₁, v₂, …, v_n)
On dit que f est une fonction booléenne à n variables si « f(v₁, v₂, …, v_n) » est une expression booléenne.

 

Proposition 3 : Toute expression booléenne est égale à un polynôme booléen.

 

Définition 5 : Soit B une algèbre de Boole et f une application de Bⁿ dans B
On appelle duale de f et on note f* l’application de Bⁿ dans B définie par :
                                               f* :      Bⁿ       →      B

                                                         (v₁, v₂, …, v_n) → f*(v₁, v₂, …, v_n)=f’(v’₁, v’₂, …, v’_n)