ALGÈBRE DE BOOLE

Page d'accueuil
Version PostScript
Version Adobe Acrobat

1. PRODUITS CARTESIENS DE DEUX ENSEMBLES
   1. Définition :

      Etant donnés deux ensembles E et F non vides, on appelle Produit cartésien de E et F l'ensemble des couples ${\displaystyle (x,y)}$ tels que ${\displaystyle x \in E \quad \textrm{et} \quad y \in F}$.

   2. Exemples :
      $$\displaystyle \left \lbrace \begin{array}{l@{\ =\ }l}% E & \{0, 1... ...w E\times F= \left \lbrace (0,0),(0,6),(1,0),(1,6),(2,0),(2,6)% \right \rbrace$$
      De même, $F\times F=F^{2}=\left\lbrace(0,0),(0,6),(6,0),(6,6)\right\rbrace$.

2. RELATION D'UN ENSEMBLE VERS LUI-MÊME :
   1. Définition : Une relation $\mathcal{R}$ d'un ensemble E vers lui-même est définie par une partie non vide de $E^{2}$. L'ensemble des couples $(x,y)$ tels que $x\,\mathcal{R}\,y$ s'appelle le graphe de la relation.

   2. exemple :

      Considérons l'ensemble $E=\{0, 1, 2\}$ et la relation "inférieur ou égal à".

      On aura : $x\mathcal{R}y\iff x\leqslant y$. Le graphe G de cette relation est alors :

      $$G=\{(0,0), (0,1), (0,2), (1,1), (1,2), (2,2)\}$$

   3. Représentation graphique de la relation :

      Il existe un arc orienté de x vers y si et seulement si $x\,\mathcal{R}\,y$.

   4. Représentation matricielle de la relation : C'est une matrice A numérique dont le terme $a_{ij}$ vaut 1 s'il existe un arc de $x_{i}$ vers $x_{j}$ et 0 sinon. Dans l'exemple ci-dessus, on obtient :
      $$A=\left[ \begin{array}{lll} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \\ \end{array}\right]$$

   5. Réflexivité d'une relation :

      La relation $\mathcal{R}$ est réflexive lorsque tout élément de l'ensmble est relié à lui-même par un arc.

      $$\forall x \in E,\quad x\,\mathcal{R}\,x$$
      Dans ce cas, la première diagonale de la matrice ne contient que des 1.

      C'est le cas de la relation $\leqslant$ et de la relation $=$ dans I R.

   6. Relations symétrique :

      On dit qu'une relation est symétrique lorsque :

      $$\forall (x,y) \in E^{2}\quad x\,\mathcal{R}\,y\Longrightarrow y\,\mathcal{R}\,x$$
      Autrement dit, s'il y a un arc de x vers y, alors il y a nécessairement un arc en retour de y vers x Dans la matrice on aura alors $a_{ij}=a_{ji}$, ce qui fait que la matrice d'une relation symétrique est symétrique par rapport à la première diagonale.

      Par exemple, la relation d'égalité est à la fois réflexive et symétrique.

   7. Relation anti-symétrique :

      Une relation est antisymétrique lorsque : $\forall (x,y) \in E^{2}\quad \left. \begin{array}{l@{\,\mathcal{R}\,}l} x & y \\ y & x \\ \end{array}\right\rbrace \Longrightarrow x = y$

      Cette définition exprime qu'il est impossible d'avoir un aller-retour direct entre deux éléments distinct, le seul cas autorisé étant l'aller-retour entre un élément et lui-même.

   8. Remarque :

      Il ne faut pas confondre la non symétrie avec l'antisymétrie. Par exemple, la relation d'égalité est à la fois symétrique et antisymétrique car les seuls aller-retour possibles ne se font qu'entre un élément et lui-même (antisymétrie).

   9. Transitivité :

      La relation $\mathcal{R}$ est transitive lorsque : $\forall (x,y,z) \in E^{3}\quad \left. \begin{array}{l@{\,\mathcal{R}\,}l} x & y \\ y & z \\ \end{array}\right\rbrace \Longrightarrow x \,\mathcal{R}\,z$

      Ceci exprime que s'il y a un arc de x vers y et un arc de y vers z, alors il y a nécessairement un arc direct de x vers z.

3. ENSEMBLES ORDONNÉS :
   1. Relation d'ordre :

      Une relation d'ordre est à la fois réflexive, antisymétrique et transitive. C'est le cas de la relation $\leqslant$ dans l'ensemble de nombres réels. On convient de noter $\leqslant$ toute relation d'ordre dans ce qui va suivre. On appelle ensemble ordoné tout ensemble muni d'une relation d'ordre.

   2. majorant et minorant :

      Dans un ensemble ordonné, s'il y a un arc de x vers y, alors on a : $x \leqslant y$. On dit que y est un majorant de x ou encore que x est un minorant de y.

   3. Ordre partiel et ordre total :

      Une relation d'ordre est partiel lorsque il existe un couple déléments distincts non reliés par un arc. L'ordre est total lorsque il existe toujours un arc entre deux éléments quelconques.

   4. Borne supérieure et borne inférieure :
      • La borne supérieure du couple $(x,y)$ est le plus petit des majorants communs à x et y s'il existe. On note $a + b$ la borne sup du couple $(a,b)$.
      • La borne inférieure du couple $(x,y)$ est le plus grand des minorants communs à x et y s'il existe. On note $a \times b$ ou encore $a\,b$ la borne inférieure du couple $(a,b)$.
      • On a : $x+x=x$ et on a aussi : $x \times x=x^{2}=x$. Cela résulte immédiatement de la définition.
      • Remarque très importante : $x\leqslant y \iff \left\lbrace \begin{array}{l@{\ =\ }l} x+y & y \\ x\,y & x \end{array}\right.$
   5. Plus grand élément, plus petit élément :
      • Le plus grand éleément, s'il existe, est un élément recevant un arc de tous les autres.
      • Le plus petit élément, s'il existe, envoit un arc sur tous les autre.
   6. Exemple : On considère un ensemble $E=\{x_{1}, x_{2}, x_{3}, x_{4}\}$ muni d'une relation d'ordre définie par la matrice A :
      $$\left[ \begin{array}{llll} 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array}\right]$$
      • Construire le graphe de la relation définie par A
      • Vérifier que c'est une relation d'ordre partiel.
      • Y-a-t-il un plus grand élément? un plus petit élément?
      • Construire les tables des opérations $+$ et $\times$ dans cet ensemble. On laissera vide les cases où l'opération est impossible.
4. ALGEBRE DE BOOLE
   1. Définition : soit E un ensemble non vide muni d'une relation d'ordre. E possède un plus grand élément, noté 1, un plus petit élément noté 0. Attention, ce ne sont pas des nombres entiers. On suppose la double distributivité de + sur $\times$ et de $\times$ sur +
      $$x+yz = (x+y)\,(x+z)\qquad\textrm{et}\qquad x\,(y+z)= x\,y+x\,z$$
      Pour tout élément x, il existe un élément $x^{\prime}$ vérifiant les deux équations suivantes :
      $$x+x^{\prime}=1\qquad\textrm{et}\qquad x\,x^{\prime}=0$$
      L'élément $x^{\prime}$ s'appelle complément de x.
   2. Unicité du complément d'un élément x:

      Démontrons que, dans une algèbre de Boole, un élément x ne peut avoir qu'un seul complément.

      Si $x^{\prime}$ et $x^{\prime\prime}$ étaient tous deux compléments du même x, on aurait :

      $$x+x^{\prime}=1 \quad\textrm{et}\quad x\,x^{\prime\prime}=0$$
      En multipliant chaque membre de la première égalité par $x^{\prime\prime}$, on en tire :
      $$(x+x^{\prime})x^{\prime\prime}=x^{\prime\prime}\Longrightarrow x^... ...me\prime}=x^{\prime\prime}\Longrightarrow x^{\prime}\leqslant x^{\prime\prime}$$
      De même, à partir de $x+x^{\prime\prime}=1 \quad\textrm{et}\quad x\,x^{\prime}=0$ on prouverait que $x^{\prime\prime}\leqslant x^{\prime}$.

      On aurait alors : $\left\lbrace \begin{array}{l@{\ \leqslant\ }l} x^{\prime} & x^{\prime\prime} \... ... x^{\prime} \\ \end{array}\right. \Longrightarrow x^{\prime}=x^{\prime\prime}$, CQFD.

      Puisque le complément de x est unique, on peut le noter de manière symbolique : $\overline{x}$.

   3. Exemple d'algèbre de Boole à quatre éléments :

      Figure 1: Algèbre de Boole à 4 éléments

      

      Construisons la table d'addition et la table de multiplication de l'algèbre de Boole ci-dessus

      
      
      

      +	0	a	b	1
      0	0	a	b	1
      a	a	a	1	1
      b	b	1	b	1
      1	1	1	1	1

               et        

      $\times$	0	a	b	1
      0	0	0	0	0
      a	0	a	0	a
      b	0	0	b	b
      1	0	a	b	1

      La figure comme les tables montrent que chaque élément possède un complément :
      $$\overline{0}=1 \qquad \overline{a}=b \qquad \overline{b}=a \qquad \overline{1}=0$$

   4. Lois de De Morgan : $\overline{\strut{x+y}}= \overline{\strut{x}}\;\overline{\strut{y}}\qquad \overline{\strut{x\,y}}= \overline{\strut{x}}+\overline{\strut{y}}$

      Pour prouver la première, il suffit de démontrer que la somme et le produit de $x+y$ avec $\overline{\strut{x}}\;\overline{\strut{y}}$ valent respectivement 1 et 0.

      • $x+y+ \overline{\strut{x}}\;\overline{\strut{y}}= (x+y+\overline{\strut{x}})\,(x+y+\overline{\strut{y}})= (1+y)\,(1+x)=1\times1=1$

      • $(x+y)\,\overline{\strut{x}}\;\overline{\strut{y}}= x\,\overline{\strut{x}}\;\overline{\strut{y}}+ y\,\overline{\strut{x}}\;\overline{\strut{y}}= 0+0=0$
      On démontre la deuxième à partir de la première en remplaçant chaque variable par son

      complémentaire puis en appliquant le complément sur chaque membre de l'égalité obtenue.

   5. Théorème : On peut additionner membre à membre deux inégalités booléennes de même sens.

      En effet, $\left\lbrace \begin{array}{l@{\ \leqslant\ }l} x & y \\ x^{\prime} & y^{\prim... ...y+y^{\prime})=y+y^{\prime} \Longrightarrow x+x^{\prime} \leqslant y+y^{\prime}$

      On démontrerait d'une manière analogue qu'il est possible de multiplier membre deux inégalités booléennes de même sens.

   6. Théorème : $x+y=0\Longrightarrow x=y=0$

      En effet, $x+y$, c'est-à-dire ici 0, est un majorant commun à x et à y. On a donc :

      $$x+y=0 \Longrightarrow \left\lbrace \begin{array}{l@{\ \leqslant\ ... ... \left\lbrace \begin{array}{l@{\ =\ }l} x & 0 \\ y & 0 \\ \end{array}\right.$$
      Les deux dernières inégalités résultent du fait que 0 est le plus petit de tous les éléments d'une algèbre de Boole.

      De même, on a $x\,y=1\Longrightarrow x=y=1$. On le déduit aisément du théoréme précédent en utilisant un des lois de De Morgan.

5. ALGEBRE DE BOOLE BINAIRE
   1. Définition : C'et une algèbre de Boole à deux éléments, le plus petit noté 0 et le plus grand noté 1. Elle se représente au moyen du graphe ci-dessous :

      Figure 2: Algèbre de Boole binaire

      
   2. Fonctions à une variable binaire :

      On sait qu'il existe $n^{p}$ fonctions possibles définies sur un ensemble E à p éléments vers un ensemble F à n éléments.

      Or les focntions booléennes binaires à une variable ne sont rien d'autre que des fonctions de $\{\,0\;;\;1\,\}$ vers $\{\,0\;;\;1\,\}$. Ces fonctions sont donc au nombre de $2^{2}=4$.

      $$\begin{array}{\vert c\vert c\vert} \hline x & f_{0}(x) \\ \hline 0 & 0 \\ 1 & 0 \\ \hline \end{array}$$
      $$\begin{array}{\vert c\vert c\vert} \hline x & f_{1}(x) \\ \hline 0 & 0 \\ 1 & 1 \\ \hline \end{array}$$
      $$\begin{array}{\vert c\vert c\vert} \hline x & f_{2}(x) \\ \hline 0 & 1 \\ 1 & 0 \\ \hline \end{array}$$
      $$\begin{array}{\vert c\vert c\vert} \hline x & f_{3}(x) \\ \hline 0 & 1 \\ 1 & 1 \\ \hline \end{array}$$
      Remarquons que l'on a : $f_{0}(x)=0;\qquad f_{1}(x)=x;\qquad f_{2}(x)=\overline{x};\qquad f_{3}(x)=1$

   3. Fonctions booléennes à deux variables :

      Avec deux variables, l'ensemble de définition de nos fonctions est $\{\,0\;;\;1\,\}^{2}$ et l'ensemble d'arrivée est $\{\,0\;;\;1\,\}$. L'ensemble de définition comporte donc $2^{2}=4$ éléments, celui d'arrivée en comporte 2. On a donc $2^{4}=16$ fonctions booléennes binaires à deux variables. En voici quatre parmi les seize possibles.

      $$\begin{array}{\vert c\vert c\vert c\vert} \hline x & y & f_{0}(x,... ...line 0 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 0 \\ \hline \end{array}$$
      $$\begin{array}{\vert c\vert c\vert c\vert} \hline x & y & f_{1}(x,... ...line 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 0 \\ \hline \end{array}$$
      $$\begin{array}{\vert c\vert c\vert c\vert} \hline x & y & f_{2}(x,... ...line 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 0 \\ \hline \end{array}$$
      $$\begin{array}{\vert c\vert c\vert c\vert} \hline x & y & f_{3}(x,... ...line 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 0 \\ \hline \end{array}$$

6. ECRITURE POLYNOMIALE DES FONCTIONS BOOLENNES :
   1. Première forme normale, les mintermes :
      • Fonctions à une variable :

        La consultation des tableaux montre aussitôt que :

        
        On le vérifie immédiatement en remplaçant x successivement par 0 puis par 1 et on démontre ainsi qu'elle reste vraie dans tous les cas de figure (il n'y en a que deux...). En remplaçant les constantes $f(0)$ et $f(1)$ par leurs valeurs, on obtient par exemple :
        $$f_{2}(x)=\overline{x}\qquad f_{1}(x)=x$$

      • Fonctions à deux variables :

        Appliquons le résultat trouvé ci-dessus en ne manipulant que la variable x.

        $$f(x,y)=\overline{x}f(0,y)+xf(1,y)$$

        Toujours en utilisant le même théorème appliqué cette fois à y :

        $$f(0,y)=\overline{y}f(0,0)+yf(0,1)\qquad\textrm{et}\qquad f(1,y)=\overline{y}f(1,0)+yf(1,1)$$
        En remplaçant $f(0,y)$ et $f(1,y)$ par leurs expressions, il vient :
        
        Appliquons ce résultat à la fonction $f_{1}$ On a : $f_{1}(x,y)=\overline{x}\,\overline{y}$.

        Appliquons-le à $f_{3}$ : $f_{3}(x,y)=\overline{x}\,\overline{y}+\overline{x}\,y$

      • Fonctions à trois variables binaires :

        La formule se généralise :

        $f(x,y,z)= \overline{x}\,\overline{y},\overline{z}\,f(0,0,0)+ \overline{x}\,\ov... ...(0,0,1)+ \overline{x}\,y\,\overline{z}\,f(0,1,0)+ \overline{x}\,y\,z\,f(0,1,1)$

        $x\,\overline{y},\overline{z}\,f(1,0,0)+ x\,\overline{y}\,z\,f(1,0,1)+ x\,y\,\overline{z}\,f(1,1,0)+ x\,y\,z\,f(1,1,1)$

      L'expression de $f$, quel qu'il soit, se présente comme une somme de produits, or ces produits sont par définition des bornes inférieures, d'où l'usage du mot mintermes.
   2. Deuxième forme normale, les maxtermes
      • Fonctions à une variable : Appelons g la fonction telle que $\overline{f(x)}=g(x)$, puis appliquons une formule de De Morgan pour calculer $\overline{g(x)}$.
        $g(x)=\overline{x}\,g(0)+x\,g(1)\Longrightarrow \overline{g(x)}=[x+\overline{g(0)}]\,[\overline{x}+\overline{g(1)}]$
        Il en résulte que :

      • Fonctions à deux variables :

        En procédant de manière analogue à celle utilisée pour la première forme normale, on trouve :

        
        On voit ainsi que dans la deuxième forme normale, on a un produit de plusieurs sommes, alors que dans la première, on a une somme de plusieurs produits.
   3. Application des formes normales aux tables booléennes :

      Considérons la fonction booléenne définie par la table :

      $$\begin{array}{\vert c\vert c\vert c\vert} \hline x & y & f(... ...& 1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 0 \\ \hline \end{array}$$

      Pour utiliser la première forme normale, on repère tous les cas où la fonction vaut 1, sans s'interesser aux autres car les valeurs de $f(x,y)$ sont les coefficients du polynôme. Pour chaque cas où la fonction vaut 1, on multiplie ce coefficients par un minterme, selon la règle énoncé plus haut.

      On obtient : $f(x,y)=\overline{x}\,\overline{y} + \overline{x}\,y$

      On obtient ces deux termes uniquement en lisant les deux premières lignes du tableau de la fonction.

      On peut également utiliser la deuxième forme normale. Les facteur où la fonction vaut 1 disparaissent car on a $1+u=1$. Seuls restent ceux où la fonction vaut 0. Dans le cas présent, on obtient en lisant seulement les deux dernières lignes de la table : $f(x,y)=(\overline{x}+y)\,(\overline{x}+\overline{y})$

      On peut simplifier : $f(x,y)=\overline{x}\,\overline{y} + \overline{x}\,y= \overline{x}\,(\overline{y}+y)=\overline{x}$ et $(\overline{x}+y)\,(\overline{x}+\overline{y})= \overline{x}+y\overline{y}=\overline{x}$

7. EXERCICES
   1. Simplifier : penser à $(x+y)(x+z)=x+yz$

      $(a+b)\,(a+c);\qquad (a+b)\,(a+c)+(b+c)\,(b+a)+(c+a)\,(c+b)$

      $(x+y)\,(x+z)\,(x+t)\,(x+u); \qquad(a+b+c)(a+\,\overline{b}\,+c)(a+\,\overline{b}\,+\,\overline{c}\,)$

   2. Trouver les complémentaires de :

      $a+b\,\overline{c}\,;\qquad \,\overline{a}\,(b+c);\qquad a\,b\,(\,\overline{a}\,+b+c) \qquad ab+b\,\overline{c}\,+c\,\overline{a}\,$

   3. On considère l'algèbre de Boole à quatre éléments $\mathcal{B}=\{0, a, b, 1\}$ dans laquelle on suppose que 0 et 1 sont respectivement le plus petit et le plus grand élément. On suppose également que l'ordre est partiel dans la mesure où aucun arc ne relie les éléments a et b.
      • Construire la table de la fonction à une variable $f(x)=\,\overline{x}\,$.
      • Construire la table de la fonction à deux variables $g(x,y)=x\,\overline{y}\,+\,\overline{x}\,y$
      • Est-il possible d'appliquer les formes normales comme pour une algèbre de Boole à deux éléments?
   4. Construire, dans une algèbre de Boole à deux éléments, la table de la fonction f définie par $f(x,y,z)=\,\overline{x}\,\,\overline{y}\,\,\overline{z}\,+x+y+z$. Ecrire l'expression de $g(x,y,z)$ en première forme puis en deuxième forme normale. Résoudre l'équation $g(x,y,z)=x$.
8. ALGEBRE PROPOSITIONNELLE
   1. On associe àtoute proposition A une variable booléenne binaire a qui vaut 1 si A est vraie et 0 dans le cas contraire
   2. L'implication :

      On dit que $A\Longrightarrow B$ pour exprimer que :

      • Si A est vraie alors B est néssairement vraie.
      • Pour que A soit vraie, il est nécessaire que B le soit aussi.
      • Il suffit que A soit vraie pour que B le soit aussi.
      • fonction booléenne associée àl'implication

        Pour dire que $A\Longrightarrow B$, il suffit d'écrire que $\,\overline{a}\,+b=1$

   3. La conjonction :

      Pour dire que A et B sont simultanément vrais, il suffit de dire que $a\,b=1$.

   4. Le ou inclusif :

      Pour exprimer que l'une au moins des deux propsitions A et B est vraie, il suffit décrire que : $a+b=1$

   5. Exemple Quatre convives A, B, C, D sont attablés. On sait que :
      • Si A mange alors B mange.
      • Si B mange alors C mange
      • D boit si et seulemnt si C mange
      • Si B boit alors A boit
      On demande qui boit et qui mange, il y a peut-être plusieurs réponses possibles.