\( %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Mes commandes %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\multirows}[3]{\multirow{#1}{#2}{$#3$}}%pour rester en mode math \renewcommand{\arraystretch}{1.3}%pour augmenter la taille des case \newcommand{\point}[1]{\marginnote{\small\vspace*{-1em} #1}}%pour indiquer les points ou le temps \newcommand{\dpl}[1]{\displaystyle{#1}}%megamode \newcommand{\A}{\mathscr{A}} \newcommand{\LN}{\mathscr{N}} \newcommand{\LL}{\mathscr{L}} \newcommand{\K}{\mathbb{K}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\M}{\mathcal{M}} \newcommand{\D}{\mathbb{D}} \newcommand{\E}{\mathcal{E}} \renewcommand{\P}{\mathcal{P}} \newcommand{\G}{\mathcal{G}} \newcommand{\Kk}{\mathcal{K}} \newcommand{\Cc}{\mathcal{C}} \newcommand{\Zz}{\mathcal{Z}} \newcommand{\Ss}{\mathcal{S}} \newcommand{\B}{\mathbb{B}} \newcommand{\inde}{\bot\!\!\!\bot} \newcommand{\Proba}{\mathbb{P}} \newcommand{\Esp}[1]{\dpl{\mathbb{E}\left(#1\right)}} \newcommand{\Var}[1]{\dpl{\mathbb{V}\left(#1\right)}} \newcommand{\Cov}[1]{\dpl{Cov\left(#1\right)}} \newcommand{\base}{\mathcal{B}} \newcommand{\Som}{\textbf{Som}} \newcommand{\Chain}{\textbf{Chain}} \newcommand{\Ar}{\textbf{Ar}} \newcommand{\Arc}{\textbf{Arc}} \newcommand{\Min}{\text{Min}} \newcommand{\Max}{\text{Max}} \newcommand{\Ker}{\text{Ker}} \renewcommand{\Im}{\text{Im}} \newcommand{\Sup}{\text{Sup}} \newcommand{\Inf}{\text{Inf}} \renewcommand{\det}{\texttt{det}} \newcommand{\GL}{\text{GL}} \newcommand{\crossmark}{\text{\ding{55}}} \renewcommand{\checkmark}{\text{\ding{51}}} \newcommand{\Card}{\sharp} \newcommand{\Surligne}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\SurligneMM}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\norm}[1]{\left\lVert#1\right\rVert} \renewcommand{\lim}[1]{\underset{#1}{lim}\,} \newcommand{\nonor}[1]{\left|#1\right|} \newcommand{\Un}{1\!\!1} \newcommand{\sepon}{\setlength{\columnseprule}{0.5pt}} \newcommand{\sepoff}{\setlength{\columnseprule}{0pt}} \newcommand{\flux}{Flux} \newcommand{\Cpp}{\texttt{C++\ }} \newcommand{\Python}{\texttt{Python\ }} %\newcommand{\comb}[2]{\begin{pmatrix} #1\\ #2\end{pmatrix}} \newcommand{\comb}[2]{C_{#1}^{#2}} \newcommand{\arrang}[2]{A_{#1}^{#2}} \newcommand{\supp}[1]{Supp\left(#1\right)} \newcommand{\BB}{\mathcal{B}} \newcommand{\arc}[1]{\overset{\rotatebox{90}{)}}{#1}} \newcommand{\modpi}{\equiv_{2\pi}} \renewcommand{\Re}{Re} \renewcommand{\Im}{Im} \renewcommand{\bar}[1]{\overline{#1}} \newcommand{\mat}{\mathcal{M}} \newcommand{\und}[1]{{\mathbf{\color{red}\underline{#1}}}} \newcommand{\rdots}{\text{\reflectbox{$\ddots$}}} \newcommand{\Compa}{Compa} \newcommand{\dint}{\dpl{\int}} \newcommand{\intEFF}[2]{\left[\!\left[#1 ; #2\right]\!\right]} \newcommand{\intEFO}[2]{\left[\!\left[#1 ; #2\right[\!\right[} \newcommand{\intEOF}[2]{\left]\!\left]#1 ; #2\right]\!\right]} \newcommand{\intEOO}[2]{\left]\!\left]#1 ; #2\right[\!\right[} \newcommand{\ou}{\vee} \newcommand{\et}{\wedge} \newcommand{\non}{\neg} \newcommand{\implique}{\Rightarrow} \newcommand{\equivalent}{\Leftrightarrow} \newcommand{\Ab}{\overline{A}} \newcommand{\Bb}{\overline{B}} \newcommand{\Cb}{\overline{C}} \newcommand{\Cl}{\texttt{Cl}} \newcommand{\ab}{\overline{a}} \newcommand{\bb}{\overline{b}} \newcommand{\cb}{\overline{c}} \newcommand{\Rel}{\mathcal{R}} \newcommand{\superepsilon}{\text{\Large$\varepsilon\!\!\varepsilon$}} \newcommand{\supere}{\text{\Large$e\!\!e$}} \makeatletter \newenvironment{console}{\noindent\color{white}\begin{lrbox}{\@tempboxa}\begin{minipage}{\columnwidth} \ttfamily \bfseries\vspace*{0.5cm}} {\vspace*{0.5cm}\end{minipage}\end{lrbox}\colorbox{black}{\usebox{\@tempboxa}} } \makeatother \def\ie{\textit{i.e. }} \def\cf{\textit{c.f. }} \def\vide{ { $ {\text{ }} $ } } %Commande pour les vecteurs \newcommand{\vv}{\overrightarrow{v}} \newcommand{\vu}{\overrightarrow{u}} \newcommand{\vup}{\overrightarrow{u'}} \newcommand{\vx}{\overrightarrow{x}} \newcommand{\vy}{\overrightarrow{y}} \newcommand{\vz}{\overrightarrow{z}} \newcommand{\vt}{\overrightarrow{t}} \newcommand{\va}{\overrightarrow{a}} \newcommand{\vb}{\overrightarrow{b}} \newcommand{\vc}{\overrightarrow{c}} \newcommand{\vd}{\overrightarrow{d}} \newcommand{\ve}[1]{\overrightarrow{e_{#1}}} \newcommand{\vf}[1]{\overrightarrow{f_{#1}}} \newcommand{\vn}{\overrightarrow{0}} \newcommand{\Mat}{Mat} \newcommand{\Pass}{Pass} \newcommand{\mkF}{\mathfrak{F}} \renewcommand{\sp}{Sp} \newcommand{\Co}{Co} \newcommand{\vect}[1]{\dpl{\left\langle #1\right\rangle}} \newcommand{\trans}[1]{{\vphantom{#1}}^{t}{#1}} \SelectTips{cm}{12}%Change le bout des flèches dans un xymatrix \newcommand{\pourDES}[8]{ \begin{itemize} \item Pour la ligne : le premier et dernier caractère forment $#1#2$ soit $#4$ en base 10. \item Pour la colonne : les autres caractères du bloc forment $#3$ soit $#5$ en base 10. \item A l'intersection de la ligne $#4+1$ et de la colonne $#5+1$ de $S_{#8}$ se trouve l'entier $#6$ qui, codé sur $4$ bits, est \textbf{\texttt{$#7$}}. \end{itemize} } \)

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).