cours-2-boole

Publié par

Algèbre de BooleEric CariouUniversité de Pau et des Pays de l'AdourDépartement InformatiqueEric.Cariou@univ-pau.fr1Algèbre de Boole Système algébrique constitué de l'ensemble { 0, 1 } Variable booléenne : variable qui prend une valeur 0 ou 1 Trois opérateurs de base NON / NOT ( )a Inverse/complémente la valeur de la variable a ET / AND ( a.b ou ab ) Retourne 1 si a et b sont à 1, sinon retourne 0 OU / OR ( a +  b ) Retourne 1 si a ou b est à 1, sinon retourne 0 Origine Mathématicien anglais Georges Boole, 1815 – 1864 2Propriétés de base a=aInvolution : Idempotence : aa=a a.a=a Complémentarité : a.a=0 aa=1 a=a.1=1.a=aÉléments neutres :a0=0a=a Absorbants : a1=1 a.0=03Propriétés de base Associativité : a.b.c=a.b.cabc=abc a.bc=a.ba.cDistributivité :ab.c=ab.ac ab=a.bRègles de De Morgan : a.b=abaab=ab Optimisations :abc=abac4Fonction logique Fonction logique  Prend en entrée une ou plusieurs variables booléennes  Retourne une valeur booléenne fonction des variables d'entrée Définition d'une fonction logique : deux méthodes Par son expression logique Combinaison des variables de la fonction via les opérateurs de base de l'algébre de boole Exemple : fonction f de trois variables a, b et cfa,b,c=abbcac Par sa table de vérité Table qui définit la valeur de la fonction pour chaque combinaison 5de valeurs possibles en entréeTables de vérité Table de ...
Publié le : samedi 24 septembre 2011
Lecture(s) : 34
Nombre de pages : 29
Voir plus Voir moins
 Algèbre de Boole
Eric Cariou
Université de Pau et des Pays de l'Adour Département Informatique
Eric.Cariou@univ-pau.fr
1
lgèbre d2AtsyS emèoB eelo cuestongéaliqbresbm'lned  etiéuVari1 } 0, le {: enneéloob elbapri que bliaar v uo rT1 siorépod ene unleva 0urateurs de baseneMrigiO1518, le4 86 1 –
OU / OR (a + b)
Retourne 1 siaetbsont à 1, sinon retourne 0
ET / AND (a.bouab)
NON / NOT (a )
Inverse/complémente la valeur de la variablea
Retourne 1 siaoubest à 1, sinon retourne 0
matiathé angcienG oealsiB oogrse
Propriétés de base
Involution
Idempotence
Complémentarité
Éléments neutres
Absorbants
:
:
:
:
:
a=a
aa=
a a a
a . a=0
a . a 0
=
a.a a
aa=1
a a 1
a=a .1=1. a=a a0=0a=a
a1=1
a 1 1
a.
=
a.0 0
3
Propriétés de base
Associativité
Distributivité
Règles de De Morgan
Optimisations
:
a.b. c=a.b.cabc=abc
:a.bc=a.ba.c ab.c=ab.ac
:ab= ba . a.b=ab
:aa b=ab abc=abac
4
ncti5Foogiqon lfoe tincolbonnéeairaselbd nov sees Retobooléennv laue rruenu enusplu  one uéetr selbairav srueilogiion onctueF nnedne Peruq eigol noied : euqhoét muxsdetnérd e'ifineéD d'utiononctne faTlb e
Exemple : fonction f de trois variables a, b et c fa , b , c=abb ca c Par sa table de vérité
Par son expression logique
Combinaison des variables de la fonction via les opérateurs de base de l'algébre de boole
ens nt eeréelav srussopelbibina com de isonp uoitnoqaeu rhcder eualncfoa  liféd iuqv al tin
Tables de vérité
Table de vérité pour une fonction àpvariables
Pour chacune des combinaisons différentes depva-leurs, préciser le résultat de la fonction
Table de vérité des opérateurs de base _      a | a a b | a + b a b | a.b ---+--- ------+------ ------+------       0 | 1 0 0 | 0 0 0 | 0 1 | 0 0 1 | 1 0 1 | 0  1 0 | 1 1 0 | 0  1 1 | 1 1 1 | 1
6
Fonction logique
Equivalence/passage entre expression logique et la table de vérité de la fonction
toujours déterminer l'une à partir de l'autreOn peut
Deux fonctions logiques sont identiques si
On peut montrer via les propriétés de l'algèbre de Boole que leurs expressions logiques sont identiques
Leurs tables de vérité sont identiques
Note
Quand on parle de fonction logique, on parle souvent de la forme correspondant à l'expression logique 7
Formes canoniques d'une fonction
Pour une fonction logique àxvariables
Un minterme : groupe desxvariables (pouvant être complémentées) liées par des ET
Un maxterme : groupe desxvariables (pouvant être complémentées) liées par des OU
Forme canonique d'une fonction logique
Première forme : union (OU) de mintermes
Second forme : intersection (ET) de maxtermes
8
Exemples de formes canoniques
Fonction à 3 variablesa,betc, exemples :
Mintermes :abc , a b b c , a b c , a c , ...
Maxtermes : abc , abc , abc , abc , ... Première forme canonique : f , c ba ,=abc ca ba b ca b c Seconde forme canonique :  ga , , c b=abc.abc.abc.abc
9
Passage aux formes canoniques
Partir de la fonction et la transformer pour faire apparaître des mintermes/maxtermes complets
Pour la transformation
On s'appuie sur les propriétés de l'algèbre de Boole, et notamment des invariants :
x.x = 0 et x + x = 1
10
Exemple de passage à la première forme canonique
Soit
f ba , , c=abb ca c
Premier mintermeab 
Il manque la variablec
Transformeabenab(c+ccarc+c=1
Même chose pour les 2 autres mintermes
D'où :
fa , b , c=abccb caaa cbb= abcab c ca b ca ba b c
11
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.