Cours : Algèbre de Boole

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 $f$ une fonction logique de $n$ variables $a_1,\,a_2,\,…,\, a_n$.

$$\begin{aligned} f: \lbrace0\ ;\,1\rbrace^n&\rightarrow \lbrace0\ ;\,1\rbrace \\ a_1,\,a_2,\,…,\, a_n&\mapsto f(a_1,\,a_2,\,…,\, a_n) \end{aligned}$$

À retenir

Quelques termes importants sont à connaître :

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

Attention

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

• $0$ est plutôt à interpréter comme « faux », « non vrai » ;
• $1$ est plutôt à interpréter comme « vrai ».

Théorème de De Morgan

Dans le cours précédent, en étudiant les portes $\text{NON ET}$ et $\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.

Théorème

Théorème de De Morgan :

Soit $n$ variables logiques $a_1,\,a_2,\,…,\,a_n$.

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

$$\overline{a_1+a_2+…+a_n}=\bar a_1 \cdot \bar a_2 \cdot … \cdot \bar a_,$$

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

$$\overline{a_1\cdot a_2\cdot …\cdot a_n}=\bar a_1 + \bar a_2 + … + \bar a_,$$

Propriétés sur une variable

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

$$\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.

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

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.

À retenir

Le produit logique a priorité sur la somme logique.

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

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

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

Exemple

Soit $S$ le résultat d’une opération entre $4$ variables binaires $a$, $b$, $c$ et $d$. Nous opérerons dans l’ordre de priorité indiqué.

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

• Négation :

À retenir

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

$$A=B \Leftrightarrow \bar A=\bar B$$

• Associativité :

À retenir

• $a\cdot b\cdot c=a\cdot(b\cdot c)=(a\cdot b)\cdot c$
• $a+ b+ c=a+(b+ c)=(a+ b)+c$

• Commutativité :

À retenir

• $a\cdot b=b\cdot a$
• $a+ b=b+ a$

• Distributivité :

À retenir

• $a\cdot (b+c)=a\cdot b + a\cdot c$
• $a+ b\cdot c=(a+ b) \cdot (a+ c)$
• $(a+b)\cdot (c+d)=a\cdot c+a\cdot d+b\cdot c + b\cdot d$

• Absorption :

À retenir

• $a+a\cdot b=a$
• $a+\bar a\cdot b=b+\bar b\cdot a=a+b$
• $a\cdot (a+b)=a$
• $a\cdot b + a\cdot \bar b=a$

Démonstration

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

$\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 $a$}]} \\ &=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.

$\begin{aligned} a\cdot b + a\cdot \bar b&= a\cdot (b + \bar b) \ \textcolor{#808080}{[\text{distributivité\ : factorisation par $a$}]} \\ &=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=1$), nous avons donné l’équation logique : $L=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é.

Définition

Minterme :

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

• Il existe $2^n$ mintermes différents possibles.

Exemple

Soit les $4$ variables logiques $a$, $b$, $c$ et $d$.

• Il y a $4$ facteurs dans chaque minterme.
• Il y a $2^4 = 16$ mintermes différents possibles.
• $a\cdot b\cdot c\cdot d$, ou $a\cdot\bar b\cdot c\cdot d$, ou $\bar a\cdot\bar b\cdot c\cdot d$, ou $a\cdot b\cdot c\cdot\bar d$ sont quelques mintermes.

Définition

Forme canonique disjonctive :

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

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

Exemple

• Soit $f$ une fonction booléenne de $4$ variables, telle que :

$$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 $4$ variables ou de leurs compléments.

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

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

• $a$ : mode automatique ;
• $\bar l$ : absence de luminosité ;
• $ p$ : présence d’une personne.
• C’est donc bien une équation écrite sous sa forme canonique disjonctive.

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 $n$ 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 $n$ 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 $\text{OU}$, avec pour variables d’entrée $a$ et $b$, et $S$, la variable de sortie :

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

• D’où la forme canonique disjonctive : $S=\bar a\cdot b+a\cdot \bar b+a\cdot b$.

À retenir

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

• sur chaque ligne où la sortie est $1$, 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 $\text{OU}$ : $S =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.

$$\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}$$

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 $\text{OU}$, nous voyons que $S=0$ sur une seule ligne (au lieu de trois).

• Nous pouvons donc écrire :

$$\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 $3$ variables $a$, $b$ et $c$, définie par l’équation logique : $S=b\cdot \bar c$.

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

$$\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é.

À retenir

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

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

• Cela donne :