Algèbre de Boole
Axiomes
Nous avons vu que les théories des ensembles et des propositions possédaient de nombreuses similitudes, notamment
CANDIMATIA. L'idée ici est d'introduire une "méga" théorie qui regroupe toutes ces théories similaire. La difficulté consiste alors à bien la définir : qu'est-ce qui est axiomatique et qu'est-ce qui se démontre ? Voici une réponse.
Définition
Une
algèbre de Boole \( \B\) est la donnée de :
- \( \bullet\)
- Un ensemble, que l'on assimile à \( \B\) , avec au moins deux éléments distincts, notés \( 0\) et \( 1\) .
- \( \bullet\)
- Trois opérations :
- Une addition
- entre deux éléments \( a\) et \( b\) de \( \B\) notée \( a+b\) .
- Une multiplication
- entre deux éléments \( a\) et \( b\) de \( \B\) notée \( a\times b\) ou plus communément \( ab\) .
- La conjugaison
- d'un élément \( a\in\B\) noté \( \ab\) .
Ces données satisfont les axiomes de CADER :
- Commutativité :
- \( a+b=b+a\) et \( ab=ba\)
- Associativité :
- \( (a+b)+c=a+(b+c)\) et \( (ab)c=a(bc)\)
- Distributivité :
- \( a(b+c)=(ab)+(ac)\) et \( a+(bc)=(a+b)(a+c)\)
- Eléments neutre:
- \( a+0=0\) et \( a1=a\)
- Relation 0-1:
- \( a+\ab=1\) et \( a\ab=0\)
Nous avons vus aux chapitre précédent qu'étant donnée un référentiel \( \E\) fixé, \( \P(\E)\) muni de l'union, de l'intersection et du complémentaire est une algèbre de Boole où \( 0=\varnothing\) et \( 1=\E\) .
L'idée est à présent de vérifier que ces axiomes et uniquement ces axiomes permettent d'obtenir toutes les propriétés CANDIMATICA
De CADER à CANDIMATICA
Proposition [Idempotence]
Soient \( a\) un élément de \( \B\) une algèbre de Boole : \[a+a=a, \qquad aa=a\]
Démonstration
Nous ne pouvons utiliser que les axiomes donnés dans la définition d'une algèbre de Boole.
\begin{eqnarray*}
a
&\overset{E}{=}&a+0\\
&\overset{R}{=}&a+a\ab \\
&\overset{D}{=}&(a+a)(a+\ab) \\
&\overset{R}{=}&(a+a)1 \\
&\overset{E}{=}& a+a
\end{eqnarray*}
\begin{eqnarray*}
a
&\overset{E}{=}&a1\\
&\overset{R}{=}&a(a+\ab) \\
&\overset{D}{=}&(aa)+(a\ab) \\
&\overset{R}{=}&(aa)+0 \\
&\overset{E}{=}& aa
\end{eqnarray*}
Proposition [Absorption I]
Soient \( a\) un élément de \( \B\) une algèbre de Boole : \[a+1=1, \qquad a0=0\]
Démonstration
Nous ne pouvons utiliser que les axiomes donnés dans la définition d'une algèbre de Boole ainsi que la proposition d'idempotence.
\begin{eqnarray*}
a+1
&\overset{R}{=}&a+(a+\ab)\\
&\overset{A}{=}&(a+a)+\ab \\
&\overset{I}{=}&a+\ab \\
&\overset{R}{=}&1
\end{eqnarray*}
\begin{eqnarray*}
a0
&\overset{R}{=}&a(a\ab)\\
&\overset{A}{=}&(aa)\ab\\
&\overset{I}{=}&a\ab\\
&\overset{R}{=}&0
\end{eqnarray*}
Proposition [Absorption II]
Soient \( a\) et \( b\) des éléments de \( \B\) une algèbre de Boole : \[a+(ab)=a, \qquad a(a+b)=a\]
Démonstration
Nous ne pouvons utiliser que les axiomes donnés dans la définition d'une algèbre de Boole ainsi que les propositions d'idempotence et d'absoption I.
\begin{eqnarray*}
a+ab
&\overset{E}{=}&(a1)+(ab)\\
&\overset{D}{=}&a(1+b)\\
&\overset{A^I}{=}&a1\\
&\overset{E}{=}&a
\end{eqnarray*}
\begin{eqnarray*}
a(a+b)
&\overset{E}{=}&(a+0)(a+b)\\
&\overset{D}{=}&a+(0b)\\
&\overset{A^I}{=}&a+0\\
&\overset{E}{=}&a
\end{eqnarray*}
Unicité du conjugué
Il reste à montrer la propriété de Morgan et l'involution. La clef de la preuve de ces deux résultats est le résultat suivant.
Théorème [Unicité du conjugué]
Soient \( A\) et \( B\) des éléments d'une algèbre de Boole \( \B\) .
\[\Ab=B \quad \Longleftrightarrow\quad \Big(\quad A+B=1\quad \et \quad AB=0\quad\Big)\]
Démonstration
Le sens \( \Rightarrow\) est une reformulation de l'axiome des relations 0-1. Démontrons la réciproque. Nous disposons de deux hypothèses \( H_+ : A+B=1\) et \( H_\times : AB=0\) . Montrons qu'avec ces deux hypothèses, CADER, les absorptions et l'idempotence, \( \Ab=B\) .
\begin{eqnarray*}
\Ab
&\overset{E}{=}&\Ab+0\\
&\overset{H_\times}{=}&\Ab+AB\\
&\overset{D}{=}&(\Ab+A)(\Ab+B)\\
&\overset{R}{=}&1(\Ab+B)\\
&\overset{E}{=}&\Ab+B\\
&\overset{E}{=}&(\Ab1)+B\\
&\overset{H_+}{=}&(\Ab(A+B))+B\\
&\overset{D}{=}&(\Ab A)+(\Ab B)+B\\
&\overset{R}{=}&0+(\Ab B)+B\\
&\overset{E}{=}&(\Ab B)+B\\
&\overset{A^{II}}{=}&B\\
\end{eqnarray*}
Corollaire [Involution]
Soit \( a\) un élément de \( \B\) une algèbre de Boole : \[\overline{\ab}=a\]
Démonstration
On cherche à appliquer le théorème d'unicité du conjugué avec \( A=\ab\) et \( B=a\) . Sa conclusion est bien la propriété de l'involution : \( \Ab=B\) se traduit en effet \( \overline{\ab}=a\) . Il s'agit donc de démontrer que les hypothèses de ce théorème sont satisfaits. Précisément que \( \ab+a=1\) et \( \ab a=0\) ce qui n'est que la reformulation de l'axiome des relation 0-1 (avec la commutativité).
Corollaire [Morgan]
Soient \( a\) et \( b\) des éléments de \( \B\) une algèbre de Boole : \[\overline{a+b}=\ab\bb, \qquad \overline{ab}=\ab+\bb\]
Démonstration
La démonstration de ces deux égalités sont duales. Nous n'allons démontrer que \( \overline{a+b}=\ab\bb\) . Posons \( A=a+b\) et \( B=\ab\bb\) .
\begin{eqnarray*}
A+B
&\overset{ }{=}&a+b+(\ab\bb)\\
&\overset{D}{=}&a+[(b+\ab)(b+\bb)]\\
&\overset{R}{=}&a+[(b+\ab)1]\\
&\overset{E}{=}&a+(b+\ab)\\
&\overset{A+C}{=}&b+(a+\ab)\\
&\overset{R}{=}&b+1\\
&\overset{A^I}{=}&1
\end{eqnarray*}
\begin{eqnarray*}
AB
&\overset{ }{=}&(a+b)(\ab\bb)\\
&\overset{D}{=}&(a(\ab\bb))+(b(\ab\bb))\\
&\overset{A+C}{=}&((a\ab)\bb)+(\ab(b\bb))\\
&\overset{R}{=}&(0\bb)+(\ab 0)\\
&\overset{A^I}{=}&0+0\\
&\overset{E}{=}&0
\end{eqnarray*}
Nous avons donc démontrer que \( A+B=1\) et \( AB=0\) . D'après le théorème d'unicité du conjugué, \( \Ab=B\) soit \( \overline{a+b}=\ab\bb\) .
En conclusion uniquement à partir de CADER, nous arrivons à retrouver toutes les propriétés CANDIMATICA.
Corollaire
Soit \( \B\) une algèbre de boole alors \( \overline{0}=1\) .
Bien que cet énoncé semble évident, il n'est ni démontré pour le moment, ni utilisé.
Démonstration
On a \( 0+1=1\) (soit par la neutralité de \( 0\) , soit par l'absorption I) et \( 01=0\) (soit par la neutralité du \( 1\) , soit par l'absorption I). D'après le théorème d'unicité du conjugué, \( \overline{0}=1\) .
Un autre exemple
Soit \( D\) l'ensemble des diviseurs positif de \( 6\) . Sans plus de cérémonie on a \( D=\{1, 2, 3, 6\}\) . On définit sur \( D\) les trois opérations suivantes :
- \( \bullet\)
- Pour \( a\) et \( b\) dans \( D\) on pose \( a\times_Db=PGCD(a, b)\) .
- \( \bullet\)
- Pour \( a\) et \( b\) dans \( D\) on pose \( a+_Db=PPCM(a, b)\) .
- \( \bullet\)
- Pour \( a\) dans \( D\) on pose \( \ab=\dfrac{6}{a}\) .
Les règles de calcul arithmétiques donnes les tables de calculs suivantes.
\[
\begin{array}{r|*{4}{|c}}
+_D&1&2&3&6\\\hline\hline
1&1&2&3&\fbox{6}\\\hline
2&2&2&\fbox{6}&6\\\hline
3&3&\fbox{6}&3&6\\\hline
6&\fbox{6}&6&6&6
\end{array}
\]
\[
\begin{array}{r|*{4}{|c}}
\times_D&1&2&3&6\\\hline\hline
1&1&1&1&\fbox{1}\\\hline
2&1&2&\fbox{1}&2\\\hline
3&1&\fbox{1}&3&3\\\hline
6&\fbox{1}&2&3&6
\end{array}
\]
\[
\begin{array}{r||c}
a&\ab\\\hline\hline
1&6\\\hline
2&3\\\hline
3&2\\\hline
6&1
\end{array}
\]
En observant ces tableaux on aperçoit très facilement (par symétrie) que \( a+_Db=b+_Da\) et \( a\times_Db=b\times_Da\) . De même, par des résultats bien connus de l'arithmétique, l'associativité et la distributivité sont vérifiées. Il reste à vérifier l'axiome des éléments neutres et des relations 0-1 pour montrer que cet ensemble et ces opérations définissent bien une algèbre de Boole.
On observe que la table d'addition que \( a+_D1=a\) de sorte que \( 1\) semble être le bon candidat pour \( 0_D\) . De la même manière, puisque \( a\times_D6=a\) , \( 1_D=6\) . Il suffit alors de vérifier que ces éléments neutres vérifient les relations 0-1. Cela se fait au cas par cas et est trivialement observé (partie encadrée dans les tableaux).
