Simplification des formulespageperso.lif.univ-mrs.fr/~arnaud.labourel/FI/cours6.pdfIConstante 1 = mon^ome sans facteur premier Arnaud Labourel, [email protected] Simpli

Formules polynomialesLa methode de Karnaugh

La methode des consensus

Simplification des formules

Arnaud LabourelCourriel : [email protected]

Universite de Provence

25 octobre 2011

Arnaud Labourel, [email protected] Simplification des formules



Limites de la forme canonique disjonctive

La forme canonique peut encore etre simplifiee

f (x1, x2, x3) = (x1x2x3) ∨ (x1x2x3) ∨ (x1x2x3) ∨ (x1x2x3)

devient f (x1, x2, x3) = x1

Consequence directe au niveau des dispositifs electriques

I Une formule represente une fonction, et le dispositif traduit laformule

I Plus un dispositif est simple, mieux il marche et moins il coute

I Le moins de litteraux et le moins d’operations possible

Formes polynomiales




Premiers pas

Fonctions simples ou non ?

I Fonctions booleennes representables par formules les plussimples = litteraux (a, x , y , etc.)

I Puis, monomes = fonctions representables par produits delitteraux (ab, xy , min-termes, etc.)

I Attention aux fonctiones nulles (xx) !

Theoreme a propos de la fonction nulle

Pour qu’un produit de litteraux donne la fonction nulle, il faut et ilsuffit qu’on y trouve a la fois un litteral et son complementaire.

Autre resultatPuisque xn = x si x ∈ B, la repetition d’un meme litteral dans unproduit est inutile




Une serie de resultats essentiels

Theoreme (preuve par l’absurde)

Modulo l’ordre des facteurs, il existe une et une seule facon dedefinir un monome par un produit de litteraux d’exposant 1.

xxz ≡ xxz ≡ xz z ≡ zx

Consequence

I Les litteraux multiplies ensembles pour faire un monomes’appellent les facteurs premiers du monome.

I Constante 1 = monome sans facteur premier




Une serie de resultats essentiels (cont’d)

TheoremeParmi les fonctions booleennes de n variables, il y a 3n monomes(3 choix par variable : elle-meme, son complementaire, ou sonabsence).

Exemple

Avec les 3 variables a, b, c , il y a 27 monomes :

1 c c b bc bc b bc bca ac ac ab abc abc ab abc abca ac ac ab abc abc ab abc abc




Une serie de resultats essentiels (cont’d)

Definition

I Un monome m divise le monome M si tout facteur premier dem est aussi un facteur premier de M

I (m est un diviseur de M, M est un multiple de m)

I Exemple : x1x3 divise x1x2x3

Theoremem divise M ⇔ M � m dans Fn (m 1 quand M le fait).

I Quand M prend la valeur 1 pour ω, tous ses f.p. sont a 1. Donc si mdivise M alors m prend la valeur 1 aussi.

I (absurde) Supposons M � m et x un f.p. de m qui n’apparaıt pas dansM. On pose p = Mx , non nulle : il existe un mot ω pour lequelp(ω) = 1. Puisque p(ω) = M(ω)x(ω), on a M(ω) = x(ω) = 1, doncx(ω) = 0 donc m(ω) = 0 : contradiction.




Formule polynomiale

DefinitionOn appelle formule polynomiale d’une fonction booleenne f touteformule permettant d’exprimer f comme somme booleenne demonomes :

f = m1 ∨m2 ∨ · · · ∨mp

Remarques

I Quand m divise M, on a M � m donc M ∨m = m

I Une forme polynomiale est dite reduite s’il n’existe pas i et j ,i 6= j , tels que mi divise mj

I Pour obtenir la forme reduite d’une formule, on supprime toutmonome pour lequel il existe un diviseur dans la formule.

I La FCD est sous forme polynomiale reduite




Exemples

I abc divise abcdef

I abc∨ abc ∨abc∨ ac

I abc ∨ abc ∨ ac




Simplicite de formule

Definition

I Soient f = m1 ∨m2 ∨ · · · ∨mp et f = M1 ∨M2 ∨ · · · ∨Mq

FPR d’une meme fonction booleenne f .I La premiere est plus simple que la seconde si :

1. p ≤ q2. Chaque mi divise au moins un Mj

TheoremePour une fonction booleenne donnee, la relationest-plus-simple-que est une relation d’ordre sur l’ensemble deses formules polynomiales reduites.




Exemple de simplicite

f = abc ∨ abc ∨ abc ∨ abc

(p1) f = abc ∨ abc ∨ abc ∨ abc (p5) f = abc ∨ ac ∨ bc(p2) f = abc ∨ ac ∨ abc (p6) f = ab ∨ ac ∨ abc(p3) f = abc ∨ abc ∨ bc (p7) f = ab ∨ abc ∨ bc(p4) f = ab ∨ abc ∨ abc (p8) f = ab ∨ ac ∨ bc

I p1 p2 car abc ∨ abc = ac

I p5 � p2 car bc divise abc




Forme reduite minimale

DefinitionUne formule polynomiale reduite est minimale, si c’est un elementminimal dans le treillis des formes polynomiales reduites ordonneespar est-plus-simple-que.

Remarques

I Il s’agit des formules les plus simples possibles

I Il existe des methodes pour trouver les minimales dans le casde fonctions a trois ou 4 variables.




Formes CD et PM de F2

Forme canonique disjonctive Formule polynomiale minimale

f0 = 0 f0 = 0f1 = xy f1 = xyf2 = xy f2 = xyf3 = xy ∨ xy f3 = xf4 = xy f4 = xyf5 = xy ∨ xy f5 = yf6 = xy ∨ xy f6 = xy ∨ xyf7 = xy ∨ xy ∨ xy f7 = x ∨ yf8 = x y f8 = x yf9 = x y ∨ xy f9 = x y ∨ xyf10 = x y ∨ xy f10 = yf11 = x y ∨ xy ∨ xy f11 = x ∨ yf12 = x y ∨ xy f12 = xf13 = x y ∨ xy ∨ xy f13 = x ∨ yf14 = x y ∨ xy ∨ xy f14 = x ∨ yf15 = x y ∨ xy ∨ xy ∨ xy f15 = 1




Introduction

Objectif

Trouver les formules polynomiales minimales des fonctions de 3 ou4 variables (adaptable pour 5 et 6, mais difficilement).

Principe

I Facon particuliere de ranger les mots binaires : disposes dansun plan.

I Principe : les mots qui se ressemblent sont proches dans leplan.

I Reconnaissance facilite des monomes qui minorent unefonction donnee + resolution d’un probleme de couverture.




Rangement des mots en tableaux (B3)

Le principe

I Disposition dans laquelle deux mots binaires adjacents nedifferent que d’un bit.

I Presque possible sur B4




Le cas de B4

L’objectif est presque atteint

Imaginer le tableau comme un cylindre (vertical et horizontal...)




Le cas de B4






Le cas de B4






Representation d’une fonction f

Principe

I Noircir les cases des mots ou f vaut 1

I Ensemble des cases noircies = diagramme de Karnaugh de f

Exemple avec f ∈ F3

B3 f0 0 0 00 0 1 00 1 0 10 1 1 11 0 0 01 0 1 11 1 0 11 1 1 0




Proprietes du diagramme de Karnaugh : Theoreme

1. Le diagramme de Karnaugh de la fonction constante 0 estvide, et celui de la fonction constante 1 est plein.

2. f � g ⇔ D.K. de f inclus dans celui de g .

3. Le D.K. de fg est l’intersection de ceux de f et g .

4. Le D.K. de f ∨ g est la reunion de ceux de f et g .

5. Le D.K. de f est le negatif de celui de f .

6. Les min-termes sont les fonctions booleennes dont le D.K. estreduit a une seule case.




Forme canonique disjonctive facile a retrouver

Union de diagrammes de Karnaugh

est l’union de

f = abc ∨ abc ∨ abc ∨ abc




Propriete importante

DefinitionUn rectangle d’un D.K. est une zone composee de plusieurs casescontrolee par au moins un litteral (ou sous-zone).

Theoreme

I Le diagramme de Karnaugh d’un monome de Fn, qui possedep facteurs premiers, est un rectangle forme de 2n−p cases

I Reciproquement, tout rectangle forme de 2n−p cases est leD.K. d’un monome qui est le produit de p litteraux.




Les 27 monomes de F3




Quelques monomes de F4

a, d , ac, bd , abd , bcd




Methode pour trouver la formule d’un monome

Cas de F4 : monome d’une cellule

I La cellule est-elle couverte par les colonnes des litteraux a, a,b et b ?

I La cellule est-elle couverte par les lignes des litteraux c , c , det d ?

I Facteurs premiers du monome : litteraux repondant OUI.




Exemple detaille ad




Methode de simplification

Remarque

I On appelle cellule les D.K. des monomes (rectangles dont lenombre de cases est une puissance de 2)

I Plus une formule est simple, plus grand est son diagramme deKarnaugh

Pour simplifier une formule f

1. On dessine son diagramme de Karnaugh

2. On cherche un ensemble de cellules aussi grosses et peunombreuses que possible

3. La reunion de ces cellules doit etre egale au diagramme deKarnaugh de f




Simplification de formules sur F4 : exemple

1. Le diagramme de Karnaugh initial

2. Grosses cellules qui couvrent le D.K. de f

Grosses cellules non contenues dans une plus grosse




Simplification de formules sur F4 : exemple (cont’d)

3. Amorcer le recouvrementCases contenues dans une seule cellule : noircir la cellule















4 et 5. Terminer le recouvrement (a repeter)

Choix de la grosse cellule qui contient le plus de cases non noircies





4 et 5. Terminer le recouvrement (a repeter)

Choix de la grosse cellule qui contient le plus de cases non noircies





6. Lire la formuleSomme booleenne des formules des cellules selectionnees :

f = abc ∨ abd ∨ ac




Pas toujours si simple

Plusieurs choix a l’etape 5

I On fait tous les choix pour aller vers plusieurs solutions

I A l’etape 6., on choisit la formule qui comporte le moinsd’operations (si elle existe)

Reperer les plus grandes cellules

I Plus difficile s’il faut passer par les bords

I Une solution = pavage du plan




Pavage du plan pour reperer les cellules









cellules abd et abc




Recherche des implicants premiersEcriture de la formule finale de la fonction

Premisses

Avantages

Methode systematique, valable pour tout nombre de variables

Theoreme (rappel : f ∨m = f ⇔ m � f )

I Si f = m1 ∨m2 ∨ · · · ∨mp est une formule polynomiale de f :∀i ,mi � f .

I Reciproquement, quand m � f , il existe une formulepolynomiale f = m1∨ · · ·∨mp dans laquelle m est l’un des mi .





Les implicants

Definition d’un implicant

I Tout monome m inferieur ou egal a une fonction booleenne fest un implicant de f (m � f ).

I Dans la methode de karnaugh : monomes dont la cellule estentierement contenue dans le D.K. de f

Les implicants premiers

I Un monome m est un implicant premier de f s’il n’existe pasd’autre implicant M de f tel que m � M � f .

I Elements maximaux de l’ensemble des implicants

I Monomes des grosses cellules dans le diagramme de Karnaugh.





Exemple d’implicants et d’implicants premiers





Exemple d’implicants et d’implicants premiers





Resultat essentiel

TheoremeLa somme booleenne de tous les implicants premiers de f est uneformule polynomiale reduite de f .

Elements de preuve

Soit une formule polynomiale f = m1 ∨ · · · ∨mp de f .Implicants premiers = maximaux des impliquants, alors m1 � M,M implicant premier, donc :f =M ∨ f

=M ∨ (m1 ∨ · · · ∨mp) = (M ∨m1) ∨m2 ∨ · · · ∨mp

=M ∨m2 ∨ · · · ∨mp

Dans une FP, on peut toujours remplacer un monome par unimplicant premier qui le majore.





Sur l’exemple

f11 = f1 ∨ f2 ∨ f8 (min-termes)

Remplacer f1 par f3, et f2 par f10 et f8 par f10 : f11 = f3 ∨ f10





Principe de la methode des consensus

Les etapes

1. Depart : formule polynomiale qcq (ex. FCD)

2. Remplacement de chaque monome par un implicant premierqui le majore

3. Elimination de ceux qui apparaissent plusieurs fois

4. Remplacement eventuel (et repete) de f par f ∨M ou M estun implicant premier n’apparaissant pas (encore) dans laformule.

On obtient une forme reduite.

TheoremeChaque monome d’une formule polynomiale minimale est unimplicant premier.






On a vu...Les formules polynomiales minimales sont a chercher parmi lessommes booleennes d’implicants premiers.

Les deux etapes de la methode

1. Rechercher tous les implicants premiers de f

2. Parmi les ensembles d’implicants premiers dont f est la sommebooleenne, rechercher celui dont le cardinal est le plus petit.





Monome consensus

Definition

I Soit une variable booleenne x

I Soient deux monomes xm1 et xm2 (m1 et m2 sans facteur xni x)

I m1m2 est le consensus de xm1 et de xm2

I Si m1 = ym′1 et m2 = ym′2 alors le consensus de xm1 et xm2

est nul.

Consequences : soient deux monomes qcq

I Ou le consensus est impossible a faire

I Ou leur consensus est nul

I Ou leur consensus n’est pas nul





Monome consensus (cont’d)

Exemples

I ad et bc n’ont pas de consensus

I abc et bcd ont un consensus nul

I abc et bd ont pour consensus acd





Monome consensus (cont’d)

TheoremeLe consensus de deux monomes est inferieur ou egal a leur sommebooleenne.Puisque x ∨ x = 1 nous avons m1m2 = m1m2(x ∨ x) = m1m2x ∨m1m2x ; et

puisque m1m2x � m1x et m1m2x � m2x , on a finalement m1m2 � m1x ∨m2x .

Consequence

Le consensus de deux implicants est un implicant (monomeinferieur a la fonction).





Methode pour trouver les implicants premiers

f = acd ∨ ade ∨ bce ∨ d e ∨ bcde

1. Determiner une formule polynomiale reduite qcq de f et ecrirela liste de ses monomes : ensemble L d’implicants.

2. En prenant tour a tour chacune des variables a :2.1 Partage de L en trois parties :

2.1.1 A : les monomes ou a est en facteur2.1.2 B : les monomes ou a est en facteur2.1.3 C : les autres monomes

2.2 Si A ou B vide, on passe a la variable suivante. Sinon, calculdes consensus obtenus en prenant un monome de A, un de B :ajout dans L

2.3 A chaque ajout d’un consensus dans L, tentative de reductionde L en eliminant monomes divisibles par d’autres de la liste.

3. L est la liste des implicants premiers de f





Exemple : f = acd ∨ ade ∨ bce ∨ d e ∨ bcde

Variable a : acd ade bce d e bcdecde

Variable b : bcde bce acd ade d e cdecde

Variable c : cde bce acd cde ade d eVariable d : cde acd cde ade d e bce

acecde cde acd ade d e bce ace

ceVariable e : ce d e ade acd

cdade d e ce cd

ad

L = {ad , d e, ce, cd}





Plusieurs sommes booleennes possibles

Un probleme de couverture

Choisir le moins possible d’implicants premiers pour que chaquemin-terme de la fonction soit majore par au moins un desimplicants choisis.

Exemple : implicants premiers et min-termes

C1 = acd C2 = abd C3 = bcd C4 = abcm1 = abcd m2 = abcd m3 = abcd m4 = abcd m5 = abcd





Sur l’exemple

Le probleme de couverture

Tableau qui montre la couverture des min-termes par les implicantspremiersC1 = acd C2 = abd C3 = bcd C4 = abcm1 = abcd m2 = abcd m3 = abcd m4 = abcd m5 = abcd

Valeur 0 aux variables indeterminees(moins possible d’IP)

f = C1 ∨ C2 ∨ C4 = acd ∨ abd ∨ abc

f = C1 ∨ C3 ∨ C4 = acd ∨ bcd ∨ abc


Documents

Simplification des formulespageperso.lif.univ-mrs.fr/~arnaud.labourel/FI/cours6.pdfIConstante 1 = mon^ome sans facteur premier Arnaud Labourel, [email protected] Simpli