modif algo euclide

[cours-maths-dis.git] / logique / AlgBoole2.tex

% \setcounter{Exo}{0}
% \setcounter{Def}{0}
% \setcounter{Th}{0}
% \setcounter{Rem}{0}
% \setcounter{Notation}{0}
% \setcounter{Ex}{0}

% AG : ne pas mettre le titre de chapitre ici, mais dans main.tex svp.

%\chapter{Algèbre de Boole}

\section{Propriétés générales}


%\subsection{Définition}
\begin{Def}[Algèbre de Boole] On appelle \emph{algèbre de
Boole}\index{algèbre de Boole} la structure algébrique 
$(\mathcal{A},+,.,\overline{\mathstrut\enskip})$
définie par un
ensemble (non vide) $\mathcal{A}$ et trois opérations  :
\begin{itemize}
 \item la somme booléenne (binaire) : ``+'',
 \item le produit booléen (binaire) : ``.'' et 
 \item la négation booléenne (unaire) : ``{$\overline{\mathstrut\enskip}$}'' 
(par exemple $\overline{a}$).
\end{itemize}
et qui doivent posséder les propriétés données dans les deux premières 
colonnes du tableau ci-dessous.
\end{Def}

% AG : parmi ces propriétés, certaines découlent des autres.
% Lesquelles ? Quelle sont les axiomatisations minimales le splus
% intéressantes ?
%
% CG : Je pense que pour nos étudiants, il vaut mieux tout détailler,
% au risque de se répéter. Ce qui n'empêche pas que l'on peut évoquer,
% à l'oral, la redondance.



% CG : Je n'arrive pas à mettre la table sur la même page que la 
% définition d'une algèbre de boole. J'ai donc supprimé le Table,
% et réduit la taille des caractères. Je pense que c'est préférable
% de tout avoir sur une même page.

\begin{small}
$$
\begin{array}{|c|c|c|}
\hline
\hbox{Propriété}        & {\cal A}          & {\cal P}(E)         \\ \hline
\hbox{idempotence}      & a+a=a             & A\union A=A         \\
                        & a\cdot a=a        & A\inter A=A         \\ \hline
\hbox{commutativité}    & a+b=b+a           & A\union B=B\union A \\
                        & a\cdot b=b\cdot a & A\inter B=B\inter A \\ \hline
\hbox{associativité}    & a+(b+c)=(a+b)+c   & A\union(B\union C)=(A\union B)\union C \\ 
                        & a\cdot(b\cdot 
                      c)=(a\cdot b)\cdot c& A\inter(B\inter C)=(A\inter B)\inter C \\ \hline
\hbox{éléments neutres} & a+0=a             & A\union\void=A      \\
                        & a\cdot 1=a        & A\inter E=A         \\ \hline
\hbox{absorption}       & a+1=1             & A\union E=E         \\
                        & a\cdot 0=0        & A\inter\void=\void  \\ \hline
\hbox{distributivités}  & a\cdot(b+c)=a\cdot b+a\cdot c 
                                            & A\inter (B\union C)=(A\inter B)\union(A\inter C) \\
                        & a+b\cdot c=(a+b)\cdot(a+c)
                                            & A\union(B\inter C)=(A\union B)\inter(A\union C)  \\ \hline
\hbox{involution}       & \sur{\sur a}=a    & E\moins(E\moins A)=A \\ \hline
\hbox{complémentation}  & \sur 0=1          & E\moins\void=E \\
                        & \sur 1=0          & E\moins E=\void \\ \hline
\hbox{partition}        & a+\sur a=1        & A\union(E\moins A)=E \\
                        & a\cdot \sur a=0   & A\inter (E\moins A)=\void \\ \hline
\hbox{\og Lois de De Morgan\fg{}} 
                        & \sur{a+b}=\sur a\cdot\sur b 
                                            & E\moins(A\union B)=(E\moins A)\inter(E\moins B) \\
                        & \sur{a\cdot b}=\sur a+\sur b 
                                            & E\moins(A\inter B)=(E\moins A)\union(E\moins B)\\\hline
\end{array}
$$
\end{small}
\begin{center}Propriétés d'une algèbre de Boole\end{center}

\newpage
Le tableau précédent met en parallèle les mêmes
propriétés, écrites en utilisant
\begin{itemize}
 \item soit les notations générales d'une algèbre de Boole,
\item soit les notations ensemblistes, définies lorsque
$\mathcal{A}$ est l'ensemble $\mathcal{P}(E)$ des parties d'un
ensemble $E$ : c'est une algèbre de Boole particulière, bien connue,
 et qui possède des notations spécifiques.
\end{itemize}



\begin{Rem}
 Les signes opératoires utilisés sont les mêmes que ceux de l'addition et de la multiplication des réels. Cependant, ces opérations n'ont évidemment pas les mêmes propriétés, et ne portent pas sur les mêmes éléments.
\end{Rem}




\begin{Exo}[Somme disjonctive]
On considère une algèbre de Boole quelconque $(E,+,\cdot ,
\overline{\mathstrut\enskip})$.

On définit l'opération \og somme disjonctive\fg{}, notée $\oplus$, par $a \oplus b = \overline{a} b+a \overline{b}$.


\begin{enumerate}
\item Que vaut $a \oplus 0$ ? $a \oplus 1$ ?
\item Calculez $a \oplus a$ et $a \oplus \overline{a}$.
\item Calculez $\overline{a \oplus b}$.
\item Montrez que $\oplus$ est associative et commutative.
%\item Comparer cette opération à la différence symétrique de la théorie des ensembles, au ou exclusif (XOR), et à l'addition modulo 2.
\end{enumerate}
\end{Exo}




\begin{Exo}[Opérateurs de Sheffer et de Peirce]
Soit $(E,+, \cdot , \overline{\mathstrut\enskip})$ une algèbre de Boole.
\begin{enumerate}
\item On définit l'opération de Sheffer\footnote{D'après le logicien H.M. Sheffer} par : $a | b= \overline{a}+
\overline{b}$.% (c'est le NAND des informaticiens).

Comment obtenir $\overline{a}$, $a+b$, $a \cdot b$ en n'utilisant que l'opérateur $|$ ? Faire de même pour $a+ \overline{b}$; étudier l'associativité de cette opération.

\item On définit la flèche de Peirce\footnote{Lorsque les logiciens,
dans les années 1930, cherchèrent un symbole pour exprimer le
connecteur découvert par C.S. Peirce (1839-1914), ``Pierce Arrow'' était
le nom d'une célèbre marque de voiture !} par: $a \downarrow b =
\overline{a} \cdot \overline{b}$.% (c'est le NOR). 
Mêmes questions. \end{enumerate} 
\end{Exo}


\begin{Rem}
Ces connecteurs sont donc remarquables, puisqu'ils sont universels (tous les autres connecteurs peuvent s'exprimer avec uniquement la barre de Scheffer, ou uniquement avec la flèche de Peirce).
Cependant, par manque de concision et de lisibilité, ces connecteurs ne sont pas utilisés en logique.
\end{Rem}

% AG : ``signe opératoire'', ``connecteur'', ``opérateur'',
% ``opérations''
% sont-ils synonymes ? dans quelle mesure ? lesquels sont à
% privilégier ?
%
% CG : Pour moi, oui. Je ne suis pas sûr qu'il faille en 
% privilégier un en particulier : autant habituer les étudiants
% à utiliser les différents vocabulaires qui existent (?)


\section{Règles de calcul dans une algèbre de Boole}


\begin{enumerate}
 \item Les priorités habituelles sont respectées pour la somme et le produit booléen.
 % AG : Mieux vaudrait rappeler ces règles ici.
\item Les éléments neutres sont notés 0 et 1, par analogie avec les
entiers de même symbole (ne pas oublier que ces calculs ne se déroulent pas dans $\R$...)
\item L'absence d'éléments symétriques pour la somme et pour le produit interdit les simplifications que l'on a l'habitude de pratiquer \og  sans y réfléchir\fg{} :
\begin{itemize}
 \item $a+b=a+c$ ne donne pas $b=c$,
 \item $ab=ac$ n'entraîne pas $b=c$.
\end{itemize}
En particulier, ne jamais perdre de vue que
\begin{itemize}
\item $a+b=0$ n'est réalisable en algèbre de Boole que si $a=b=0$
\item $a.b=1$ n'est réalisable en algèbre de Boole que si $a=b=1$ ($A \cap B = E \Leftrightarrow A=E \textrm{ et } B = E$)
\item $a.b=0$ peut être réalisé avec $a\neq 0$ et $b\neq 0$ (par exemple, avec $b=\sur a$, mais ce n'est pas la seule solution...). On parle de \og  diviseurs de zéro\fg{}. (Ainsi, $A \cap B = \varnothing$ est possible sans avoir obligatoirement $A = \varnothing$ et $B = \varnothing$). 
\end{itemize}
\item Il y a deux distributivités. Celle de la somme (booléenne) sur le produit (booléen) n'est pas habituelle. Par exemple, simplifier $(a+b)(a+c)(a+d)(a+e)(a+f)$
\item Signalons pour finir que, comme ci-dessus, le point pour le produit est souvent omis. 
\end{enumerate}










Dans une expression booléenne, une sous-expression est dite \og redondante\fg{} lorsqu'on peut la supprimer sans changer la \og valeur\fg{} de l'expression :
\begin{enumerate}
\item Dans une somme booléenne, tout terme absorbe ses multiples.

Autrement dit : $a+a\cdot b=a$.

\begin{Proof}
 En effet, $a+a\cdot b=a\cdot(\sur b+b)+a\cdot b=a\cdot\sur b+a\cdot b+a\cdot b=a\cdot\sur b+a\cdot b\ \hbox{ (par idempotence)}=a\cdot(\sur
b+b)=a$.
\end{Proof}

\item Dans un produit booléen, tout facteur absorbe tout autre facteur qui le contient en tant que terme.

Autrement dit : $a\cdot(a+b)=a$.

\begin{Proof}
En effet, $a\cdot(a+b)=a\cdot a+a\cdot b=a+a\cdot b=a$.
\end{Proof}

\item Enfin, la troisième règle de redondance s'exprime par :
$$a+\sur a\cdot b=a+b$$

\begin{Proof}
$a+\sur a\cdot b=(a+\sur a)\cdot(a+b)=1\cdot(a+b)=a+b$.
\end{Proof}

\begin{Ex}
 $ab + \sur a c + \sur b c = a b +(\sur a + \sur b )\cdot c = ab + \sur {ab} \cdot c = ab+c$
\end{Ex}

\end{enumerate}


 \begin{Exo}
% L'application de cette troisième règle peut être combinée avec celle des autres, comme par exemple dans le calcul suivant :
Montrer que $a\cdot b+\sur a\cdot c+b.c=a\cdot b+\sur a\cdot c$
\end{Exo}

% \begin{Proof}
% $a\cdot b+\sur a\cdot c+b\cdot c=a\cdot b+\sur a\cdot
% c+(a+\sur a)\cdot b\cdot c=a\cdot b+\sur a\cdot c+a\cdot b\cdot
% c+\sur a\cdot b\cdot c$; $a\cdot b$ absorbe $a\cdot b\cdot c$ et
% $\sur a\cdot c$ absorbe $\sur a\cdot b\cdot c$, d'où le
% résultat.
% \end{Proof}

\begin{Exo}[Somme disjonctive]
Montrez que l'on a $a = b$ si et seulement si $a \oplus b = 0$.
\end{Exo}



\begin{Exo}[Calcul booléen élémentaire]
% AG : Que veut dire ``effectuer les calculs ? Est-ce en terme de
% règles appliquées au maximum de gauche à droite, en terme de forme
% normale atteinte ?
Appliquer au maximum les règles précédentes pour supprimer les redondances 
dans les calculs suivants.
\begin{enumerate}
%\item $(a+b) \cdot (b+c) \cdot (c+a)$
%\item $(a+b) \cdot (a+c)+(b+c) \cdot (a+b)+(a+c) \cdot (b+c)$
\item $(a+b+c) \cdot (a+\overline{b}+c) \cdot (a+\overline{b}+\overline{c})$
\item $a+\overline{a} \cdot b \cdot c+\overline{a}+a \cdot b$
\item $a \cdot b+\overline{a} \cdot b \cdot c+a \cdot \overline{b} \cdot c$
%\item $a \cdot \overline{b}+a \cdot b \cdot c+a \cdot \overline{b} \cdot c \cdot d$
\item $(a+b+c) \cdot (\overline{a}+\overline{b}+\overline{c}+d)$
\end{enumerate}
\end{Exo}


\begin{Exo}[Calcul booléen]
Même énoncé qu'à l'exercice précédent.
%Simplifier les expressions suivantes.
\begin{enumerate}
 \item $(\sur a+b)(\sur c+\sur a\cdot\sur b+a\cdot b)\ $.
 \item $(a+\sur b+\sur c)\cdot(\sur a+b)\cdot(\sur b+c)$.
% \item $(a+\sur b+c+b\cdot\sur d)\cdot(\sur b+c)$.
% \item $\sur{\sur a+\sur b+c}+\sur{\sur a+b}+\sur a+c$.
% \item $(a+\sur b+c)\cdot(\sur{a+b}+c+d)+\sur{a+\sur b+d}\cdot\sur{\sur{a+b}+a+d}$.
% \item $\sur{[(\sur a+c)+(\sur b+d)]\cdot(\sur c+\sur d)}+\sur a+\sur b\ $.
% \item $a\cdot(\sur b+c)\cdot(\sur{a\cdot b}+a\cdot c)+\sur{a\cdot(\sur
% b+c)}\cdot\sur{\sur{a\cdot b}+a\cdot c}$.
% \item $(\sur{a\cdot b\cdot c+a\cdot b\cdot d})\cdot(\sur{\sur a+\sur
% b+\sur{c+d}})+a\cdot b\cdot(c+d)\cdot(\sur a+\sur b+\sur{c+d})\ $.
% \item $\sur{\sur a\cdot\sur b+a\cdot b}+\sur b\cdot\sur c+b\cdot c$.
%  \item $\sur{\sur a+b+\sur{\sur a\cdot b}}+\sur{a\cdot\sur b}+c$.
% \item $\sur{\sur{a\cdot\sur b}+\sur c+d}\cdot(\sur{a\cdot c}+b+d)+(\sur{a\cdot\sur b}+\sur
% c+d)\cdot\sur{\sur{a\cdot c}+b+d}$.
\item $(a+c)\cdot(\sur a+d)\cdot(\sur b+\sur e)\cdot(\sur b\cdot\sur
c+b\cdot c)\cdot(\sur d+c\cdot e)\cdot(\sur c+d)$.
\item $(\sur a\cdot\sur{a\cdot(\sur b+\sur c)}+a\cdot(\sur b+\sur
c))\cdot(\sur b\cdot\sur{\sur a+c}+(\sur a+c)\cdot b)\cdot(a\cdot\sur
b\cdot c+\sur{a\cdot\sur b}\cdot\sur c)$.
\end{enumerate}
\end{Exo}



\section{Fonctions booléennes}


\subsection{Définitions}


Soit $\mathcal{A}$ une algèbre de Boole.


\begin{Def}[Fonction booléenne]
On appelle \emph{fonction booléenne de $n$ variables} \index{fonction!booléenne} toute application de $\mathcal{A}^n$ dans $\mathcal{A}$ dont l'expression ne contient que :
\begin{itemize}
 \item les symboles des opérations booléennes,
\item des symboles de variables, de constantes,
\item d'éventuelles parenthèses.
\end{itemize}
\end{Def}






\begin{Ex}
$f(a,b,c)=a\cdot\sur b+c$.
\end{Ex}


\begin{Rem}
Si $a$ est une variable booléenne, elle peut intervenir dans l'expression d'une fonction booléenne sous la forme $a$ ou sous la forme $\sur a$, qui sont appelées les deux \emph{aspects} de cette variable : affirmé et nié.
\end{Rem}


\begin{Def}[Fonction booléenne nulle]
On appelle \emph{fonction booléenne nulle} \index{fonction!booléenne!nulle} (à $n$ variables) la fonction booléenne qui, à chaque valeur des variables, associe la valeur 0.

Son expression est $f(x_1,x_2,\ldots,x_n)=0$.
\end{Def}


\begin{Def}[Fonction référentiel]
On appelle \emph{fonction référentiel}\index{fonction!référentiel} (à $n$ variables) la fonction booléenne qui, à chaque valeur des variables, associe la valeur 1.

Son expression est $f(x_1,x_2,\ldots,x_n)=1$.
\end{Def}


\subsection{Fonctions booléennes élémentaires}


\begin{Def}[Minterme, maxterme]
 Un \emph{minterme} à $n$ variables\index{minterme} est une fonction booléenne à $n$ variables dont l'expression se présente sous la forme du produit d'un aspect et d'un seul de chacune des $n$ variables.

Définition analogue pour un \emph{maxterme} \index{maxterme}, en remplaçant dans la définition précédente \og produit\fg{} par \og somme\fg{}.
\end{Def}

\begin{Def}[Fonctions booléennes élémentaires]
Pour un nombre de variables $n$ fixé, les \emph{fonctions booléennes élémentaires}\index{fonctions booléennes élémentaires} sont les mintermes et les maxtermes (à $n$ variables).
\end{Def}


\begin{Ex}[Minterme à trois variables]
$a\cdot\sur b\cdot c$ 
\end{Ex}

\begin{Ex}[Maxterme à trois variables]
$\sur a+b+\sur c$.
\end{Ex}

\begin{Exo}
Pour 3 variables $a$, $b$ et $c$, repérez les mintermes et les maxtermes : $b \sur c$, $a + \sur b + c$, $a \sur b b \sur c$, $\sur a b c$, $a + \sur b c$.
\end{Exo}

\begin{Exo}
Dressez la liste des mintermes et des maxtermes pour deux variables $a$ et $b$.
\end{Exo}


\begin{Th}[Nombre de mintermes et de maxtermes] Les mintermes et
maxtermes, pour un nombre donné $n$ de variables, sont au nombre de
$2^n$ chacun.
\end{Th}


\begin{Notation}[Représentation des mintermes et des maxtermes] Les
mintermes et les maxtermes sur $n$ variables sont respectivement notés
$m_i^{(n)}$ et $M_i^{(n)}$. L'indice $i$ varie entre 0 et $2^n-1$,
selon une convention d'ordre de numérotation des mintermes et
maxtermes.
\end{Notation}

La convention est la suivante : à chaque variable, on associe 0 ou 1
selon que cette variable apparaît sous son aspect nié ou sous son
aspect affirmé dans l'expression du minterme ou du maxterme. En
écrivant ces chiffres les uns à côté des autres, dans le même ordre que
les variables correspondantes, on obtient un code binaire du minterme
ou du maxterme, qu'on peut considérer comme l'écriture d'un entier
positif en base 2.


Pour que cette convention de numérotation ait un sens, il est
indispensable de fixer un ordre d'énumération des variables une fois
pour toutes, et de s'y tenir.
\begin{Ex}
Si les variables sont $a$, $b$, $c$ et $d$ et qu'on décide de les énumérer dans l'ordre alphabétique, il sera, par exemple, strictement
interdit d'écrire un produit sous la forme $c\cdot a\cdot d\cdot b$, et
ceci, même de manière transitoire au cours d'un calcul : la seule
expression admissible est alors $a\cdot b\cdot c\cdot d$. 
\end{Ex}


\begin{Def}[Indice d'un minterme ou d'un maxterme] L'\emph{indice d'un
minterme ou d'un maxterme}\index{indice!d'un minterme} 
est la valeur décimale du code binaire de ce minterme ou de ce maxterme.
\end{Def}




\begin{Ex}
Pour 3 variables $a$, $b$ et $c$ rangées par ordre
alphabétique :


\begin{center}\begin{tabular}{|c|c|c|c|}\hline
minterme (ou Maxterme) & code binaire associé & indice décimal & représentation\\ \hline
$\sur a\cdot b\cdot\sur c$ & 010 & 2 & $m_2$\\ \hline
$a\cdot\sur b\cdot\sur c$ & 100 & 4 & $m_4$ \\ \hline
$a+b+c$ & 111 & 7 & $M_7$\\ \hline
\end{tabular}\end{center}
\end{Ex}


\begin{Exo}
Pour 3 variables $a$, $b$ et $c$ rangées par ordre
alphabétique, trouvez l'indice des mintermes et maxtermes suivants : $\sur a + b + \sur c$, $\sur a + \sur b + c$, $a \cdot b \cdot c$ et $\sur a \cdot b \cdot c$.
\end{Exo}

\subsection{Correspondance entre maxtermes et mintermes}

\begin{Th}
 La négation (booléenne) d'un minterme est un maxterme (et
réciproquement).
\end{Th}

\begin{Proof}
 Lois de De Morgan : la négation échange les opérations booléennes binaires...
\end{Proof}


\begin{Ex}
$\sur{\sur a\cdot b\cdot\sur c}=a+\sur b+c$ 
\end{Ex}


Si l'indice du minterme (ou du maxterme) dont on prend
la négation est $i$ et si l'indice de cette négation est $j$, on a des expressions du type :


\centerline{\begin{tabular}{c c c}
$i$ & $=$ & $0011\,0100\,1110\,\ldots\ldots\,0110$ \\
$j$ & $=$ & $1100\,1011\,0001\,\ldots\ldots\,1001$ \\ \hline
$i+j$ & $=$ & $1111\,1111\,1111\,\ldots\ldots\,1111$
\end{tabular}}\psaut



L'expression en système binaire de la valeur de $i+j$ est donc, quelles que soient les valeurs de ces deux indices, 111.....1 ($n$ chiffres).
La valeur correspondante est $2^n-1$.
Autrement dit,

\begin{Th}
La négation d'un minterme est un maxterme, et réciproquement.

$$\qqs i\in\{0,...,2^n-1\}, \sur{m_i^{(n)}}=M_{2^n-1-i}^{(n)}\
{\rm et }\ \sur{M_i^{(n)}}=m_{2^n-1-i}^{(n)}.$$
\end{Th}




\subsection{Principaux résultats concernant mintermes et maxtermes}

\begin{Th}
Les mintermes à $n$ variables sont disjoints.

\begin{center}
Si $i\not =j$, alors $m_i^{(n)}\cdot m_j^{(n)}=0$.
\end{center}
\end{Th}

\begin{Exo}
Vérifiez la dernière propriété dans le cas de deux variables.
\end{Exo}



\begin{Proof}
Si $i\not =j$, les écritures en système binaire des entiers $i$ et $j$ comportent au moins un chiffre différent, en l'occurrence au moins un \og 1\fg{} à la place d'un \og 0\fg{}.

Il y a donc au moins une variable qui figure sous deux aspects différents.

Or, on sait que $a\cdot\sur a=0$. Donc, lorsque l'on calcule le produit des deux mintermes, celui-ci est nécessairement nul.
\end{Proof}


\begin{Rem}
On prend la négation de chacun des membres de l'égalité, et l'on obtient : si $i\not =j$, alors $M_i^{(n)}+M_j^{(n)}=1$. Ainsi, la somme de deux maxtermes distincts vaut 1. 
\end{Rem}


\begin{Th}
Les mintermes forment une partition de l'unité :

$$\ds\sum_{i=0}^{2^n-1}m_i^{(n)}=1$$
\end{Th}


\begin{Proof}
En effet, il y a un nombre pair de mintermes.

Dans cette somme, on les ordonne les mintermes par indice croissant, puis on les regroupe deux à deux. Dans chacun de ces groupes, seul diffère l'aspect de la dernière variable.
On met les autres en facteur de la somme $\sur x_n+x_n$, c'est-à-dire 1 : le facteur qui subsiste est un minterme à $(n-1)$ variables.

Donc  $\ds\sum_{i=0}^{2^n-1}
m_i^{(n)}=\sum_{i=0}^{2^{n-1}-1}m_i^{(n-1)}$.

Par récurrence, cette somme est égale à $\sur x_1+x_1$, c'est-à-dire finalement 1.
\end{Proof}

\begin{Exo}
Le vérifier dans le cas de deux variables.
\end{Exo}


\begin{Rem}
Par négation (booléenne) de cette propriété, on obtient : \emph{le produit de tous les maxtermes à $n$ variables est nul}.
\end{Rem}

\subsection{Formes canoniques d'une fonction booléenne}
% AG : en licence, ceci est repris sous le nom de formes normales de
% formules propositionnelles, obtenues par réécriture.
% Redondant, mais c'est bien d'avoir vu la méthode des diagrammes de
% Karnaugh et la méthode des consensus.
% Ma première lecture s'arrête ici.

%\subsubsection{Définition et théorème}
% AG : Pas assez précis. Un monôme est un produit de variables
% affirmées ou niées.

\begin{Def}[Monômes]
Un \emph{monôme}\index{monôme} est une fonction booléenne dans l'expression de laquelle n'interviennent que le produit et la négation booléennes.
\end{Def}

\begin{Exo}
Parmi les expressions suivantes dire lesquelles sont des monômes et lesquelles ne le sont pas en justifiant:
$a + b$,
$a+bc$, 
$a(b+c)$,
$a\sur{b}$,
$b$.
\end{Exo}

\begin{Th}
Quelle que soit l'expression de la fonction booléenne, il est possible de la mettre sous la forme d'une somme de monômes. 
\end{Th}

\begin{Proof}
En effet, comme elle ne fait intervenir que les trois opérations booléennes, il suffit de lui appliquer les règles du calcul booléen:
\begin{enumerate}
\item On développe les négations (en appliquant les règles $\sur{a+b}=\sur a\cdot\sur b$ et $\sur{a\cdot b}=\sur a+\sur b$), jusqu'à ce qu'il n'y ait plus de négations que sur les variables;

\item Puis on développe les produits qui portent sur des sommes, en utilisant la distributivité du produit sur la somme;

\item On obtient ainsi une expression qui s'écrit sans parenthèses, et qui ne contient que des sommes de produits de variables éventuellement niées.
\end{enumerate}

\end{Proof}


\begin{Th}
Chaque monôme peut ensuite être mis sous la forme d'une somme de mintermes.
\end{Th}


\begin{Proof}
En effet, si, dans l'expression de ce monôme, toutes les variables interviennent, c'est déjà un minterme.

Dans le cas contraire, il manque (par exemple) la variable $a$ dans son expression : on la fait intervenir sous la forme $(\sur a+a)$. On développe, les deux monômes obtenus font intervenir la variable $a$.

Ou bien, il s'agit de mintermes et le processus est terminé, ou bien il manque encore une variable, qu'on fait intervenir en utilisant le même procédé, et ainsi de suite jusqu'à aboutir aux mintermes.
\end{Proof}


On fait évidemment disparaître du résultat, par idempotence, les occurrences multiples de mintermes, pour pouvoir énoncer le résultat suivant :

\begin{Th}[Forme canonique disjonctive]
Toute fonction booléenne à $n$ variables (autre que la fonction nulle) peut se mettre sous la forme d'une somme de mintermes à $n$ variables.

Cette forme, unique, s'appelle \emph{Forme Canonique Disjonctive}\index{forme canonique!disjonctive} (dans la suite, FCD).
\end{Th}

 
\begin{Rem}
L'unicité de cette FCD permet la comparaison des fonctions booléennes entre elles.
\end{Rem}


Par négation booléenne de ce résultat, on obtient :


\begin{Th}[Forme canonique conjonctive]
Toute fonction booléenne de $n$ variables (autre que la fonction référentiel) peut se mettre sous la forme d'un produit de maxtermes à $n$ variables.

Cette forme, unique, est la \emph{Forme Canonique Conjonctive}\index{forme canonique!conjonctive} (FCC dans la suite). 
\end{Th}


\subsubsection{Obtention des formes canoniques}

La méthode algébrique consiste à :

\begin{itemize}
 \item tout développer pour mettre l'expression sous la forme d'une somme 
   de monômes,
\item dans chaque terme de cette somme, faire apparaître les valeurs qui n'y figurent pas.
\end{itemize}

\begin{Ex}
On illustre cela :

\noindent $f(a,b,c) = a+bc = a(\sur b + b) (\sur c + c) + (\sur a + a)bc$

\noindent $ = a \sur b \sur c + a \sur b c + ab \sur c + abc + \sur a bc +abc = m_3 + m_4 + m_5 + m_6 + m_7.$
\end{Ex}


Pour la FCC, on peut imaginer une méthode analogue.

\begin{Ex}
$f(a,b,c) = a+bc = (a+b)(a+c) = (a+b+ \sur c c) (a + \sur b b +c)$

$ = (a+b + \sur c ) \cdot (a+b+c) \cdot (a + \sur b +c) \cdot (a+b+c) = M_5 M_6 M_7$
\end{Ex}


\begin{Rem}
Si on prend la négation de la FCD, on obtient bien sûr une FCC... mais pas celle de la fonction, celle de sa négation !

Il suffit de prendre la négation de la fonction, de
calculer sa FCD puis de prendre la négation du résultat.
\end{Rem}


\begin{Exo}
Obtenir la FCC de $x + \overline{y}z$.
\end{Exo}


Il existe une autre méthode pour obtenir ces formes canoniques : la méthode des diagrammes.





\section{Diagrammes de Karnaugh}


La représentation des fonctions booléennes par diagrammes de Karnaugh-Veitch :
% \begin{itemize}
%  \item
est fondée sur les propriétés des mintermes (ils réalisent une partition de l'unité),
% \item et est copiée de la représentation des ensembles par diagrammes d'Euler-Venn (les fameuses \og patates\fg{}).
%\end{itemize}


Ces derniers diagrammes deviennent rapidement inextricables quand le nombre de variables augmente, c'est pourquoi, dans les diagrammes de Karnaugh, on divise systématiquement l'\og univers\fg{} (le référentiel $E$) en deux parties égales en superficie pour représenter la partie concernée et son complémentaire.


À chaque introduction de variable supplémentaire, chaque case du précédent diagramme est divisée en 2.



\begin{Ex}

On obtient, par exemple :

\begin{center}
\begin{tabular}{|c|c|c|}
\hline 
  & $\sur a$ & $a$\\
\hline
$\sur b$ & $\sur a \sur b$ & $a \sur b$ \\
\hline
$b$ & $\sur a b$ & $ab$\\
\hline
\end{tabular}
\end{center}


\noindent Pour obtenir un diagramme de Karnaugh, on place dans ce diagramme les numéros des mintermes :

\begin{center}
\begin{tabular}{|c|c|c|}
\hline 
\backslashbox{b}{a}  & 0 & 1\\
\hline
0 & 0 & 2 \\
\hline
1 & 1 & 3\\
\hline
\end{tabular}
\end{center}
\end{Ex}



\begin{Ex}
Cas de trois variables :
\begin{itemize}
 \item les deux premières colonnes correspondent à $\sur a$, les deux dernières à $a$,
\item la première et la dernière colonne correspondent à $\sur b$, les deux centrales à $b$,
\item enfin, la première ligne est associée à $\sur c$, la deuxième à $c$.
\end{itemize}

\noindent ...ce qui donne 

\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline 
\backslashbox{c}{ab}  & 00 & 01 & 11 & 10 \\
\hline
0 & 0 & 2 & 6 & 4 \\
\hline
1 & 1 & 3 & 7 & 5\\
\hline
\end{tabular}
\end{center}
\end{Ex}



\begin{Ex}
Cas de quatre variables :

\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline 
\backslashbox{cd}{ab}  & 00 & 01 & 11 & 10 \\
\hline
00 & 0 & 4 & 12 & 8 \\
\hline
01 & 1 & 5 & 13 & 9\\
\hline
11 & 3 & 7 & 15 & 11\\
\hline
10 & 2 & 6 & 14 & 10\\
\hline
\end{tabular}
\end{center}
\end{Ex}



Dans un tel diagramme, chaque case représente un minterme. Les autres monômes regroupent un nombre de cases qui est une puissance de 2, selon le nombre de variables présentes.




\begin{Exo}
Faire un diagramme à cinq variables.
\end{Exo}

\noindent Réponse :


\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline 
\backslashbox{de}{abc}  & 000 & 001 & 011 & 010 & 110 & 111 & 101 & 100 \\
\hline
00 & 0 & 4 & 12 & 8 & 24 & 28 & 20 & 16 \\
\hline
01 & 1 & 5 & 13 & 9 & 25 & 29 & 21 & 17 \\
\hline
11 & 3 & 7 & 15 & 11 & 27 & 31 & 23 & 19 \\
\hline
10 & 2 & 6 & 14 & 10 & 26 & 30 & 22 & 18 \\
\hline
\end{tabular}
\end{center}

C'est-à-dire :
\begin{itemize}
 \item les quatre premières colonnes correspondent à $\sur a$, les quatre dernières à $a$,
\item les deux premières, et les deux dernières colonnes correspondent à $\sur b$, les quatre centrales à $b$,
\item les colonnes 1, 4, 5 et 8 à $\sur c$, les autres à $c$,
\item les deux premières lignes à $\sur d$, les deux dernières à $d$,
\item enfin, la première et la dernière ligne sont associées à $\sur e$, les deux centrales à $e$.
\end{itemize}



%\subsection{Utilisation}

Les diagrammes peuvent être utilisés en réunion, en intersection ou en complémentation.

Ils permettent :
\begin{itemize}
 \item d'obtenir la FCD d'une fonction booléenne plus aisément que par le calcul algébrique (utilisé pour découvrir la forme en question),
 \item une première approche du problème de la simplification des fonctions booléennes (dans des cas simples et pour un petit nombre de variables)...
\end{itemize}

\medskip

Utilisation des diagrammes de Karnaugh pour représenter les fonctions booléennes...

\begin{description}
\item[En réunion.] Soit par exemple $f(a,b,c) = a +\sur b c$. Son diagramme est :

\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline 
\backslashbox{c}{ab}  & 00 & 01 & 11 & 10 \\
\hline
0 & 0 & 2 & \colorbox{red}{6} & \colorbox{red}{4} \\
\hline
1 & \colorbox{red}{1} & 3 & \colorbox{red}{7} & \colorbox{red}{5}\\
\hline
\end{tabular}
\end{center}

On lit aisément la FCD de $f$ sur le diagramme : $f(a,b,c) = m_1 + m_4 + m_5 + m_6 + m_7$.

\item[En intersection.] Soit $f(a,b,c) = (a + \sur b ) (a+c)$.

On peint en rouge les  cases correspondant à $a + \sur b$, et on note en italique  les nombres correspondant à $a+c$ :

\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline 
\backslashbox{c}{ab}  & 00 & 01 & 11 & 10 \\
\hline
0 & \colorbox{red}{0} & 2 & \textit{{\colorbox{red}{6}}} & \textit{{\colorbox{red}{4}}} \\
\hline
1 & \textit{{\colorbox{red}{1}}} & \textit{{3}} & \textit{{\colorbox{red}{7}}} & \textit{{\colorbox{red}{5}}}\\
\hline
\end{tabular}
\end{center}

La représentation de $f$ est contenue dans les cases rouges possédant les nombres en italique. Comme  
$(a + \sur b ) (a+c) = a + \sur b c$, 
on retrouve la même FCD.

\item[En complémentation.] Soit $f(a,b,c) = a + \sur b c$, de diagramme :


\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline 
\backslashbox{c}{ab}  & 00 & 01 & 11 & 10 \\
\hline
0 & 0 & 2 & \colorbox{red}{6} & \colorbox{red}{4} \\
\hline
1 & \colorbox{red}{1} & 3 & \colorbox{red}{7} & \colorbox{red}{5}\\
\hline
\end{tabular}
\end{center}

Alors la négation de $a+ \sur b c$ est dans les cases pas rouge : la FCD de $\sur f$ est $m_0+m_2+m_3$.

\end{description}





\begin{Exo}[Fonctions booléennes]
Donner la forme canonique disjonctive de la fonction booléeene dont l'expression est
$$f(a,b,c,d,e)=\sur a\cdot[\sur b\cdot\sur e\cdot(c+d)+b\cdot(\sur c\cdot\sur
d\cdot\sur e+c\cdot\sur{d\cdot e})].$$
\end{Exo}



\begin{Exo}
Pour chacune des expressions suivantes...
%\newcommand{\overline}[1]{\ensuremath{\overline{#1}}} 
$$\begin{array}{lll}
E_1 & = & xyz + xy\overline{z} + \overline{x}y\overline{z} + \overline{x}\overline{y}z\\
E_2 & = & xyz + xy\overline{z} + x\overline{y}z + \overline{x}\overline{y}z\\
E_3 & = & xyz + xy\overline{z} + \overline{x}y\overline{z} + \overline{x}\overline{y}\overline{z} +
\overline{x}\overline{y}z \\
\end{array}$$
donner la forme minimale en exploitant les diagrammes de Karnaugh
\end{Exo}


\begin{Exo}[Application de la méthode de Karnaugh] % Lipschutz 12.18
Trouver une forme minimale de 
$E = x\sur{y} + xyz + \sur{x}\sur{y}\sur{z} + \sur{x}yz\sur{t}$.
\end{Exo}


\begin{Exo}[Composition de la méthode de Karnaugh] %Velu 12.11
On considère deux fonctions booléennes $u$ et $v$ des quatres variables $a$, $b$, $c$, $d$ définies par 
$u = (a+d)(b+c)$ et $v = (a+c)(\sur{b}+d)$.
\begin{enumerate}
\item Dessiner les diagrammes de Karnaugh de $u$ et de $v$.
\item En déduire le diagramme de Karnaugh de $w = uv+\sur{u}\sur{v}$.
\item Donner une forme minimale pour $w$
\end{enumerate}
\end{Exo}

\begin{Exo}[BTS-2009]
La société \textit{K-Gaz} décide de recruter en interne des collaborateurs 
pour sa filiale en Extrême-Orient.
Pour chaque employé, on définit les variables booléennes suivantes:
\begin{itemize}
\item $a$ = 1 s'il a plus de cinq ans d'ancienneté dans l'entreprise;
\item $b$ = 1 s'il possède un B.T.S. informatique de gestion (BTS-IG);
\item $c$ = 1 s'il parle couramment l'anglais.
\end{itemize}
La direction des ressources humaines décide que pourront postuler les employés :\begin{itemize}
\item qui satisfont aux trois conditions, 
\item ou qui ont moins de 5 ans d'ancienneté mais qui maîtrisent l'anglais,
\item ou qui ne maîtrisent pas l'anglais mais qui possèdent un BTS-IG.
\end{itemize}
\begin{enumerate}
\item  Écrire une expression booléenne $E$ traduisant les critères 
  de la direction.
\item  Représenter l'expression $E$ par un tableau de Karnaugh.
\item  À l'aide du tableau de Karnaugh, donner une expression simplifiée de $E$.
\item  Retrouver ce résultat par le calcul.
\item  En déduire une version simplifiée des critères de la direction.
\end{enumerate}

\end{Exo}

\begin{Exo}[BTS-2002]
On considère l’expression $E= a.c +b.c +a.b +a.b.c$ dépendant des variables booléennes $a$, $b$ et $c$:

\begin{enumerate}
\item Simplifier l’expression $E$ à l’aide de la lecture d’un tableau 
  de Karnaugh (ou d’une table de vérité). % et en déduire que $E = b +c$
\item  Dans un organisme qui aide des personnes au chômage à trouver un emploi,
on considère pour ces personnes, trois variables booléennes définies ainsi:
\begin{itemize}
\item $a$ = 1 si la personne est âgée de 45 ans ou plus (sinon a = 0);
\item $b$ = 1 si la personne est au chômage depuis un an ou plus (sinon b = 0);
\item $c$ = 1 si la personne a déjà suivi une formation 
  l’année précédente (sinonc = 0).
\end{itemize}
Une formation qualifiante sera mise en place pour les personnes vérifiant au
moins un des critères suivants:
\begin{itemize}
\item avoir 45 ans ou plus et être au chômage depuis moins de un an;
\item avoir moins de 45 ans et ne pas avoir suivi de formation l’année précé-
dente;
\item être au chômage depuis un an ou plus et ne pas avoir suivi de formation
l’année précédente;
\item avoir moins de 45 ans, être au chômage depuis moins de un an et avoir
suivi une formation l’année précédente.
\end{itemize}
Les personnes qui ne répondent à aucun de ces quatre critères, pourront par-
ticiper à un stage d’insertion en entreprise.
\begin{enumerate} 
\item Écrire l’expression booléenne $F$ en fonction des variables $a$, $b$ et 
$c$ qui
traduit le fait que la personne pourra suivre cette formation qualifiante.
\item En déduire une caractérisation simple des personnes qui participeront 
à un stage d’insertion en entreprise.
\end{enumerate}
\end{enumerate}
\end{Exo}



\section{Résolution d'équations booléennes}


Soit une équation booléenne de la forme la plus générale: 
$$f(x_1, x_2, \ldots , x_n) = g(x_1, x_2, \ldots, x_n)$$

\begin{enumerate}
\item Puisque $A = B \Longleftrightarrow A \oplus B = 0$, on se ramène immédiatement à une équation du type:
$$F(x_1, x_2, \ldots , x_n) = 0$$
\item On met F sous la forme:
$$F(x_1, x_2, \ldots , x_n)= \overline{x_1} \cdot r+x_1 \cdot s = 0$$
Cette dernière équation est équivalente, en algèbre de Boole, aux deux équations  $$\left\{\hbox{$\vcenter{\hbox{$(1)\quad
\overline{x_1} \cdot r = 0$}\hbox{$(2)\quad x_1 \cdot s =
0$}}$}\right.$$
\item Une équation du type de (2) se résout par introduction d'une variable auxiliaire $y_1$. En effet, $$x_1 \cdot s = 0 \Longleftrightarrow \exists
y_1 \in E, x_1 = y_1 \cdot \overline{s}$$.
\item Dans ces conditions, $\overline{x_1}= \overline{y_1} + s$, valeur que l'on
porte dans (1), pour obtenir l'équation $\overline{y_1} \cdot r + r \cdot s =
0$, qui est elle-m\^eme équivalente aux deux équations
\begin{center}
$\left\{\hbox{$\vcenter{\hbox{$(3)\quad
\overline{y_1} \cdot r = 0$}\hbox{$(4)\quad r \cdot s =
0$}}$}\right.$.
\end{center}

En utilisant la variable auxiliaire $z_1$, (3) se résout comme (2) par : $$\exists z_1 \in E, y_1 = \overline{z_1} + r$$

\item Finalement, l'équation proposée est équivalente aux équations :
\begin{itemize}
\item (5) $x_1 = (\overline{z_1} + r) \cdot \overline{s}$;(qui donne les valeurs de $x_1$)
\item (4) $r \cdot s = 0$ (qui ne comporte plus que n-1 variables).
\end{itemize}

On recommence donc les mêmes opérations pour $x_2$ dans (4), et ainsi de suite.
\end{enumerate}





\begin{Exo}
Résoudre l'équation: $x + y = x + z$.
\end{Exo}

\begin{Exo}
Résoudre l'équation: $x \cdot y+ \overline{x} \cdot z = 0$
\end{Exo}

\begin{Exo}
Résoudre le système d'équations :
$\left\{\hbox{$\vcenter{\hbox{$x+y=x+z$}\hbox{$x \cdot y = x \cdot z$}}$}\right.$
\end{Exo}




\begin{Exo}[Fonctions booléennes universelles]
On considère une fonction booléenne de deux variables, mise sous forme canonique disjonctive:
$f(x,y) = \alpha \cdot \overline{x} \cdot
\overline{y}+\beta \cdot \overline{x} \cdot y+ \gamma \cdot x
\cdot \overline{y} + \delta \cdot x \cdot y$, où $(\alpha\vir\beta\vir
\gamma\vir\delta )\in\{0,1\}^4$
\begin{itemize}
\item Montrer que cette fonction n'est susceptible d'exprimer la négation que si $\alpha =1$ et $\delta = 0$.
\item Dans ce cas, montrer qu'il n'y a que deux couples de valeurs possibles pour $\beta$ et $\gamma$, si l'on veut que f puisse aussi exprimer la somme $x+y$ et
le produit $x \cdot y$.
\end{itemize}
\end{Exo}


%%%%%%%%%%%%%%%%% méthode des consensus 
La simplification des fonctions booléennes doit être laissée aux méthodes 
algébriques dans les cas plus complexes, de manière à pouvoir affirmer 
avoir trouvé une forme minimale, et éventuellement toutes, si nécessaire.
Diverses méthodes visent cet objectif. 
Nous n'en exposerons ici qu'une seule, la méthode de Quine-Mac Cluskey, 
dite aussi \emph{méthode des consensus}.




\section{Méthode des consensus}

La méthode des consensus est une méthode algébrique permettant :

\begin{itemize}
 \item d'être certain d'obtenir la forme minimale,
\item de les obtenir toutes.
\end{itemize}

Commençons par introduire la notion de consensus...

%\subsubsection{Les consensus}
\begin{Def}
Lorsque, dans une somme booléenne, deux monômes admettent dans leur expression une et une seule variable qui se présente sous son aspect affirmé dans l'un et sous son aspect nié dans l'autre, on dit que ces deux monômes \emph{présentent un consensus} (ou sont en consensus).

Le \emph{consensus}\index{consensus} de ces deux monômes est alors le produit de toutes les autres variables.
\end{Def}



\begin{Ex}
Les monômes $\sur a\cdot b\cdot d\cdot e$ et
$a\cdot\sur c\cdot d\cdot f$ présentent un consensus, car le premier contient $\sur a$ et le second $a$. Le consensus de ces deux termes est $b\cdot\sur c\cdot d\cdot e\cdot f$.
\end{Ex}

\begin{Ex}
 $abc$ et $\sur b c d$ présentent un consensus ($acd$), quand $abc$ et $bcd$ d'une part, et $a \sur b c$ et $b \sur c d$ d'autre part, n'en présentent pas.
\end{Ex}

\begin{Exo}
Trouvez tous les consensus de $$f(a,b,c,d)= \overline{a}\overline{b}c +\overline{a}c\overline{d}+a\overline{b} \overline{c}\overline{d} + a\overline{c}d+bcd$$
\end{Exo}


\begin{Th}[Résultat fondamental]
Rajouter, à une somme booléenne, le consensus de deux termes de la somme (qui en présentent un) ne modifie pas sa valeur.
\end{Th}


\begin{Proof}
En effet, le consensus de $a\cdot m$ et de $\sur a\cdot m'$ est $m\cdot m'$, et on peut constater que
$a\cdot m+\sur a\cdot m'+m\cdot m'=a\cdot m+\sur a\cdot m'+(a+\sur a)\cdot m\cdot
m'=a\cdot m+\sur a\cdot m'+a\cdot m\cdot m'+\sur a\cdot m\cdot m'=a\cdot m+\sur a\cdot m'$.
\end{Proof}



Venons-en à la méthode proprement dite (qui permettra, on le rappelle, de trouver toutes les formes les plus simplifiées d'une expression booléenne donnée). Elle se déroule en trois étapes...

\paragraph{Étape préliminaire.}

Développer l'expression pour la mettre sous la forme d'une somme de monômes, et en suppprimer les multiples (toute autre tentative de simplification est inutile).

\paragraph{Obtention d'une forme stable par consensus.}

Répéter les deux phases suivantes, jusqu'à ce que l'expression obtenue soit stable, ne change plus :
\begin{enumerate}
\item rajouter tous les consensus des termes qui en présentent un,
\item supprimer les multiples nouvellement introduits.
\end{enumerate}


\begin{Rem}
L'introduction des consensus fait parfois apparaître des multiples. La suppression de ces derniers fait parfois apparaître de nouvelles possibilités de consensus... 
\end{Rem}



\begin{Def}[Expression stable, monômes principaux]
L'expression obtenue est dite \emph{stable du point de vue des consensus} ; elle est unique.
Ses termes s'appellent les \emph{monômes principaux}\index{monômes principaux}.
\end{Def}


\begin{Exo}
Trouvez la forme stable par consensus de $$f(a,b,c,d)= \overline{a}\overline{b}c +\overline{a}c\overline{d}+a\overline{b} \overline{c}\overline{d} + a\overline{c}d+bcd$$
\end{Exo}

La somme des monômes principaux d'une expression booléenne est généralement plus longue que l'expression de départ. Parfois, elle peut s'avérer plus courte, mais même dans ce cas, rien ne prouve qu'il n'existe pas une expression encore plus courte. C'est pourquoi, dans tous les cas, une nouvelle étape est nécessaire.

\begin{Ex}
Dans $a+\sur a\cdot b$, les deux termes présentent un consensus, qui est $b$, et on a alors $a+\sur a\cdot b=a+\sur a\cdot b+b=a+b$ (comme on le sait, c'est la règle \no 3). Ici, il y a simplification. 

Mais dans $a\cdot b+\sur a\cdot c$, les deux termes présentent un consensus, qui est $b\cdot c$. On a alors $a\cdot b+\sur a\cdot c=a\cdot b+\sur a\cdot c+b\cdot c$. Ici, il apparaît un terme de plus.
\end{Ex}




\paragraph{Choix d'un nombre minimal de monômes principaux.}
C'est la dernière étape de la méthode des consensus, qui fait intervenir la FCD. 

Les formes minimales de l'expression algébrique de départ sont des sommes des monômes principaux ci-dessus. Pour savoir quels monômes principaux garder, et quels monômes principaux supprimer, on calcule la FCD de l'expression de départ. Les mintermes de cette FCD sont des multiples des monomes principaux. Les monômes principaux retenus dans les formes minimales sont tels qu'ils possèdent tous les mintermes de la FCD parmi leurs multiples.

Pour bien comprendre cette dernière étape, \emph{i.e.} cette sélection des monômes principaux réellement utiles, on donne plusieurs exemples complets...

\begin{Ex}

Appliquons la méthode des consensus à
$$f(a,b,c) = (a+b) ( \sur a + \sur b + c)$$

\begin{enumerate}
\item On développe : $f(a,b,c) = a \sur b + ac + \sur a b + bc$.

\item Obtention d'une forme stable par consensus.

\begin{itemize}
\item $\sur a b, ac$ : pas de consensus,
\item $ac, \sur a b$ : consensus $bc$,
\item $a \sur b, \sur a b$ : pas de consensus,
\item $a c, b c$ : pas de consensus,
\item $a \sur b, b c$ : consensus $ac$,
\item $\sur a b, b c$ : pas de consensus,
\end{itemize}

D'où $f(a,b,c) = a \sur b + a c + \sur a b + b c + a c + b c $.

Par idempotence : $f(a,b,c) = a \sur b + a c + \sur a b + b c $.

Rajouter des consensus ne change alors rien : c'est notre forme stable.

Soient $p_1, p_2, p_3, p_4$ les quatre monômes principaux.

\item  Le diagramme de Karnaugh de l'expression de départ est :

\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline 
\backslashbox{c}{ab}  & 00 & 01 & 11 & 10 \\
\hline
0 & 0 & \colorbox{red}{2} & 6 & \colorbox{red}{4} \\
\hline
1 & 1 & \colorbox{red}{3} & \colorbox{red}{7} & \colorbox{red}{5}\\
\hline
\end{tabular}
\end{center}

D'où la FCD de l'expression de départ : $m_2+m_3+m_4+m_5+m_7$.

\item Choix d'un nombre minimal de monomes principaux :

\begin{center}
\begin{tabular}{|c|c c c c c|}
\hline 
\backslashbox{monomes principaux}{mintermes}  & 2 & 3 & 4 & 5 & 7 \\
\hline
1 &  &  & \colorbox{red}{X} &  \colorbox{red}{X} & \\
2 &  &  & & \colorbox{red}{X} &  \colorbox{red}{X} \\
3 & \colorbox{red}{X} &  \colorbox{red}{X} & & & \\
4 &  &  \colorbox{red}{X} & & & \colorbox{red}{X}\\
\hline
  & $\uparrow$ & $\uparrow$ & $\uparrow$ & $\uparrow$ & $\uparrow$ \\
  & $p_3$ & $p_3$ & $p_1$ & $p_1$ & $p_2$ \\
  &       & $p_4$  &      & $p_2$ & $p_4$ \\
\hline
\end{tabular}
\end{center}

Tout minterme de la FCD doit être pris au moins une fois. Donc :

\begin{itemize}
 \item pour avoir $m_2$, pas le choix : il faut prendre $p_3$. Mais, comme on a pris $p_3$, on a récupéré $m_3$.
\item pour avoir $m_4$, il faut prendre $p_1$. Avec cela, on récolte $m_5$.
\item enfin, pour avoir $m_7$, on a le choix entre $p_2$ et $p_4$.
\end{itemize}

Il y a donc deux formes minimales :
\begin{itemize}
 \item $p_1, p_2, p_3$,
\item $p_1, p_3, p_4$.
\end{itemize}

\end{enumerate}

\end{Ex}




\begin{Ex}
Appliquons la méthode des consensus à
$$S=a\cdot b+\sur a\cdot c$$



La somme des monômes principaux de $S$ est $a\cdot b+\sur a\cdot c+b\cdot c$.


Posons :

\begin{itemize}
 \item $P_1=a\cdot b$,
 \item $P_2=\sur a\cdot c$
 \item $P_3=b\cdot c$.
\end{itemize}



La FCD de $S$ est $m_1+m_3+m_6+m_7$.

\begin{itemize}
\item $m_1$ est contenu dans $P_2$. Le choix de $P_{2}$ est donc obligatoire, ce que l'on exprime par l'équation booléenne $p_{2}=1$.
\item $m_3$ est contenu dans $P_2$ et $P_3$. On a donc le choix entre ces deux monômes, ce que l'on exprime par l'équation booléenne $p_{2}+p_{3}=1$ (évidemment, le choix précédent rend cette condition inutile, mais on expose ici la méthode).
\item $m_6$ est contenu dans $P_1$, soit $p_{1}=1.$
\item $m_7$ est contenu dans $P_1$ et $P_3$, soit $p_{1}+p_{3}=1$.
\end{itemize}



Il faut donc développer le produit $p_2(p_2+p_3)p_1(p_1+p_3)=p_1p_2$ qui prouve que la forme minimale (unique, dans cet exemple) de la fonction donnée est obtenue avec la somme de $P_1$ et de $P_2$ ; il s'agit, bien entendu, de $a\cdot b+\sur a\cdot c$.
\end{Ex}



\begin{Ex}
Appliquons la méthode des consensus à
$$S=\sur a\cdot\sur c+a\cdot b\cdot d+\sur a\cdot
b\cdot c+a\cdot\sur b\cdot\sur c+\sur b\cdot c\cdot\sur d+\sur a\cdot\sur
b\cdot\sur c$$




\begin{enumerate}
\item Suppression des multiples :
$\sur a\cdot\sur c$  ~absorbe~ $\sur a\cdot\sur b\cdot\sur c$

Il reste :

 $\sur a\cdot\sur c+a\cdot b\cdot d+\sur a\cdot
b\cdot c+a\cdot\sur b\cdot\sur c+\sur b\cdot c\cdot\sur d$

\item Premiers consensus : 

$\sur a\cdot\sur c+a\cdot b\cdot d+\sur a\cdot
b\cdot c+a\cdot\sur b\cdot\sur c+\sur b\cdot c\cdot\sur d
+b\cdot\sur c\cdot d+\sur a\cdot b+\sur b\cdot\sur c+\sur a\cdot\sur
b\cdot\sur d+b\cdot c\cdot d+a\cdot\sur c\cdot d+a\cdot c\cdot\sur d+\sur
a\cdot c\cdot\sur d+a\cdot\sur b\cdot\sur d$

\item Suppression des multiples :

$\sur a\cdot b$ ~absorbe~ $\sur a\cdot b\cdot c$

$\sur b\cdot\sur c$ ~absorbe~ $a\cdot\sur b\cdot\sur c$

Il reste :

$\sur a\cdot\sur c+a\cdot b\cdot d+\sur b\cdot c\cdot\sur d
+b\cdot\sur c\cdot d+\sur a\cdot b+\sur b\cdot\sur c+\sur a\cdot\sur
b\cdot\sur d+b\cdot c\cdot d+a\cdot\sur c\cdot d+a\cdot c\cdot\sur d+\sur
a\cdot c\cdot\sur d+a\cdot\sur b\cdot\sur d$

\item Nouveaux consensus (on n'a fait figurer qu'une seule fois chacun d'entre eux) :

$\sur a\cdot\sur c+a\cdot b\cdot d+\sur b\cdot c\cdot\sur d
+b\cdot\sur c\cdot d+\sur a\cdot b+\sur b\cdot\sur c+\sur a\cdot\sur
b\cdot\sur d+b\cdot c\cdot d+a\cdot\sur c\cdot d+a\cdot c\cdot\sur d+\sur
a\cdot c\cdot\sur d+a\cdot\sur b\cdot\sur d
+\sur a\cdot b\cdot d+\sur c\cdot d+\sur a\cdot\sur d+\sur b\cdot\sur
c\cdot\sur d+b\cdot d+a\cdot b\cdot c+\sur b\cdot\sur d+b\cdot c\cdot\sur
d+\sur a\cdot b\cdot c+a\cdot\sur b\cdot\sur c+c\cdot\sur d$

\item Suppression des multiples :

$\sur a\cdot b$ ~absorbe~ $\sur a\cdot b\cdot d$ ~et~ $\sur a\cdot b\cdot c$,
$\sur b\cdot\sur c$ ~absorbe~ $\sur b\cdot\sur c\cdot\sur d$ ~et~ $a\cdot\sur
b\cdot\sur c$,
$\sur c\cdot d$ ~absorbe~ $b\cdot\sur c\cdot d$ ~et~ $a\cdot\sur c\cdot d$
$\sur a\cdot\sur d$ ~absorbe~ $\sur a\cdot\sur b\cdot\sur d$ ~et~ $\sur a\cdot c\cdot\sur d$,
$b\cdot d$ ~absorbe~ $a\cdot b\cdot d$ ~et~ $b\cdot c\cdot d$,
$\sur b\cdot\sur d$ ~absorbe~ $\sur b\cdot c\cdot\sur d$ ~et~ $a\cdot\sur
b\cdot\sur d$ 
$c\cdot\sur d$ ~absorbe~ $a\cdot c\cdot\sur d$ ~et~ $b\cdot c\cdot\sur d$

Il reste : 
$\sur a\cdot\sur c+\sur a\cdot b+\sur b\cdot\sur c+
\sur c\cdot d+\sur a\cdot\sur d+b\cdot d+a\cdot b\cdot c+\sur b\cdot\sur
d+c\cdot\sur
d$

\item Nouveaux consensus (on n'a fait figurer qu'une seule fois chacun d'entre eux) :

$\sur a\cdot\sur c+\sur a\cdot b+\sur b\cdot\sur c+
\sur c\cdot d+\sur a\cdot\sur d+b\cdot d+a\cdot b\cdot c+\sur b\cdot\sur
d+c\cdot\sur d+b\cdot c+a\cdot b\cdot d+b\cdot c\cdot\sur d+a\cdot c\cdot\sur
d$ 

\item Suppression des multiples :

$b\cdot d$ ~absorbe~ $a\cdot b\cdot d$,
$c\cdot\sur d$ ~absorbe~ $a\cdot c\cdot\sur d$ ~et~ $b\cdot
c\cdot\sur d$,
$b\cdot c$ ~absorbe~ $a\cdot b\cdot c$ 

Il reste : 
$\sur a\cdot\sur c+\sur a\cdot b+\sur b\cdot\sur c+
\sur c\cdot d+\sur a\cdot\sur d+b\cdot d+\sur b\cdot\sur
d+c\cdot\sur d+b\cdot c$

\item Un dernier tour de consensus montre que cette expression est stable par consensus.
\end{enumerate}






A l'aide d'un diagramme de Karnaugh, on détermine les mintermes contenus dans chacun des monômes principaux.


On en déduit la FCD, et, dans le tableau qui suit, on fait apparaître les monômes principaux et les mintermes qu'ils contiennent :



\scriptsize
\noindent \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\backslashbox{monome}{minterme} & $m_0$ & $m_1$ & $m_2$ & $m_4$ & $m_5$ & $m_6$ & $m_7$ & $m_8$ & $m_9$ & $m_{10}$ & $m_{13}$ & $m_{14}$ & $m_{15}$ \\
\hline
$P_1 = \sur a\cdot\sur c$ &  $\diamond$  &  $\diamond$ &  &  $\diamond$ &  $\diamond$ &  &  &  &  &  &  &  & \\
\hline
$P_2 = \sur a\cdot b$     &  &  &  &  $\diamond$ &  $\diamond$ &  $\diamond$ &  $\diamond$ &  &  &  &  &  &  \\
\hline
$P_3 = \sur b\cdot\sur c$ &  $\diamond$ &  $\diamond$ &  &  &  &  &  &  $\diamond$ &  $\diamond$ &  &  &  & \\
\hline
$P_4 = \sur c\cdot d $    &  &  $\diamond$ &  &  &  $\diamond$ &  &  &  &  $\diamond$ &  &  $\diamond$ &  &  \\
\hline
$P_5 = \sur a\cdot\sur d$ &  $\diamond$ &  &  $\diamond$ &  $\diamond$ &  &  $\diamond$ &  &  &  &  &  &  &  \\
\hline
$P_6 = b\cdot d $         &  &  &  &  &  $\diamond$ &  &  $\diamond$ &  &  &  &  $\diamond$ &  &  $\diamond$ \\
\hline
$P_7 = \sur b\cdot\sur d$ &  $\diamond$ &  &  $\diamond$ &  &  &  &  &  $\diamond$ &  &  $\diamond$ &  &  &  \\
\hline
$P_8 = c\cdot\sur d $     &  &  &  $\diamond$ &  &  &  $\diamond$ &  &  &  &  $\diamond$ &  &  $\diamond$ &  \\
\hline
$P_9 = b\cdot c $         &  &  &  &  &  &  $\diamond$ &  $\diamond$ &  &  &  &  &  $\diamond$ &  $\diamond$ \\
\hline
\end{tabular}
\normalsize




La première colonne, par exemple, s'interprète comme suit : dans toute forme (réduite ou non) prétendant représenter l'expression donnée au départ, il est nécessaire qu'un monôme au moins contienne le
minterme $m_0$, puisque ce dernier figure dans la FCD.


Cette condition peut être réalisée en choisissant le monôme principal $P_1$, ou $P_3$, ou $P_5$, ou $P_7$. Elle peut être exprimée par l'équation booléenne $p_1+p_3+p_5+p_7=1$, etc.


On obtient l'équation booléenne :

\noindent
$(p_1+p_3+p_5+p_7)(p_1+p_3+p_4)(p_5+p_7+p_8)(p_1+p_2+p_5)(p_1+p_2+p_4+p_6)(p_2+p_5+p_8+p_9)(p_2+p_6+p_9)
(p_3+p_7)(p_3+p_4)(p_7+p_8)(p_4+p_6)(p_8+p_9)(p_6+p_9)=1$




On supprime évidemment les conditions qui sont automatiquement réalisées lorsque d'autres le sont (si
$p_3+p_7$ vaut 1, alors $p_1+p_3+p_5+p_7$ aussi), il
reste

\noindent
$(p_1+p_2+p_5)(p_3+p_7)(p_3+p_4)(p_7+p_8)(p_4+p_6)(p_8+p_9)(p_6+p_9)=1$



On développe le produit, mais pas le premier facteur, car il est le seul à contenir les monômes principaux $p_1$, $p_2$ et $p_5$, donc on sait déjà qu'il faudra en prendre un (et un seul, pour une forme minimale...) des trois.



On obtient


\noindent
$(p_1+p_2+p_5)(p_3+p_4p_7)(p_8+p_7p_9)(p_6+p_4p_9)
= (p_1+p_2+p_5)(p_3p_8p_3p_7p_9+p_4p_7p_8+p_4p_7p_9)(p_6+p_4p_9) = (p_1+p_2+p_5)
(p_3p_6p_8+p_3p_4p_8p_9+p_3p_6p_7p_9+p_3p_4p_7p_9+p_4p_6p_7p_8+p_4p_7p_8p_9+p_4p_6p_7p_9+p_4p_7p_9) =
(p_1+p_2+p_5)
(p_3p_6p_8+p_3p_4p_8p_9+p_3p_6p_7p_9+p_4p_6p_7p_8+p_4p_7p_9) = 1 $



On constate qu'il est possible de réaliser la condition de la seconde parenthèse en ne choisissant que 3
monômes principaux : $P_3$, $P_6$ et $P_8$, ou encore $P_4$, $P_7$ et $P_9$ (les autres choix possibles
en nécessitent 4).


En plus, il faut choisir l'un des trois de la première parenthèse, comme on l'a dit plus haut.



On obtient donc 6 formes minimales :

$$\left\{\begin{array}{c}\sur b\cdot\sur c+b\cdot d+c\cdot\sur d\cr {\rm ou} \cr \sur c\cdot d+\sur
b\cdot\sur d+b\cdot c\cr\end{array}\right\}\quad+\quad\left\{\begin{array}{c}
\sur a\cdot\sur c\cr{\rm ou}\cr 
\sur a\cdot b\cr{\rm ou}\cr\sur a\cdot\sur d\cr\end{array}\right\}$$

\end{Ex}

\begin{Exo}
On considère $f(a,b,c,d)= \overline{a}\overline{b}c +\overline{a}c\overline{d}+a\overline{b} \overline{c}\overline{d} + a\overline{c}d+bcd$
\begin{itemize}
\item Trouvez sa FCD.
\item En déduire ses formes minimales.
\end{itemize}
\end{Exo}





\begin{Exo}
Utiliser la méthode des consensus pour obtenir toutes les formes minimales des fonctions booléennes suivantes:
\begin{enumerate}
\item Celles des précédents exemples et exercices.
\item $\sur d\cdot e+\sur a\cdot c+b\cdot\sur c+a\cdot \sur b+a\cdot d\cdot e+\sur
a\cdot d\cdot
\sur e$
\end{enumerate}
\end{Exo}

% 
\newcommand{\n}[1]{\ensuremath{\overline{#1}}} 

% \begin{Exo}[Implicants premiers] % Lipschutz 12.10
% Un monôme de $P$ est un implicant premier de l'expression booléenne $E$ si $P + E = E$ et tout autre monôme inclus $P$ n'a pas cette  proprité.

% Etant donné $ E = x\n{y}+xy\n{z} + \n{x}y\n{z}$, montrer que $x\n{z}$ est un implicant premier de $E$.
% \end{Exo}

% \noindent\underline{\textit{Réponse : }}
% $x\n{z} + E = E$, 
% $x + E \neq E$ et $\n{z} + E \neq E$. 

% \begin{Exo}[Application de la méthode des consensus] % Lipschutz 12.15
% Utiliser la méthode du consensus pour trouver une forme 
% minimale de $E$ et $F$ avec 
% $E = x\n{y} + xy\n{z} + \n{x}y\n{z}$ et 
% $F = xy + \n{y}t + \n{x}y\n{z} + x\n{y}z\n{t}$.
% \end{Exo}






\centerline{\x{Fin du Chapitre}}