ajout de proposition13

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

\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 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|c||}
\hline
\hbox{Propriété}        &   & &            \\ \hline
\hbox{idempotence}      & a+a=a               &    \hbox{distributivités}  & a\cdot(b+c)=a\cdot b+a\cdot c 
                                        \\
                        & a\cdot a=a           &                         & a+b\cdot c=(a+b) \cdot(a+c)
                                           \\ \hline

\hbox{commutativité}    & a+b=b+a         & \hbox{involution}       & \sur{\sur a}=a    \\ 
&a\cdot b=b\cdot a &                        &  \\ \hline
\hbox{associativité}    & a+(b+c)=(a+b)+c  & \hbox{complémentation}  & \sur 0=1          \\ 
                        & a\cdot(b\cdot c)=(a\cdot b)\cdot c &                         & \sur 1=0          \\ \hline
\hbox{éléments neutres} & a+0=a               &\hbox{partition}        & a+\sur a=1        \\

                        & a\cdot 1=a &                        & a\cdot \sur a=0  \\ \hline           
\hbox{absorption}       & a+1=1                  & \hbox{\og Lois de De Morgan\fg{}} 
                        & \sur{a+b}=\sur a\cdot\sur b 
                                            \\

                        & a\cdot 0=0     &                        & \sur{a\cdot b}=\sur a+\sur b 
                                           \\\hline


\end{array}
$$
\end{small}
\begin{center}Propriétés d'une algèbre de Boole\end{center}



\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{Th}[Suppression de redondance]
On a les trois règles suivantes:
\begin{enumerate}
\item Dans une somme booléenne, tout terme absorbe ses multiples: $a+a\cdot b=a$.
\item Dans un produit booléen, tout facteur absorbe tout autre facteur qui le contient en tant que terme: $a\cdot(a+b)=a$.
\item Ajouter à un terme un multiple $b$ de son complément revient à ne lui ajouter que $b$: $a+\sur a\cdot b=a+b$
\end{enumerate}
\end{Th}

\begin{Proof}
On déomntre les trois règles comme suit:
\begin{enumerate}
\item  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$.
\item En effet, $a\cdot(a+b)=a\cdot a+a\cdot b=a+a\cdot b=a$.
\item $a+\sur a\cdot b=(a+\sur a)\cdot(a+b)=1\cdot(a+b)=a+b$.
\end{enumerate}
\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}




 \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}

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{Def}[Aspect d'une variable]
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{Def}


\begin{Def}[Fonction booléenne nulle]
On appelle \emph{fonction booléenne nulle} \index{fonction!booléenne!nulle} 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}  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}



\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{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}


\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 produit de variables booléennes éventuellement niées.
\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}


\subsection{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 :
est fondée sur les propriétés des mintermes (ils réalisent une partition de l'unité),


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.

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}


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{array}{|c|c|c|c|c|}
\hline 
%\backslashbox{c}{ab}
  & 00 & 01 & 11 & 10 \\
\hline
0 & \sur a \sur b \sur c & \sur a b \sur c & a b \sur c & a \sur b \sur c  \\
\hline
1 & \sur a \sur b  c & \sur a  b  c &  a  b  c & a \sur b  c\\
\hline
\end{array}
$$




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{Exoc}
Faire un diagramme à cinq variables.
\end{Exoc}

$$
\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline 
  & 000 & 001 & 011 & 010 & 110 & 111 & 101 & 100 \\
\hline
00 & 
\sur a \sur b \sur c \sur d \sur e & 
\sur a \sur b c \sur d \sur e & 
\sur a  b c \sur d \sur e & 
\sur a b \sur c \sur d \sur e & 
a  b \sur c \sur d \sur e  & 
a b  c \sur d \sur e & 
a \sur b  c \sur d \sur e & 
 a \sur b \sur c \sur d \sur e \\
\hline
01 & 
\sur a \sur b \sur c \sur d  e & 
\sur a \sur b c \sur d  e & 
\sur a  b c \sur d  e & 
\sur a b \sur c \sur d  e & 
a  b \sur c \sur d  e  & 
a b  c \sur d e & 
a \sur b  c \sur d  e & 
 a \sur b \sur c \sur d  e \\
\hline
11 & 
\sur a \sur b \sur c d  e & 
\sur a \sur b c d  e & 
\sur a  b c  d  e & 
\sur a b \sur c  d  e & 
a  b \sur c  d  e  & 
a b  c d e & 
a \sur b  c  d  e & 
 a \sur b \sur c  d  e \\
\hline
10 &
\sur a \sur b \sur c d  \sur e & 
\sur a \sur b c d  \sur e & 
\sur a  b c  d  \sur e & 
\sur a b \sur c  d  \sur  e & 
a  b \sur c  d  \sur  e  & 
a b  c d \sur e & 
a \sur b  c  d \sur  e & 
 a \sur b \sur c  d \sur  e \\
\hline
\end{array}
$$



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}







\centerline{\x{Fin du Chapitre}}