cours-2-boole

Description

Algèbre de BooleEric CariouUniversité de Pau et des Pays de l'AdourDépartement [e-mail]1Algè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 ...

Informations

• Publié par: Immi
• Nombre de lectures: 38
• Langue: Français

Extrait

 Algèbre de Boole

Eric Cariou

Université de Pau et des Pays de l'Adour Département Informatique

[e-mail]

1

lgèbre d 2 A tsyS emè oB e  elo  cuestongéaliqbresbm'lned  etiéu Vari 1 }   0, le { : enneéloob elbapri que bliaar v uo  rT  1  siorépo d ene unleva 0ur ateurs de base ne  M rigi  O 1518, 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

aa=

a a a

a . a=0

a . a 0

=

a.a a

aa=1

a a 1

a=a .1=1. a=a a0=0a=a

a1=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.c abc=abc

: a.bc=a.ba.c ab.c=ab.ac

: ab= ba . a.b=ab

: aa b=ab abc=abac

4

ncti 5 Foogiqon l foe tincolbonnéeairaselbd nov se es   Reto booléenn v laue rruenu en usplu  one uéetr selbairav sruei logiion onct ue  F  nnedne P  er uq e igol noied : euqhoét muxsde tnérd   e' ifin  e éD d'utiononctne f  aTlb e

 Exemple : fonction f de trois variables a, b et c fa , b , c=abb ca 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 srussopelbi bina 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 : abc , abc , abc , abc , ...  Première forme canonique : f , c ba ,=abc ca ba b ca b c  Seconde forme canonique :   ga , , c b=abc.abc.abc.abc

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=abb ca c

 Premier mintermeab 

 Il manque la variablec

 Transformeabenab(c+ccarc+c=1

 Même chose pour les 2 autres mintermes

 D'où :

fa , b , c=abccb caaa cbb = abcab c ca b ca ba b c

11