"'O
0
c
:J
0
:<:;
li)
.,,
..--t
c::
:l
0
~
N
"
@
~
.......
0
J::
:;
O'l
"'
·;::::
c::
0
>c::
o.
c::
0
.9
u
ü
:l
.,,
2
o.
~
"
:;
0
11
.,,
0
c:
:l
0
QJ
4.3 • Calcul booléen
Propriété 4.4
Dans une algèbre de Boole :
- L'addition et la multiplication sont commutatives : a+ b = b +a ; ab= ba .
- L' addition et la multiplication sont associatives : (a+ b) + c =a+ (b + c) ;
(ab)c = a(bc).
- La multiplication et l'addition sont distributives l'une par rapport à l' autre :
a ( b + c) = ab + ac ; a + be = (a + b )(a + c) .
- 0 est élément neutre de l'addition : 0 +a =a+ 0 =a .
- 1 est élément neutre de la multiplication : la= al= a .
- 1 est élément absorbant de l'addition: a+ 1=1+a=1.
- 0 est élément absorba_!!t de la f!!Ultiplication: Oa = aO = 0.
- Quel que soit a: a+ a= 1 ; aa = 0.
Les démonstrations de la distributivité seront proposées dans l'exercice 4.20, les
autres propriétés sont très simples à démontrer.
Exemple
Montrons que 0 est élément neutre de l'addition :
Si a= 0, alors a+ 0 = 0 + 0 = 0 et 0 + a= 0 + 0 =O . Le résultat est égal à la valeur
de a.
Si a= 1, alors a+ 0 = 1 + 0 = 1 et 0 + a= 0 + 1 = 1. Le résultat est encore égal à
la valeur de a.
Donc, quel que soit a, on a 0 + a= a+ 0 = a.
Dans une expression, la complémentation est prioritaire sur la multiplication, qui
est elle-même prioritaire sur l'addition.
_ Si_ on doit calculer a + b c pour a = 0 , b = 1 et c = 0 , on commence par calculer
c = Ü= l.
-
-
Puis on calcule le produit be= 1·1=1 et enfin la somme a+ be= 0+1=1.
a+ a= a et plus généralement a+ a+ ... + a= a.
aa = a et plus généralement aa ... a = a .
Ces formules montrent qu' en calcul booléen, il n'y a ni multiple ni puissance.
4.3.3 Lois de Morgan
Propriété 4.5 (lois de Morgan)
Quelles qu~ sol_ent les variables a et b d'une algèbre de Boole, on a : a+ b = a· b
et a·b = a+b.
Les démonstrations peuvent se faire avec des tables de vérité comme illustré par
les tableaux 4.13 et 4.14.
Les r~s_.!:lltats identiques dans les colonnes ~olQ_rées du tableau 4.13 montrent que
a+ b = ab et dans le tableau 4.14, que ab = a+ b.
97
0
c
:J
0
:<:;
li)
.,,
..--t
c::
:l
0
~
N
"
@
~
.......
0
J::
:;
O'l
"'
·;::::
c::
0
>c::
o.
c::
0
.9
u
ü
:l
.,,
2
o.
~
"
:;
0
11
.,,
0
c:
:l
0
QJ
4.3 • Calcul booléen
Propriété 4.4
Dans une algèbre de Boole :
- L'addition et la multiplication sont commutatives : a+ b = b +a ; ab= ba .
- L' addition et la multiplication sont associatives : (a+ b) + c =a+ (b + c) ;
(ab)c = a(bc).
- La multiplication et l'addition sont distributives l'une par rapport à l' autre :
a ( b + c) = ab + ac ; a + be = (a + b )(a + c) .
- 0 est élément neutre de l'addition : 0 +a =a+ 0 =a .
- 1 est élément neutre de la multiplication : la= al= a .
- 1 est élément absorbant de l'addition: a+ 1=1+a=1.
- 0 est élément absorba_!!t de la f!!Ultiplication: Oa = aO = 0.
- Quel que soit a: a+ a= 1 ; aa = 0.
Les démonstrations de la distributivité seront proposées dans l'exercice 4.20, les
autres propriétés sont très simples à démontrer.
Exemple
Montrons que 0 est élément neutre de l'addition :
Si a= 0, alors a+ 0 = 0 + 0 = 0 et 0 + a= 0 + 0 =O . Le résultat est égal à la valeur
de a.
Si a= 1, alors a+ 0 = 1 + 0 = 1 et 0 + a= 0 + 1 = 1. Le résultat est encore égal à
la valeur de a.
Donc, quel que soit a, on a 0 + a= a+ 0 = a.
Dans une expression, la complémentation est prioritaire sur la multiplication, qui
est elle-même prioritaire sur l'addition.
_ Si_ on doit calculer a + b c pour a = 0 , b = 1 et c = 0 , on commence par calculer
c = Ü= l.
-
-
Puis on calcule le produit be= 1·1=1 et enfin la somme a+ be= 0+1=1.
a+ a= a et plus généralement a+ a+ ... + a= a.
aa = a et plus généralement aa ... a = a .
Ces formules montrent qu' en calcul booléen, il n'y a ni multiple ni puissance.
4.3.3 Lois de Morgan
Propriété 4.5 (lois de Morgan)
Quelles qu~ sol_ent les variables a et b d'une algèbre de Boole, on a : a+ b = a· b
et a·b = a+b.
Les démonstrations peuvent se faire avec des tables de vérité comme illustré par
les tableaux 4.13 et 4.14.
Les r~s_.!:lltats identiques dans les colonnes ~olQ_rées du tableau 4.13 montrent que
a+ b = ab et dans le tableau 4.14, que ab = a+ b.
97