Médaille
N°1 pour apprendre & réviser du collège au lycée.
Algèbre de Boole

Déjà plus de

1 million

d'inscrits !

Introduction :

Un système automatisé s’organise autour de portes logiques ou d'équations logiques qui, en fonction des valeurs des entrées (capteur, bouton poussoir, détecteur, etc.), actionnent des sorties (voyant, contacteur, vérin, etc.).
Il peut y avoir de nombreuses entrées et sorties, il est donc important de connaître les règles qui régissent cette algèbre si particulière, appelée algèbre de Boole.

Ce cours donnera les principales propriétés de calcul et de simplification en algèbre binaire. Il explicitera aussi les correspondances entre les différentes notions que nous avons découvertes : table de vérité, équation logique, etc.

Propriétés

Tout d’abord, puisqu’il est ici question de mathématiques, nous pouvons exprimer mathématiquement ce qu’est une fonction logique (ou booléenne).

Soit ff une fonction logique de nn variables a1,a2,,ana1,\,a2,\,…,\, a_n.

f:{0 ;1}n{0 ;1}a1,a2,,anf(a1,a2,,an)\begin{aligned} f: \lbrace0\ ;\,1\rbrace^n&\rightarrow \lbrace0\ ;\,1\rbrace \ a1,\,a2,\,…,\, an&\mapsto f(a1,\,a2,\,…,\, an) \end{aligned}

bannière à retenir

À retenir

Quelques termes importants sont à connaître :

  • aˉ\bar a est le complément de aa ;
  • avec la porte ET\text{ET}, on parle de produit (logique),
  • d’où le signe « \cdot » dans les équations logiques ;
  • avec la porte OU\text{OU}, on parle de somme (logique),
  • d’où le signe « ++ » dans les équations logiques.
bannière attention

Attention

N’oubliez pas que, en algèbre de Boole, les 00 et 11 que nous manipulons ne sont pas les réels avec lesquels nous travaillons habituellement.

  • 00 est plutôt à interpréter comme « faux », « non vrai » ;
  • 11 est plutôt à interpréter comme « vrai ».

Théorème de De Morgan

Dans le cours précédent, en étudiant les portes NON ET\text{NON ET} et NON OU\text{NON OU}, nous avions donné deux propriétés découvertes intuitivement.

  • Il s’agissait de l’expression du théorème de De Morgan.
bannière theoreme

Théorème

Théorème de De Morgan :

Soit nn variables logiques a1,a2,,ana1,\,a2,\,…,\,a_n.

  • Le complément d’une somme est égal au produit des compléments :

a1+a2++an=aˉ1aˉ2aˉ,\overline{a1+a2+…+an}=\bar a1 \cdot \bar a2 \cdot … \cdot \bar a,

  • Le complément d’un produit est égal à la somme des compléments :

a1a2an=aˉ1+aˉ2++aˉ,\overline{a1\cdot a2\cdot …\cdot an}=\bar a1 + \bar a2 + … + \bar a,

Propriétés sur une variable

  • Le complément du complément d’une variable est égal à la variable :

aˉˉ=a\bar{\bar a}=a

  • Il s’agit d’une double négation, et dire : « La lampe n’est pas non allumée », revient à dire : « La lampe est allumée ».
  • Le tableau ci-dessous donne les propriétés du produit logique. En outre, pour expliciter et représenter visuellement la formule donnée, nous mettrons un schéma électrique équivalent, comme nous l’avons fait dans un cours précédent.

Propriété Schéma électrique équivalent
a0=0a\cdot0=0

première sciences de l’ingénieur algèbre Boole

a1=aa\cdot 1=a

première sciences de l’ingénieur algèbre Boole

aa=aa\cdot a=a

première sciences de l’ingénieur algèbre Boole

aaˉ=0a\cdot\bar a=0

première sciences de l’ingénieur algèbre Boole

  • Le tableau ci-dessous donne les propriétés de la somme logique et un schéma électrique équivalent.

Propriété Schéma électrique équivalent
a+0=aa+0=a

première sciences de l’ingénieur algèbre Boole

a+1=1a+1=1

première sciences de l’ingénieur algèbre Boole

a+a=aa+a=a

première sciences de l’ingénieur algèbre Boole

a+aˉ=1a+\bar a=1

première sciences de l’ingénieur algèbre Boole

Propriétés sur plusieurs variables

Comme les maths sont toujours bien faites, nombre de règles que vous manipulez en algèbre classique sont aussi vraies en algèbre binaire : associativité, commutativité, distributivité. Et nous découvrirons aussi une autre propriété : l’absorption.

  • Avant tout, regardons les priorités d’opération.
bannière à retenir

À retenir

Le produit logique a priorité sur la somme logique.

  • La fonction ET\text{ET} a priorité sur la fonction OU\text{OU}.

Les parenthèses sont aussi à traiter en priorité.

  • La fonction NON\text{NON} est l’équivalent d’une parenthèse et doit être traitée en priorité.
bannière exemple

Exemple

Soit SS le résultat d’une opération entre 44 variables binaires aa, bb, cc et dd. Nous opérerons dans l’ordre de priorité indiqué.

a+bc+d123\underbrace{\large a+\underbrace {\large b\cdot\underbrace{ \overline{c+d}}{\red 1}}{\red 2}}_{\red 3}

  • Négation :
bannière à retenir

À retenir

Si deux expressions logiques sont égales, alors leurs compléments sont égaux :

A=BAˉ=BˉA=B \Leftrightarrow \bar A=\bar B

  • Associativité :
bannière à retenir

À retenir

  • abc=a(bc)=(ab)ca\cdot b\cdot c=a\cdot(b\cdot c)=(a\cdot b)\cdot c
  • a+b+c=a+(b+c)=(a+b)+ca+ b+ c=a+(b+ c)=(a+ b)+c
  • Commutativité :
bannière à retenir

À retenir

  • ab=baa\cdot b=b\cdot a
  • a+b=b+aa+ b=b+ a
  • Distributivité :
bannière à retenir

À retenir

  • a(b+c)=ab+aca\cdot (b+c)=a\cdot b + a\cdot c
  • a+bc=(a+b)(a+c)a+ b\cdot c=(a+ b) \cdot (a+ c)
  • (a+b)(c+d)=ac+ad+bc+bd(a+b)\cdot (c+d)=a\cdot c+a\cdot d+b\cdot c + b\cdot d
  • Absorption :
bannière à retenir

À retenir

  • a+ab=aa+a\cdot b=a
  • a+aˉb=b+bˉa=a+ba+\bar a\cdot b=b+\bar b\cdot a=a+b
  • a(a+b)=aa\cdot (a+b)=a
  • ab+abˉ=aa\cdot b + a\cdot \bar b=a
bannière demonstration

Démonstration

Par exemple, démontrons la première formule d’absorption donnée.

a+ab=a1+ab [car a1=a]=a(1+b) [distributiviteˊ : factorisation par a]=a1 [car 1+b=1]=a [toujours parce que a1=a]\begin {aligned} a+a\cdot b &= a\cdot 1+ a\cdot b\ \textcolor{#808080}{[\text{car } a\cdot 1=a]} \ &=a\cdot (1 + b)\ \textcolor{#808080}{[\text{distributivité\ : factorisation par aa}]} \ &=a\cdot 1\ \textcolor{#808080}{[\text{car } 1+b=1]} \ &=a\ \textcolor{#808080}{[\text{toujours parce que } a\cdot 1=a]} \end{aligned}

Démontrons aussi la dernière, car elle nous sera très utile par la suite.

ab+abˉ=a(b+bˉ) [distributiviteˊ : factorisation par a]=a1 [car b+bˉ=1]=a [car a1=a]\begin{aligned} a\cdot b + a\cdot \bar b&= a\cdot (b + \bar b) \ \textcolor{#808080}{[\text{distributivité\ : factorisation par aa}]} \ &=a\cdot 1\ \textcolor{#808080}{[\text{car } b+\bar b=1]} \ &=a\ \textcolor{#808080}{[\text{car } a\cdot 1=a]} \end{aligned}

Vous pouvez démontrer les deux autres, cela vous sera un bon entraînement !

Forme canonique

Dans les cours précédents, nous avons défini notamment ce qu’étaient une équation de vérité et une table de vérité. Nous avons aussi vu comment passer de la table de vérité à l’équation logique.
Dans l’application du dernier cours, avec le capteur de luminosité qui commande une lampe, à partir de la table de vérité et de la ligne où la lampe est éclairée (L=1L=1), nous avons donné l’équation logique : L=alˉpL=a\cdot \bar{l}\cdot p.

  • Cette équation était écrite sous sa forme canonique disjonctive.

Forme canonique disjonctive

La forme canonique disjonctive nous intéresse car elle donne une relation directe entre équation logique et table de vérité.

bannière definition

Définition

Minterme :

Soit nn variables logiques.
Un minterme est un produit de nn facteurs, chaque facteur étant une variable donnée ou son complément.

  • Il existe 2n2^n mintermes différents possibles.
bannière exemple

Exemple

Soit les 44 variables logiques aa, bb, cc et dd.

  • Il y a 44 facteurs dans chaque minterme.
  • Il y a 24=162^4 = 16 mintermes différents possibles.
  • abcda\cdot b\cdot c\cdot d, ou abˉcda\cdot\bar b\cdot c\cdot d, ou aˉbˉcd\bar a\cdot\bar b\cdot c\cdot d, ou abcdˉa\cdot b\cdot c\cdot\bar d sont quelques mintermes.
bannière definition

Définition

Forme canonique disjonctive :

Toute fonction booléenne ff peut s’écrire sous sa forme disjonctive.

  • Celle-ci est son unique écriture sous forme d’une somme de mintermes.
bannière exemple

Exemple

  • Soit ff une fonction booléenne de 44 variables, telle que :

f(a,b,c,d)=abcd+abˉcd+aˉbˉcd+abcdˉf(a,\,b,\,c,\,d)= a\cdot b\cdot c\cdot d+ a\cdot\bar b\cdot c\cdot d+\bar a\cdot\bar b\cdot c\cdot d + a\cdot b\cdot c\cdot\bar d

Il s’agit d’une somme entre termes formés par le produit des 44 variables ou de leurs compléments.

  • La fonction ff est écrite sous sa forme canonique disjonctive.
  • Reprenons notre équation : L=alˉpL=a\cdot \bar{l}\cdot p.

Il s’agit d’une somme de 11 terme, formé par le produit de chaque variable, ou son complément, dont dépend la lampe :

  • aa : mode automatique ;
  • lˉ\bar l : absence de luminosité ;
  • p p : présence d’une personne.
  • C’est donc bien une équation écrite sous sa forme canonique disjonctive.
bannière attention

Attention

Il existe une autre forme canonique, dite conjonctive. Elle ne concerne pas notre propos ici, nous n’entrerons donc pas dans le détail.
Sachez juste qu’une fonction booléenne de nn termes peut aussi s’écrire, de manière unique, sous une forme canonique conjonctive, qui est un produit de maxtermes, un maxterme étant une somme de nn termes correspondant à une variable ou à son complément.

Forme disjonctive et table de vérité

  • Passage de la table de vérité à l’équation logique

Reprenons, par exemple, la table de vérité de la fonction OU\text{OU}, avec pour variables d’entrée aa et bb, et SS, la variable de sortie :

aa bb S\red S
00 00 0\red 0
00 11 1\red1 aˉb\Rightarrow \bar a \cdot b
11 00 1\red1 abˉ\Rightarrow a\cdot\bar b
11 11 1\red1 ab\Rightarrow a \cdot b

S=1S=1 pour les trois dernières lignes.

  • D’où la forme canonique disjonctive : S=aˉb+abˉ+abS=\bar a\cdot b+a\cdot \bar b+a\cdot b.
bannière à retenir

À retenir

Pour passer d’une table de vérité à son équation logique :

  • sur chaque ligne où la sortie est 11, nous effectuons le produit des valeurs de chaque variable de la ligne ;
  • puis nous effectuons la somme des produits obtenus.
  • Ceci étant fait, nous avons obtenu l’équation logique sous sa forme canonique disjonctive.

Vous vous en êtes peut-être rendu compte, l’équation donnée plus haut était différente de l’équation que nous avions définie pour OU\text{OU} : S=a+bS =a+b.

  • Les deux équations sont évidemment équivalentes. Nous allons le montrer mathématiquement, ce qui nous permettra de manipuler les propriétés vues en première partie sur un exemple simple.

S=aˉb+abˉ+ab=aˉb+a(bˉ+b) [distributiviteˊ : factorisation par a]=aˉb+a [car b+bˉ=1]=a+aˉb [commutativiteˊ]=a+b [absorption]\begin{aligned} S&=\bar a\cdot b+a\cdot \bar b+a\cdot b \ &=\bar a\cdot b+a\cdot(\bar b+ b) \textcolor{#808080}{\text{ [distributivité : factorisation par }a]} \ &=\bar a\cdot b+a\ \textcolor{#808080}{[\text{car } b+\bar b=1]} \ &=a+\bar a\cdot b \textcolor{#808080}{\text{ [commutativité]}} \ &=a+b \textcolor{#808080}{\text{ [absorption]}} \end{aligned}

bannière astuce

Astuce

Nous pouvons aussi aller plus vite, cette fois en utilisant le théorème de De Morgan.
À partir de la table de vérité de OU\text{OU}, nous voyons que S=0S=0 sur une seule ligne (au lieu de trois).

  • Nous pouvons donc écrire :

S=aˉbˉS=aˉbˉS=aˉˉ+bˉˉ [car S=S, puis par le theˊoreˋme de De Morgan]=a+b [toujours par le principe de la double neˊgation]\begin{aligned} \overline S&=\bar a\cdot \bar b \ \overline {\overline {S}} &=\overline{\bar a\cdot \bar b } \ S&=\bar{\bar a}+\bar{\bar b} \textcolor{#808080}{ \text{ [car }\overline {\overline {S}}=S \text{, puis par le théorème de De Morgan]}} \ &=a+b \textcolor{#808080}{\text{ [toujours par le principe de la double négation]}} \end{aligned}

  • Passage de l’équation logique à la table de vérité

Soit la fonction logique de 33 variables $a$, bb et cc, définie par l’équation logique : S=bcˉS=b\cdot \bar c.

  • Mettons l’équation sous sa forme canonique disjonctive :

S=bcˉ=1bcˉ [car 1 est l’eˊleˊment neutre de ET]=(a+aˉ)bcˉ [car a+aˉ=1]=abcˉ+aˉbcˉ [par distributiviteˊ]\begin{aligned} S&=b\cdot \bar c \ &=1\cdot b\cdot \bar c \textcolor{#808080}{\text{ [car }1\text{ est l’élément neutre de ET]}} \ &=(a+\bar a) \cdot b\cdot \bar c \textcolor{#808080}{\text{ [car }a+\bar a=1]} \ &=a\cdot b\cdot \bar c + \bar a\cdot b\cdot \bar c \textcolor{#808080}{\text{ [par distributivité]}} \end{aligned}

  • Il est maintenant possible d’écrire la table de vérité.
bannière à retenir

À retenir

Pour passer d’une équation logique à la table de vérité, nous mettons :

  • S=1S=1 sur chaque ligne concernée par l’équation ;
  • S=0S=0 sur les autres.
  • Cela donne :

$a$ bb cc S\red S
00 00 00 0\red 0
00 00 11 0\red 0
00 11 00 1\red 1
00 11 11 0\red0
11 00 00 0\red0
11 00 11 0\red0
11 11 00 1\red1
11 11 11 0\red0

Conclusion :

Nous connaissons maintenant les propriétés de l’algèbre binaire et nous savons, par exemple, passer d’une table de vérité à une équation logique.
Celle-ci, toutefois, n’apparaît pas toujours sous sa forme simplifiée (nous l’avons vu pour la fonction OU\text{OU}).

Il est donc important de pouvoir simplifier une telle écriture. C’est ce que le prochain cours va nous apprendre.