cours 2 Boole.key

Sicard

Informations

• Publié par: Kanic
• Nombre de lectures: 67
• Langue: Catalan

Extrait

Algèbre de Boole et fonctions Définition d’un Algèbre de Boole
booléennes • Soit un ensemble A possédant 2 éléments particuliers notés 0 et 1
• A muni des opérations . (produit), + (somme) et • Introduction
(complémentation) est une algèbre de Boole si!et seulement si il
• Boole!: mathématicien anglais du 19ème siècle qui s’intéresse aux
respecte les axiomes suivants!:
propositions logiques
- A1!: . et + commutatives et associatives
• Proposition Vraie/Fausse
• a.b= b.a, a+b= b+a, a.(b.c)= (a.b).c, a+(b+c)= (a+b)+c
• Et, Ou, complément
- A2!: 0 est l’élément neutre pour +, 1 est l’élément neutre pour .
•Ordinateur!: manipule des 0 et 1 (2 tensions électrique 0v et 5v)
• 0+a= a, 1.a= a
• 0 : faux
- A3!: . est distributive par rapport à + et inversement
• 1: vrai
• a.(b+c)= a.b+a.c , a+(b.c)= (a+b).(a+c)
• L’étude des fonctions booléennes permet de construire des - A4!: pour tout a élément de A!: a+ a= 1 et a. a = 0
circuits électroniques
Boole Boole© P. Sicard-Cours ALM 2 © P. Sicard-Cours ALM 21 2
Un algèbre de Boole Notations
• Il existe de nombreux algèbres de Boole
• Le . est prioritaire sur le +. Le complément est prioritaire sur le +
• L’exemple le plus simple d’algèbre de Boole est celui pour lequel et le .
A= {0, 1}. On notera B= {0,1}
• On omet souvent les .
• D’après les axiomes nous avons:
• Exemple!: "
- 1.0= 0, 1.1= 1, 0.0= 0 - ab+c= a.b+c= (a.b)+c
- 1+0=1, 1+1=1, 0+0=0 - ab = (ab)
- 1= 0, 0= 1
• Propositions logiques!:
- produit: et
- somme: ou

- 1: vrai; 0: faux
Boole Boole© P. Sicard-Cours ALM 2 © P. Sicard-Cours ALM 23 4Règles de simplification
Propriétés et Théorèmes
• a= a duale: a= a
• Dualité!:
• a+1= 1 duale: a.0= 0- Si (A, 0, 1, +, ., -) est un algèbre de Boole alors
(A, 1, 0, ., +,- ) est aussi un algèbre de Boole • a+a= a duale: a.a= a
- Tous les axiomes (ou propriétés) sont toujours vrais si on
• a + a.b = a duale: a.(a+b)= a
remplace les + par des . et inversement , et les 0 par des
1 et inversement • a.b+ a.b = b duale: (a+b).(a+b) = b
- Exemple: a.1= a ; dualité: a+ 0= a
• a.b + a = b + a duale: (a+b). a = b. a
• Règles de De Morgan!:
• a.b + a.c + b.c = a.b + a.c
- (a+b)= a . b

- (a.b)’ = a + b • A démontrer à partir des axiomes
Boole Boole© P. Sicard-Cours ALM 2 © P. Sicard-Cours ALM 25 6
Fonctions booléennes Représentation des fonctions
booléennes•Définition!:
-On appelle fonction booléenne à n variables une application de • Table de vérité
nB dans B!: - Tableau: valeurs de la fonction pour chaque combinaison des
n valeurs des n variables- f!: " B -> B
n- 2 lignes- (x1,x 2, …, xn) -> f(x1, x2, …, xn)
• Expressions algébriques
•Exemple! à 2 variables!: - à partir des noms des variables et des opérateurs de l’algèbre de
Boolex ,x f(x ,x )1 2 " 1 2
• Exemple!: f(x ,x )= x .x + x (x + x )1 2 1 2 1. 1 20 0 " 0
- Une fonction!: une infinité d’expressions algébriques0 1 " 0
- Simplification des fonctions grâce aux règles de l’algèbre1 0 " 0
• Exemple!: f = ab + a b c + c + b= ab + a b + c + b= 1+ c = 11 1 " 1
Boole Boole© P. Sicard-Cours ALM 2 © P. Sicard-Cours ALM 27 8Expression algébrique Vocabulaire
à partir de la table de vérité
• Monôme!: produit de variables sous forme normale ou
complémentée •Théorème de Shannon!:
-Exemple: x x x x1. 2. 3. 4 f(x ,x , …,x )= x . f(x ,x , …, 0, …, x ) + x . f(x ,x , …,1, …, x )1 2 n i 1 2 n i 1 2 n
• Monal!: somme de variables sous forme normale ou complémentée
•Exemple avec n=2!:
-Exemple: x x x x1+ 2+ 3+ 4
- f(x ,x )= x . f(0,x ) + x . f(1,x )1 2 1 2 1 2•Forme polynomiale!: somme de monômes
- f(x ,x )= x . (x f(0,0)+ x f(0,1) )+ x . (x f(1,0)+ x f(1,1) )1 2 1 2 . 2 . 1 2 . 2 . •Monômes canoniques!: toutes les variables de la fonction
- f(x ,x )= x x f(0,0)+ x x f(0,1) + x x f(1,0)+ x x f(1,1)1 2 1 . 2 . 1. 2 . 1. 2 . 1. 2 . apparaissent (complémentée ou non)
•Forme normal conjonctive: somme de monômes canoniques • Passage évident de la table de vérité à une expression
algébrique sous forme de somme de produits (forme normale)•Forme normal disjonctive: somme de monaux canoniques
Boole Boole© P. Sicard-Cours ALM 2 © P. Sicard-Cours ALM 29 10
MéthodeExemple sur une table de vérité
• On regarde les lignes où la fonctions vaut 1• x , x f(x , x )1 2 " 1 2
• On écrit les monômes avec la variable sous forme normal si elle • 0 0 " f(0,0)= 1
vaut 1 , complémentée si elle vaut 0
• 0 1 " f(0,1)= 0
• Possibilité d’obtenir la forme normale disjonctive (par dualité)
• 1 0 " f(1,0)= 1
- On regarde les lignes où la fonction vaut 0 et on écrit un produit de somme
canonique en prenant la variable sous forme normale si elle vaut 0 et • 1 1 " f(1,1)= 1
complémentée si elle vaut 1
• Exemple
x , x f(x , x )1 2 " 1 2• f(x ,x )= x x f(0,0)+ x x f(0,1) + x x f(1,0)+ x x f(1,1)1 2 1 . 2 . 1. 2 . 1. 2 . 1. 2 .
0 0 "f(0,0)= 1• f(x ,x )= x x 1 + x x 0 + x x 1+ x x 11 2 1 . 2 . 1. 2 . 1. 2 . 1. 2 .
0 1 "f(0,1)= 0 f(x , x )= (x + x ).(x + x )1 2 1 2 1 2
• f(x1,x2)= x1 .x2 + x1.x2 + x1.x2 = x1 .x2 + x1.x2 + x1.x2 + x1.x2
1 0 "f(1,0)= 1 = x x + x .x 1. 2 1 2
• f(x ,x )= x + x 1 2 2 1
1 1 "f(1,1)= 0
Boole Boole© P. Sicard-Cours ALM 2 © P. Sicard-Cours ALM 211 12Simplification Quelques fonctions particulières
• Fonctions à 1 variable!(4):
- f(x)= x‘!: complément• Pour concevoir un circuit , on peut partir d’une expression algébrique
- f(x)= x
• Forme simplifiée permet d’obtenir le circuit le plus petit ou le plus - f(x) = 1 tautologie (toujours vrai)
rapide! - f(x) = 1 (toujours faux)
• Fonctions à 2 variables!(16):• Formes et critères de simplification des expressions algébriques
- f(x,y) =x.y!: Et and dépendent de la technologie utilisée, on comprendra plus tard
- f(x,y) =x+y!: Ou or
• Exemple: Forme polynomiale
- f(x,y) = x y+ x y!: Ou exclusif, noté !
- f(x,y) = x y+ x y!: noté !– Critère de simplification:
- f(x,y) = (x.y)!: non-et , nand
»Minimum de monômes et (en deuxième lieu) minimum de - f(x,y) = (x+y)!: non-ou , nor
variables par monômes - Même nom à n variables
• 2 puissance (2 puissance n) fonctions à n variables! Architecture et principes 01© P. Sicard-Cours Réseaux 1 13
Boole© P. Sicard-Cours ALM 2 14
Principe de la minimisation d’une Tableau de Karnaugh
•Outil “manuel” de simplification des fonctions booléennes forme polynomiale
•Définitions!: •Principe
-Relation d’ordre!sur les expressions algébriques booléennes : f#g ssi f.g = f- Table de vérité sous forme de tableau
-Exemple!: abc < ab car abc ab= abc faire le tableau de karnaughn- Principe du regroupement de 2 cases adjacentes
•Un point d’une fonction: un monôme canonique: une case à 1 du
- Exemple f(a,b,c)
tableau de Karnaugh(a b + a b) c = b c
ab
c 00 01 11 10 •On parle de recouvrement de points de la fonction
1 0 0 10 n-k•Un monôme à k variables (parmi n) couvre 2 points
0 1 1 11
•Monôme premier!d’une fonction!f!:
- m # f et il n’existe pas monôme m’ tel que m’# f et m’# m
(a b + a b) c = a c
k - Monôme premier; Plus gros regroupement de 2 points sur le tableau de
- Attention à l’ordre des colonnes et des lignes
Karnaugh
Boole Boole© P. Sicard-Cours ALM 2 © P. Sicard-Cours ALM 215 16Minimisation
Algorithme de minimisation
•Base d’une fonction
• Trouver la base complète-Somme de mônomes premiers tel que tous les points de f sont
couverts par au moins un de ces monômes • Garder les monômes essentiels (seul à couvrir au moins un
point)
•Base complète!: Tous les monômes premiers de la fonction
• Eliminer les monômes inutiles (tous les points qu’il couvre sont
couverts par des essentiels•Base irrédondante d’une fonction!:
-Si on enlève un de ses monômes ce n’est plus une base de f • Essayer tous les cas pour couvrir les points non couverts par les
-Il peut y avoir plusieurs bases irrédondantes essentiels
• Heuristique!: prendre d’abord ceux qui couvrent le plus de •But!de la minimisation:
-Critère!: nombre minimal de monômes et de variables par monômes points non encore couverts
-Trouver une base irrédondante possédant le moins possible de monôme
-Problème NP complet!: il faut trouver toutes les bases irrédondantes pour trouver la (ou
les) minimales
Boole Boole© P. Sicard-Cours ALM 2 © P. Sicard-Cours ALM 217 18
Exemple sur tableau de Karnaugh
Fonctions phi-bo