Sauter au contenu
Logo image

Algèbre abstraite Théorie et applications

Thomas W. Judson

Section 19.2 Algèbres de Boole

Examinons de plus près l’exemple de l’ensemble des parties, \({\mathcal P}(X)\text{,}\) d’un ensemble \(X\text{.}\) L’ensemble des parties est un treillis ordonné par inclusion. Par définition de l’ensemble des parties, le plus grand élément de \({\mathcal P}(X)\) est \(X\) lui-même et le plus petit élément est \(\emptyset\text{,}\) l’ensemble vide. Pour tout ensemble \(A\) dans \({\mathcal P}(X)\text{,}\) nous savons que \(A \cap X = A\) et \(A \cup \emptyset = A\text{.}\) Cela suggère la définition suivante pour les treillis. Un élément \(I\) dans un poset \(X\) est un plus grand élément si \(a \preceq I\) pour tout \(a \in X\text{.}\) Un élément \(O\) est un plus petit élément de \(X\) si \(O \preceq a\) pour tout \(a \in X\text{.}\)
🔗
Soit \(A\) dans \({\mathcal P}(X)\text{.}\) Rappelons que le complémentaire de \(A\) est
\begin{equation*} A' = X \setminus A = \{ x : x \in X \text{ et } x \notin A \}\text{.} \end{equation*}
Nous savons que \(A \cup A' = X\) et \(A \cap A' = \emptyset\text{.}\) Nous pouvons généraliser cet exemple pour les treillis. Un treillis \(L\) avec un plus grand élément \(I\) et un plus petit élément \(O\) est complémenté si pour chaque \(a \in L\text{,}\) il existe un \(a'\) tel que \(a \vee a' = I\) et \(a \wedge a' = O\text{.}\)
🔗
Dans un treillis \(L\text{,}\) les opérations binaires \(\vee\) et \(\wedge\) satisfont les lois commutatives et associatives ; cependant, elles ne satisfont pas nécessairement la loi distributive
\begin{equation*} a \wedge ( b \vee c ) = (a \wedge b ) \vee ( a \wedge c ); \end{equation*}
toutefois, dans \({\mathcal P}(X)\) la loi distributive est satisfaite puisque
\begin{equation*} A \cap ( B \cup C ) = (A \cap B ) \cup ( A \cap C ) \end{equation*}
pour \(A, B, C \in {\mathcal P}(X)\text{.}\) Nous dirons qu’un treillis \(L\) est distributif si la loi distributive suivante est satisfaite :
\begin{equation*} a \wedge ( b \vee c ) = (a \wedge b ) \vee ( a \wedge c ) \end{equation*}
pour tout \(a, b, c \in L\text{.}\)
🔗

Démonstration.

Supposons que \(L\) est un treillis distributif.
\begin{align*} a \vee ( b \wedge c ) & = [a \vee (a \wedge c) ] \vee ( b \wedge c )\\ & = a \vee [(a \wedge c) \vee ( b \wedge c )]\\ & = a \vee [(c \wedge a) \vee ( c \wedge b )]\\ & = a \vee [c \wedge ( a \vee b )]\\ & = a \vee [( a \vee b ) \wedge c ]\\ & = [( a \vee b ) \wedge a ] \vee [(a \vee b) \wedge c ]\\ & = ( a \vee b ) \wedge ( a \vee c )\text{.} \end{align*}
La réciproque découle directement du principe de dualité.
🔗
🔗
Une algèbre de Boole est un treillis \(B\) avec un plus grand élément \(I\) et un plus petit élément \(O\) tel que \(B\) est à la fois distributif et complémenté. L’ensemble des parties de \(X\text{,}\) \({\mathcal P}(X)\text{,}\) est notre prototype d’algèbre de Boole. Il s’avère que c’est également l’une des algèbres de Boole les plus importantes. Le théorème suivant nous permet de caractériser les algèbres de Boole en termes des relations binaires \(\vee\) et \(\wedge\) sans mentionner le fait qu’une algèbre de Boole est un poset.
🔗

Démonstration.

Soit \(B\) un ensemble satisfaisant (1)–(5) dans le théorème. L’une des lois idempotentes est satisfaite puisque
\begin{align*} a & = a \vee O\\ & = a \vee (a \wedge a')\\ & = (a \vee a) \wedge (a \vee a')\\ & = (a \vee a ) \wedge I\\ & = a \vee a\text{.} \end{align*}
Observons que
\begin{equation*} I \vee b = (b \vee b' ) \vee b = (b' \vee b ) \vee b = b' \vee (b \vee b) = b' \vee b = I\text{.} \end{equation*}
Par conséquent, la première des deux lois d’absorption est vérifiée, puisque
\begin{align*} a \vee (a \wedge b) & = (a \wedge I) \vee (a \wedge b)\\ & = a \wedge (I \vee b)\\ & = a \wedge I\\ & = a\text{.} \end{align*}
Les autres lois idempotentes et d’absorption se démontrent de manière similaire. Puisque \(B\) satisfait également (1)–(3), les conditions du Théorème 19.1.14 sont remplies ; donc \(B\) doit être un treillis. La condition (4) nous dit que \(B\) est un treillis distributif.
🔗
Pour \(a \in B\text{,}\) \(O \vee a = a\) ; donc \(O \preceq a\) et \(O\) est le plus petit élément de \(B\text{.}\) Pour montrer que \(I\) est le plus grand élément de \(B\text{,}\) nous allons d’abord montrer que \(a \vee b = b\) est équivalent à \(a \wedge b = a\text{.}\) Puisque \(a \vee I = a\) pour tout \(a \in B\text{,}\) en utilisant les lois d’absorption nous pouvons déterminer que
\begin{equation*} a \vee I =(a \wedge I) \vee I = I \vee ( I \wedge a) = I \end{equation*}
soit \(a \preceq I\) pour tout \(a\) dans \(B\text{.}\) Enfin, puisque nous savons que \(B\) est complémenté par (5), \(B\) doit être une algèbre de Boole.
🔗
Réciproquement, supposons que \(B\) est une algèbre de Boole. Soient \(I\) et \(O\) respectivement le plus grand et le plus petit élément de \(B\text{.}\) Si nous définissons \(a \vee b\) et \(a \wedge b\) comme la borne supérieure et la borne inférieure de \(\{ a, b\}\text{,}\) alors \(B\) est une algèbre de Boole par Théorème 19.1.14, Théorème 19.2.1, et notre hypothèse.
🔗
🔗
De nombreuses autres identités sont valables dans les algèbres de Boole. Certaines de ces identités sont énoncées dans le théorème suivant.
🔗

Démonstration.

Nous ne prouverons que (2). Les autres identités sont laissées en exercices. Pour \(a \vee b = a \vee c\) et \(a \wedge b = a \wedge c\text{,}\) nous avons
\begin{align*} b & = b \vee (b \wedge a)\\ & = b \vee (a \wedge b)\\ & = b \vee (a \wedge c)\\ & = ( b \vee a) \wedge ( b \vee c)\\ & = ( a \vee b) \wedge ( b \vee c)\\ & = ( a \vee c) \wedge ( b \vee c)\\ & = ( c \vee a ) \wedge ( c\vee b )\\ & = c \vee (a \wedge b)\\ & = c \vee ( a \wedge c )\\ & = c \vee ( c \wedge a )\\ & = c\text{.} \end{align*}
🔗
🔗

Sous-section 19.2.1 Algèbres de Boole finies

Une algèbre de Boole est une algèbre de Boole finie si elle contient un nombre fini d’éléments en tant qu’ensemble. Les algèbres de Boole finies sont particulièrement agréables car nous pouvons les classifier à isomorphisme près.
🔗
Soient \(B\) et \(C\) des algèbres de Boole. Une application bijective \(\phi : B \rightarrow C\) est un isomorphisme d’algèbres de Boole si
\begin{align*} \phi( a \vee b ) & = \phi(a) \vee \phi(b)\\ \phi( a \wedge b ) & = \phi(a) \wedge \phi(b) \end{align*}
pour tout \(a\) et \(b\) dans \(B\text{.}\)
🔗
Nous allons montrer que toute algèbre de Boole finie est isomorphe à l’algèbre de Boole obtenue en prenant l’ensemble des parties d’un ensemble fini \(X\text{.}\) Nous aurons besoin de quelques lemmes et définitions avant de prouver ce résultat. Soit \(B\) une algèbre de Boole finie. Un élément \(a \in B\) est un atome de \(B\) si \(a \neq O\) et \(a \wedge b = a\) pour tout \(b \in B\) avec \(b \neq O\text{.}\) De manière équivalente, \(a\) est un atome de \(B\) s’il n’existe pas de \(b \in B\) avec \(b \neq O\) distinct de \(a\) tel que \(O \preceq b \preceq a\text{.}\)
🔗

Démonstration.

Si \(b\) est un atome, posons \(a = b\text{.}\) Sinon, choisissons un élément \(b_1\text{,}\) différent de \(O\) et de \(b\text{,}\) tel que \(b_1 \preceq b\text{.}\) Nous avons la garantie que cela est possible puisque \(b\) n’est pas un atome. Si \(b_1\) est un atome, alors nous avons terminé. Sinon, choisissons \(b_2\text{,}\) différent de \(O\) et de \(b_1\text{,}\) tel que \(b_2 \preceq b_1\text{.}\) De nouveau, si \(b_2\) est un atome, posons \(a = b_2\text{.}\) En poursuivant ce processus, nous pouvons obtenir une chaîne
\begin{equation*} O \preceq \cdots \preceq b_3 \preceq b_2 \preceq b_1 \preceq b\text{.} \end{equation*}
Puisque \(B\) est une algèbre de Boole finie, cette chaîne doit être finie. C’est-à-dire que pour un certain \(k\text{,}\) \(b_k\) est un atome. Posons \(a = b_k\text{.}\)
🔗
🔗

Démonstration.

Puisque \(a \wedge b\) est la borne inférieure de \(a\) et \(b\text{,}\) nous savons que \(a \wedge b \preceq a\text{.}\) Donc, soit \(a \wedge b = a\) soit \(a \wedge b = O\text{.}\) Cependant, si \(a \wedge b = a\text{,}\) alors soit \(a \preceq b\) soit \(a = O\text{.}\) Dans l’un ou l’autre cas, nous arrivons à une contradiction car \(a\) et \(b\) sont tous deux des atomes ; donc \(a \wedge b = O\text{.}\)
🔗
🔗

Démonstration.

(1) \(\Rightarrow\) (2). Si \(a \preceq b\text{,}\) alors \(a \vee b = b\text{.}\) Donc,
\begin{align*} a \wedge b' & = a \wedge (a \vee b)'\\ & = a \wedge ( a' \wedge b')\\ & = ( a \wedge a') \wedge b'\\ & = O \wedge b'\\ & = O\text{.} \end{align*}
🔗
(2) \(\Rightarrow\) (3). Si \(a \wedge b' = O\text{,}\) alors \(a' \vee b = (a \wedge b')' = O' = I\text{.}\)
🔗
(3) \(\Rightarrow\) (1). Si \(a' \vee b = I\text{,}\) alors
\begin{align*} a & = a \wedge (a' \vee b)\\ & = (a \wedge a') \vee (a \wedge b)\\ & = O \vee (a \wedge b)\\ & = a \wedge b\text{.} \end{align*}
Ainsi, \(a \preceq b\text{.}\)
🔗
🔗

Démonstration.

Par le Lemme 19.2.6, \(b \wedge c' \neq O\text{.}\) Donc il existe un atome \(a\) tel que \(a \preceq b \wedge c'\text{.}\) Par conséquent, \(a \preceq b\) et \(a \not\preceq c\text{.}\)
🔗
🔗

Démonstration.

Posons \(b_1 = a_1 \vee \cdots \vee a_n\text{.}\) Puisque \(a_i \preceq b\) pour chaque \(i\text{,}\) nous savons que \(b_1 \preceq b\text{.}\) Si nous pouvons montrer que \(b \preceq b_1\text{,}\) alors le lemme est vrai par antisymétrie. Supposons \(b \not\preceq b_1\text{.}\) Alors il existe un atome \(a\) tel que \(a \preceq b\) et \(a \not\preceq b_1\text{.}\) Puisque \(a\) est un atome et \(a \preceq b\text{,}\) nous pouvons déduire que \(a = a_i\) pour un certain \(a_i\text{.}\) Cependant, cela est impossible puisque \(a \preceq b_1\text{.}\) Donc \(b \preceq b_1\text{.}\)
🔗
Supposons maintenant que \(b = a_1 \vee \cdots \vee a_n\text{.}\) Si \(a\) est un atome inférieur à \(b\text{,}\)
\begin{equation*} a = a \wedge b = a \wedge( a_1 \vee \cdots \vee a_n ) = (a \wedge a_1) \vee \cdots \vee ( a \wedge a_n )\text{.} \end{equation*}
Mais chaque terme est \(O\) ou \(a\text{,}\) avec \(a \wedge a_i\) n’apparaissant que pour un seul \(a_i\text{.}\) Donc, par le Lemme 19.2.5, \(a = a_i\) pour un certain \(i\text{.}\)
🔗
🔗

Démonstration.

Nous allons montrer que \(B\) est isomorphe à \({\mathcal P}(X)\text{,}\) où \(X\) est l’ensemble des atomes de \(B\text{.}\) Soit \(a \in B\text{.}\) Par le Lemme 19.2.8, nous pouvons écrire \(a\) de manière unique sous la forme \(a = a_1 \vee \cdots \vee a_n\) pour \(a_1, \ldots, a_n \in X\text{.}\) Par conséquent, nous pouvons définir une application \(\phi : B \rightarrow {\mathcal P}(X)\) par
\begin{equation*} \phi(a) = \phi( a_1 \vee \cdots \vee a_n ) = \{a_1, \ldots, a_n \}\text{.} \end{equation*}
Il est clair que \(\phi\) est surjective.
🔗
Soient maintenant \(a = a_1 \vee \cdots \vee a_n\) et \(b = b_1 \vee \cdots \vee b_m\) des éléments de \(B\text{,}\) où chaque \(a_i\) et chaque \(b_i\) est un atome. Si \(\phi(a) = \phi(b)\text{,}\) alors \(\{a_1, \ldots, a_n \} = \{b_1, \ldots, b_m \}\) et \(a = b\text{.}\) Par conséquent, \(\phi\) est injective.
🔗
La réunion de \(a\) et \(b\) est préservée par \(\phi\) puisque
\begin{align*} \phi(a \vee b) & = \phi( a_1 \vee \cdots \vee a_n \vee b_1 \vee \cdots \vee b_m )\\ & = \{ a_1, \ldots, a_n, b_1, \ldots, b_m \}\\ & = \{ a_1, \ldots, a_n \} \cup \{ b_1, \ldots, b_m \}\\ & = \phi( a_1 \vee \cdots \vee a_n ) \cup \phi( b_1 \wedge \cdots \vee b_m )\\ & = \phi(a) \cup \phi(b)\text{.} \end{align*}
De même, \(\phi( a \wedge b ) = \phi(a) \cap \phi(b)\text{.}\)
🔗
🔗
Nous laissons la preuve du corollaire suivant en exercice.
🔗
🔗
🔗
PrécédentTopSuivant