\chapterimage{ensemble2}
\chaptertext{La   notion   d'ensemble   peut   paraître   évidente:   le
dictionnaire parle de \og  groupe, assemblage d'éléments formant un tout
ou ayant les mêmes  caractéristiques\fg{}.  Les mathématiques du XX \eme
siècle ont pour  base la \textit{théorie des ensembles}:  il s'agit donc
d'un concept  de base et  même DU concept  de base, encore  plus basique
que  la  notion de  nombre  car nous  verrons  que  les nombres  entiers
peuvent être définis et construits à l'aide d'ensembles.

En informatique,  c'est aussi  une notion essentielle:  un \textit{type}
est en effet un ensemble au  sens mathématique du terme, comme les types
de base que  vous avez vu en ALGO-1 (entiers,  chaînes, booléens) ou les
types construits que nous allons créer selon nos besoins.

Nous allons  prendre une approche fonctionnelle de  la notion d'ensemble
et  des  opérations  associées   ce  qui  nous  permettra  d'implémenter
directement nos travaux dans le langage \textsc{Caml}.}


\setlength{\topsep}{1pt}
\setlength{\parskip}{1pt}
\setlength{\partopsep}{1pt}
\setlength{\parsep}{1pt}
\chapter{Ensembles: une approche fonctionnelle}


\begin{flushright}
  \begin{quote}
{\itshape
Tous ensemble, tous ensemble, hé, hé\\
Tous ensemble, tous ensemble, hé, hé\\
Tous ensemble, tous ensemble, hé, hé\\
Tous ensemble, tous ensemble, hé, hé\\
}
  \end{quote}
Rue de Strasbourg,13 Mai 2003
\end{flushright}

\section{Définition}

\subsection{Définition récursive}

\begin{definition}
  Un ensemble d'\textit{éléments} est:
  \begin{itemize}
  \item soit l'ensemble vide, noté $\bigl\{\bigr\}$ (ou bien $\emptyset$);
  \item soit construit en \og ajoutant\fg{} un élément $x$ à un ensemble
        E. On notera  alors cette opération
        $x\oplus E$.
  \end{itemize}
\end{definition}


Cette  définition  est  \textit{récursive}  comme  nous  l'avons  vu  au
chapitre précédent. Elle nous permettra  de définir un type construit le
plus abstrait possible avec \textsc{Caml}.

\subsection{Avec \textsc{Caml}}


\caml
\begin{lstlisting}[caption={}]
type 'a ens =
  | Vide 
  | Ens of ('a * 'a ens);;
\end{lstlisting}

L'ensemble vide et  l'opération $\oplus$ sont les \textit{constructeurs}
du type  construit \texttt{ens}. Les éléments sont  d'un type quelconque
\texttt{'a}.

On peut par exemple construire des ensembles d'entiers:


\begin{lstlisting}[caption={}]
# Ens(1,Vide);;
- : int ens = Ens (1, Vide)
# Ens(3,Ens(2,Ens(1,Vide)));;
- : int ens = Ens (3, Ens (2, Ens (1, Vide)))
# let e = Ens(3,Ens(2,Ens(1,Vide)));;
val e : int ens = Ens (3, Ens (2, Ens (1, Vide)))
# Ens(4,e);;
- : int ens = Ens (4, Ens (3, Ens (2, Ens (1, Vide))))
\end{lstlisting}


Nous reviendrons en fin de chapitre sur la programmation des différentes
opérations sur les ensembles avec \textsc{Caml}. Revenons au cas général.



\section{Propriétés et notations}


\begin{definition}[Axiome d'extensionnalité]
Deux ensembles  A et B sont  égaux si, et seulement  si, ils contiennent
les mêmes éléments. On écrit alors $A=B$.
\end{definition}

Ça  paraît  idiot  comme axiome  mais  cela  permet  de bien  cerner  le
problème: c'est la notion d'appartenance  d'un élément à un ensemble qui
est primordiale.


Une première  conséquence est que l'ordre d'apparition  des éléments dans
la construction des ensembles n'est pas important:

$$x\oplus \bigl\{y\bigr\}=y\oplus \bigl\{x\bigr\}$$




\begin{notation}
On notera $x\in  A$ pour signifier que $x$ est  un élément de l'ensemble
A.    Cette  notation   est  due   au  mathématicien   anglais  Bertrand
    \textsc{Russel} en 1903 qui reprenait l'epsilon $\varepsilon$ de l'italien
    Giuseppe  \textsc{Peano}  en 1889  mais  en \og  l'arrondissant\fg{}
    compte-tenu des  contraintes typographiques anglaises  sous la forme
    $\epsilon$ qui a donné $\in$.
\end{notation}




Par souci de simplification, nous noterons aussi:
\begin{itemize}
\item  le \textit{singleton} $x\oplus \bigl\{\bigr\}$ sous la forme
$\bigl\{x\bigr\}$;
\item    l'ensemble    $x\oplus    \left(y   \oplus    \left(z    \oplus
      \bigl\{\bigr\}\right)\right)$ sous la forme $\bigl\{x,y,z\bigr\}$.
\end{itemize}


Ainsi $$x\oplus \left(y\oplus \bigl\{\bigr\}\right)=x\oplus\bigl\{y\bigr\}=\bigl\{x,y\bigr\}$$



\begin{recherche}
On considère les ensembles:

      $E_1=\bigl\{a,b,c\bigr\}$,
$E_2=\bigl\{b,c,a\bigr\}$,        $E_3=\bigl\{b,a,a,c,b\bigr\}$,
$E_4=\bigl\{c,c,c,a,b,a,c,b,b,b\bigr\}$, $E_5=c \oplus E_2$.

Quels   sont,    parmi   ces
ensembles, ceux qui sont égaux?
\end{recherche}



L'opérateur  $\oplus$ n'est  pas \textit{commutatif}  car  l'opérande de
gauche est  un élément et  celui de droite  un ensemble: leurs  rôles ne
peuvent pas être échangés.


\begin{remarque}
On pourrait cependant modifier notre définition et ne pas accepter des
ensembles du type $\bigl\{1,2,2,3\bigr\}$, cet ensemble étant pour nous égal
à $\bigl\{1,2,3\bigr\}$. Cependant, cela  n'est pas gênant et correspond
à la construction proposée avec \textsc{Caml}. Il faudra malgré tout
faire attention  à la définition du \textit{cardinal}  d'un ensemble que
nous allons voir plus loin.
\end{remarque}


\section{Extension - compréhension}


\subsection{Définition par extension}

On  peut définir  un  ensemble \textit{par  extension}, c'est-à-dire  en
écrivant tous ses éléments:

$$A=\bigl\{1,3,5,7,9\bigr\}$$

C'est  pourquoi  on  a  parlé  d'axiome  d'\textit{extensionnalité}:  on
compare les éléments des ensembles.

Vous aurez remarqué que des ensembles égaux peuvent avoir des définition
en extension différentes.


Cependant,  il  peut s'avérer  fastidieux  de  définir  un ensemble  par
extension. Nous  allons introduire un  peu de vocabulaire de  la \textit{logique
des prédicats} pour définir certains ensembles plus facilement.

\subsection{Un très rapide survol de la logique}


Nous consacrerons plusieurs chapitres à l'étude de la logique qui est un
des piliers  de l'informatique.  Cependant, nous allons  voir rapidement
quelques notions  simples en avant-première dont nous  avons besoin tout
de suite.

Il existe un type (donc un ensemble..) défini dans tous les langages informatiques car il en
constitue la  base. Il s'agit  du type \textit{booléen} qui  ne contient
que  deux  éléments:  VRAI  et  FAUX  (ou  TRUE  et  FALSE  ou  0  et  1
ou ...). Nous noterons cet ensemble $\BR_2=\bigl\{VRAI,FAUX\bigr\}$.


Si E est  un ensemble quelconque, un \textit{prédicat}  est une fonction
de E dans l'ensemble $\BR_2$.

\begin{exemple}
Par exemple \og \textit{est un entier pair}\fg{} est un prédicat défini sur
l'ensemble  $\bbn$  des entiers  naturels  que  nous  noterons P.  Alors
$P(2)=VRAI$ et $P(3)=FAUX$.
\end{exemple}

Nous serons plus  rigoureux un peu plus tard  afin de pouvoir comprendre
le  fonctionnement de  la  machine. Nous  définirons  en particulier  la
notion de \textit{proposition logique}. Pour l'instant cette approche naïve
sera suffisante.


Soit un prédicat P défini sur $\bbn$ par $P(x)=\og x^2=2\fg{}$.

Quelque soit l'entier  $x$, on a $x^2\neq 2$.  On notera cette propriété
par:

$$\forall x,x\in \bbn \text{ ET } P(x)=FAUX$$



\begin{remarque}
  Nous noterons ceci plus tard : $\forall x (x\in\bbn \wedge \neg P(x))$...
\end{remarque}


$\forall$  est  un  \textit{quantificateur  universel}  (c'est  un  A  à
l'envers, car  en anglais, ce symbole  se lit \textit{for All}  et a été
introduit par l'anglais \textsc{Russel}...).

Soit maintenant le prédicat R défini sur $\bbn$ par $R(x)=\og x^2=4\fg{}$.


Il existe au moins  un entier dont l'image par R est  VRAI: il s'agit de
2.


On note alors:

$$\exists x,x\in \bbn \text{ ET } R(x)=VRAI$$



$\exists$   est   l'autre   quantificateur   universel   introduit   par
\textsc{Russel} (un E à l'envers comme dans \textit{it Exists}).


On  peut même  préciser que  cet entier  est \textit{unique}  en faisant
suivre le quantificateur d'un point d'exclamation:




$$\exists ! x, x\in\bbn \text{ ET } R(x)=VRAI$$




\subsection{Définition par compréhension}


Un entier pair est un entier multiple de 2.

Nous pouvons  à présent définir \textit{par  compréhension} l'ensemble $\bbn_2$
des entiers naturels pairs:

$$\bbn_2=\bigl\{x\mid (x\in\bbn) \text{ ET } (\exists n, n\in\bbn \text{ ET } x=2n)\bigr\}$$


\begin{recherche}
   On note $E=\bigl\{x\mid x\in\bbz \text{ ET } x^2=1\bigr\}$ et
  $F=\bigl\{x\mid x \in\bbr \text{ ET }\left|x\right|=1\bigr\}$. 

Que pouvez-vous dire de $E$ par rapport à $F$? 
\end{recherche}


\subsection{Définition récursive}

On sait que 0 est un entier naturel pair.

On  peut montrer  par récurrence  que si  l'entier $x$  est  pair, alors
l'entier $x+2$ l'est aussi.

On définit ainsi l'ensemble  $\bbn_2$ précédent de manière récursive par
la donnée:
\begin{itemize}
\item d'une  base: 0 est un  entier pair (c'est  l'élément ou l'ensemble
      qui  servira  à construire  \textit{tous}  les  autres éléments  à
      l'aide de la règle de récurrence);
\item  d'une règle  de récurrence:  ici, si  $x$ est  pair,  alors $x+2$
      l'est aussi. 
\end{itemize}

La base et la règle de récurrence constituent les \textsc{constructeurs}
de l'ensemble. 

Informatiquement,  les  langages fonctionnels  permettent  de créer  des
types (donc des ensembles...) construits récursivement comme nous le verrons avec \textsc{Caml}.



\section{Inclusion}

\begin{definition}
  Un ensemble d\'{e}sign\'{e} par $B$ est \textbf{contenu} ou \textbf{inclus}
dans l'ensemble d\'{e}sign\'{e} par $A$ ou encore est une \textbf{partie} de
l'ensemble $A$ si, et seulement si, tout \'{e}l\'{e}ment de $B$ est aussi un 
\'{e}l\'{e}ment de $A$. On note alors $B\subseteq A$ ou $A\supseteq B$.

 On
dit aussi que $B$ est \textbf{une partie ou un sous ensemble de} $A$.
\end{definition}





La d\'{e}finition pr\'{e}c\'{e}dente affirme que $\{\} $ est inclus dans
n'importe quel ensemble $A$ car, si ce n'\'{e}tait pas le cas, l'ensemble
vide poss\`{e}derait au moins un \'{e}l\'{e}ment qui n'appartient pas \`{a} $%
A$ ce qui est absurde.
 On notera aussi que tout ensemble est inclus dans lui m\^{e}me. On
retiendra donc que si $A$ d\'{e}signe un ensemble \textbf{on a toujours} 

$$
\{\} \subseteq A\text{ et }A\subseteq A
$$


\begin{remarque}
Pratiquement tous les auteurs d'ouvrages math\'{e}matiques en langue fran\-%
\c{c}aise utilisent le symbole $\subset $ pour d\'{e}finir l'inclusion
(large), nous estimons qu'ils le font \`{a} tort. Nous ne nous alignons pas
sur une notation anglo-saxonne, nous ne faisons qu'utiliser la notation du
syst\`{e}me internationnal. Pour nous, le symbole $\subset $ d\'{e}signe
l'inclu\-sion stricte en ce sens que si $B\subset A$ on ne peut avoir $B=A$
et par cons\'{e}quent l'\'{e}nonc\'{e} $A\subset A$ est faux. Pour \'{e}%
viter les confusions toujours possibles nous utiliserons le symbole $%
\varsubsetneq $ ou $\subsetneqq $ pour d\'{e}signer l'inclusion stricte%
\begin{equation*}
B\varsubsetneq A\text{ signifie }\left( B\subseteq A\text{ et }B\neq
A\right) \vspace{0.2cm}
\end{equation*}%
qu'il ne faut pas confondre avec $B$ $\nsubseteq A$ qui exprime que $B$
n'est pas inclus dans $A.$ On dit que $B$ est une partie propre de $A$ si,
et seulement si, $B\subseteq A$ avec $B\neq A$ et $B\neq \big\{\big\} \ $(il
est n\'{e}cessaire que $A$ ne soit pas vide et ne soit pas un singleton).
\end{remarque}







Comme nous l'avons d\'{e}j\`{a} indiqu\'{e}, un ensemble est toujours inclus
dans lui m\^{e}me. Pour tout ensemble $A$ il est correct d'\'{e}crire $%
A\subseteq A.$ La d\'{e}finition de l'\'{e}galit\'{e} de deux ensembles s'%
\'{e}crit maintenant%
$$
\left[ A\subseteq B\text{ et }B\subseteq A\right] \text{ si, et seulement si, } A=B
$$


\begin{NB}
Cette propri\'{e}t\'{e} est \`{a} retenir. Pour d\'{e}montrer l'\'{e}galit%
\'{e} de deux ensembles, on n'a pratiquement pas d'autre m\'{e}thode que de d%
\'{e}montrer la double inclusion. Notons aussi le r\'{e}sultat \'{e}vident 
$$
\text{SI   }\left[   C\subseteq    B\text{   et   }B\subseteq   A\right]
\text{ ALORS } C\subseteq A
$$
\end{NB}

Pour guider les raisonnements ou pour \og imaginer\fg{} les ensembles en pr\'{e}%
sence on est amen\'{e} \`{a} sch\'{e}matiser les ensembles par une ligne ferm%
\'{e}e sans point double, une \og patate\fg{}  peut tr\`{e}s
bien faire l'affaire mais un cercle ou un rectangle sont aussi d'excellentes
solutions. Ces figures sont appel\'{e}es diagrammes d'Euler-Venn ou
\textit{diagrammes de Venn}. Pour \'{e}viter les confusions, il est convenu que les 
\'{e}l\'{e}ments de l'ensemble repr\'{e}sent\'{e} \og sont tous \`{a} l'int\'{e}%
rieur du dessin et pas sur la fronti\`{e}re\fg{}. Pour mettre en exergue un ou
plusieurs \'{e}l\'{e}ments, on utilise des points ou croix et pour repr\'{e}%
senter l'ensemble vide, il n'y a aucune bonne solution.%



Les patates permettent d'illustrer l'inclusion:




% Definition of circles
\def\firstcircle{(0,0) ellipse (2.5cm and 1.5cm)}
\def\secondcircle{(0,0) circle (.75cm)}

\colorlet{circle edge}{blue!50}
\colorlet{circle area}{blue!20}

\tikzset{filled/.style={fill=circle area, draw=circle edge, thick},
    outline/.style={draw=circle edge, thick}}

\setlength{\parskip}{5mm}
% Set A and B
\begin{center}
\begin{tikzpicture}
    \begin{scope}
        \clip \firstcircle;
        \fill[filled] \secondcircle;
    \end{scope}
    \draw[outline] \firstcircle node {$A$};
    \draw[outline] \secondcircle node  {};
    \node[anchor=south] at (current bounding box.north) {$A \subseteq B$};
\end{tikzpicture}
\end{center}





\section{Parties d'un ensemble}

\subsection{Définition}

\begin{definition}
Nous admettons que si $E$ d\'{e}signe un ensemble alors \textbf{l'ensemble
des parties de} $E$ est un ensemble (math\'{e}matiquement parlant) not\'{e} $%
\mathcal{P}\left( E\right) $ mais aussi $\mathbb{P}\left( E\right) .$ Cet
ensemble peut s'\'{e}crire en \og pseudo-compr\'{e}hension\fg{} par: 

$$
\mathcal{P}\left( E\right) =\Bigl\{ X\mid X\subseteq E\Bigr\}
$$
\end{definition}

Nous pr\'{e}cisons bien \og pseudo-compr\'{e}hension\fg{} car nous ne pouvons
indiquer \`{a} quel ensemble appartient $X$ puisque nous cherchons \`{a} d%
\'{e}finir cet ensemble. Il faut imm\'{e}diatement retenir l'\'{e}quivalence%

$$
X\in \mathcal{P}\left( E\right) \text{ si, et seulement si, } X\subseteq E\vspace{0.2cm}
$$


qui seule permet de v\'{e}rifier que $X$ est bien un \'{e}l\'{e}ment de $%
\mathcal{P}\left( E\right) $ car il ne faut surtout pas croire que notre
esprit soit capable de \og ma\^{\i}triser\fg{} un ensemble de parties quasi imm%
\'{e}diatement. Pour imaginer un peu plus ce qu'est $\mathcal{P}\left(
E\right) $ on peut dire que $\mathcal{P}\left( E\right) $ est l'\textbf{%
ensemble} des solutions du probl\`{e}me $X\subseteq E$ o\`{u} $X$ est
l'inconnue. On remarque alors que $\{\} $ et $E$ sont des solutions 
\'{e}videntes et donc que $\mathcal{P}\left( E\right) $ ne peut \^{e}tre
vide. Si $E=\{\} ,$ $\mathcal{P}\left( E\right) $ ne contient qu'un
seul \'{e}l\'{e}ment qui est $\{\} $ ; $\mathcal{P}\left( \{\}
\right) =\left\{ \{\} \right\} $ et on se persuadera que $\left\{
\{\} \right\} $ n'est pas l'ensemble vide, c'est parfaitement clair,
entre les deux accolades \og il y a quelque chose\fg{} qui existe et qui est
l'ensemble vide, $\left\{ \{\} \right\} $ est un singleton ! Si $E\neq
\{\} $ alors $\mathcal{P}\left( E\right) $ poss\`{e}de au moins deux 
\'{e}l\'{e}ments distincts $\{\} $ et $E$ :%

$$
\mathcal{P}(E)=\Bigl\{ \{\} ,\ldots ,E\Bigr\}
$$


Prenons par exemple pour ensemble $E=\Bigl\{ D,L,M\Bigr\} $
 alors

$$
\mathcal{P}\left( E\right) =\Bigl\{ \{\} ,\left\{ D\right\} ,\left\{
L\right\} ,\left\{ M\right\} ,\left\{ D,L\right\} ,\left\{ D,M\right\}
\left\{ L,M\right\} ,E\Bigr\}
$$


Que dire alors de $\mathcal{P}\left( \mathcal{P}\left( E\right) \right) $ ? Que
c'est un  ensemble \og compliqu\'{e}\fg{}, qu'il  a 256 \'{e}l\'{e}ments,
comme nous le prouverons bientôt, dont en
voici quelques uns :%

$$
\mathcal{P}\left( \mathcal{P}\left( E\right) \right) =\Bigl\{ \{\}
,\left\{ \left\{ D\right\} \right\} ,\cdots ,\left\{ \left\{ D\right\}
,\left\{ D,L\right\} \right\} ,\cdots ,\left\{ \left\{ D,L\right\} ,\left\{
D,M\right\} \right\} ,\cdots \Bigr\}
$$

On comprend tout de suite la difficult\'{e} d'imaginer l'ensemble des
parties d'un ensemble d'autant plus que les diagrammes de Venn ne peuvent
nous venir en aide.



\subsection{Construction récursive}

La remarque  qui va suivre  va nous permettre  à la fois de  compter les
éléments de $\PR(E)$ en fonction  du nombre d'éléments de E et également
de construire informatiquement l'ensemble $\PR(E)$.


Il    suffit   de   remarquer    que   si    $E=\bigl\{\bigr\}$,   alors
$\PR(E)=\Bigl\{\bigl\{\bigr\}\Bigr\}$.

Sinon, on peut écrire $E$ sous  la forme $x\oplus F$ avec $x$ un élément
quelconque de E.

$\PR(E)$  est alors  l'union de  $\PR(F)$  et des  éléments de  $\PR(F)$
auxquels on a ajouté $x$...


\section{Op\'{e}rations}

\subsection{Intersection}

\begin{definition}
L'\textbf{intersection} des ensembles $A$ et $B$ est l'ensemble $A\cap B$
constitu\'{e} des \'{e}l\'{e}ments communs \`{a} $A$ et $B.$ En d'autres
termes:%

$$
A\cap B=\Bigl\{ x\in E\mid x\in A\text{ et }x\in B\Bigr\}
$$
\end{definition}
% 

C'est une partie de $E.$ L'intersection est une\textit{ loi de composition} (ou op%
\'{e}ration) \textit{interne} dans $\mathcal{P}\left( E\right) $ qui est\textit{ associative,}
\textit{commutative} et qui admet $E$ comme \textit{\'{e}l\'{e}ment neutre} $\left( A\cap
E=A\right) $, de plus, tout \'{e}l\'{e}ment est idempotent $\left( A\cap
A=A\right) $. Lorsque $A\cap B=\{\} $ on dit que les ensembles $A$ et $%
B $ sont \textbf{disjoints}.%


% Definition of circles
\renewcommand\A{(0,0) ellipse (0.75cm and 1.25cm)}
\newcommand\B{(0:1.375cm) ellipse (1.25cm and 0.75cm)}
\newcommand\Cc{(0.75cm,0.75cm) circle (0.75cm)}
\newcommand\Uni{(-1.5,-1.5) rectangle (3,1.5)}

\colorlet{circle edge}{blue!50}
\colorlet{circle area}{blue!20}

\tikzset{filled/.style={fill=circle area, draw=circle edge, thick},
    outline/.style={draw=circle edge, thick}}

\setlength{\parskip}{5mm}
% Set A and B
\begin{center}
\begin{tikzpicture}
    \begin{scope}
        \clip \A;
        \fill[filled] \B;
    \end{scope}
     \draw \Uni ;
    \draw[outline] \A node [above left] {$A$};
    \draw[outline] \B node [below right] {$B$};
 \node[anchor=north] at (current bounding box.south) {\textcolor{blue}{$A \cap B$}};
\end{tikzpicture}
\end{center}


\begin{remarque}
On a l'\'{e}quivalence $A\cap B=B\Leftrightarrow B\subseteq A,$ en effet,
supposons en premier que $A\cap B=B,$ par d\'{e}finition $A\cap B\subseteq A$
et on obtient tout de suite $B\subseteq A.$ Supposons maintenant que $%
B\subseteq A,$ les \'{e}l\'{e}ments communs \`{a} $A$ et $B$ sont exactement
les \'{e}l\'{e}ments de $B$ et donc $A\cap B=B.$
\end{remarque}


\subsection{Union}

\begin{definition}
L'\textbf{union} ou la \textbf{r\'{e}union }des ensembles $A$ et $B$ est
l'ensemble:%
$$
A\cup B=\Bigl\{ x\in E\mid x\in A\text{ ou }x\in B\Bigr\}
$$
\end{definition}


On doit se persuader que le \og ou\fg{} intervenant dans cette d\'{e}finition est
un \og ou non exclusif\fg{} et par cons\'{e}quent on a $A\subseteq \left( A\cup
B\right) ,B\subseteq \left( A\cup B\right) $ et $\left( A\cap B\right)
\subseteq \left( A\cup B\right) .$ L'union est une loi de composition (ou op%
\'{e}ration) interne dans $\mathcal{P}\left( E\right) $ qui est associative,
commutative et qui admet $\{\} $ comme \'{e}l\'{e}ment neutre $\left(
A\cup \{\} =A\right) $, de plus tout \'{e}l\'{e}ment est idempotent $%
\left( A\cup A=A\right) $.%



\begin{center}
\begin{tikzpicture}
  \draw \Uni ;
    \draw[filled] \A node[left] {$A$}
                  \B node [right] {$B$};
    \node[anchor=north] at (current bounding box.south) {\textcolor{blue}{$A \cup B$}};
\end{tikzpicture}
\end{center}


\begin{remarque}
On a l'\'{e}quivalence $A\cup B=A\Leftrightarrow B\subseteq A$. En effet, si $%
A\cup B=A$ et comme $B\subseteq \left( A\cup B\right) $, on obtient $%
B\subseteq A.$ Si $B\subseteq A$, tout \'{e}l\'{e}ment de $B$ est aussi un 
\'{e}l\'{e}ment de $A$  donc tout \'{e}l\'{e}ment de $A\cup B$ est aussi
un \'{e}l\'{e}ment de $A$; on obtient alors $\left( A\cup B\right)
\subseteq A$ et comme $A\subseteq \left( A\cup B\right) $ on conclut que $%
A\cup B=A.$
\end{remarque}

\subsection{Différence}

\begin{definition}
La \textbf{diff\'{e}rence} des ensembles $A$ et $B$ est l'ensemble%
$$
A\setminus B=\Bigl\{ x\in E\mid x\in A\text{ et }x\notin B\Bigr\}
$$
\end{definition}



\begin{center}
\begin{tikzpicture}
    \begin{scope}
        \clip \A;
        \draw[filled, even odd rule] \A node [left]{$A$}
                                     \B;
    \end{scope}
\draw \Uni;
  \draw[outline] \A
                   \B node [right] {$B$};
    \node[anchor=north] at (current bounding box.south) {\textcolor{blue}{$A \setminus B$}};
\end{tikzpicture}
\end{center}

\begin{remarque}
Certains pr\'{e}f\`{e}rent utiliser la notation $A - B$ \`{a} la
place de $A\setminus B.$
\end{remarque}


\subsection{Différence symétrique}


\begin{definition}
La \textbf{diff\'{e}rence sym\'{e}trique} des ensembles $A$ et $B$ est
l'ensemble:%

\begin{eqnarray*}
A\bigtriangleup B &=&\Bigl\{ x\in E\mid x\in A\setminus B\text{ ou }x\in
B\setminus A\Bigr\}
=\left( A\setminus B\right) \cup \left( B\setminus A\right) \\
A\bigtriangleup B &=&\Bigl\{ x\in E\mid x\in A\cup B\text{ et }x\notin A\cap
B\Bigr\} =\left( A\cup B\right) \setminus \left( A\cap B\right)
\end{eqnarray*}
\end{definition}


\begin{center}
  \begin{tikzpicture}
\draw \Uni;
    \draw[filled, even odd rule] \A [left] node {$A$}
                                 \B [right] node{$B$};
    \node[anchor=north] at (current bounding box.south) {\textcolor{blue}{$A \bigtriangleup B$}};
\end{tikzpicture}
\end{center}



L'op\'{e}ration $\bigtriangleup $ est associative (nous d\'{e}montrons cette
affirmation plus loin), commutative, admet $\{\} $ comme \'{e}l\'{e}%
ment neutre et tout \'{e}l\'{e}ment $A$ est son propre sym\'{e}trique $%
\left( A\bigtriangleup A=\{\} \right) .$ On r\'{e}sume toutes ces propri\'{e}t%
\'{e}s en disant que $\mathcal{P}\left( E\right) $ muni de la loi $\bigtriangleup $
est un groupe\footnote{%
Les structures de groupe, anneau et corps doivent devenir pour vous des
notions famili\`{e}res mais ne peuvent faire l'objet de questions \`{a} un
DS.} commutatif. Vous pourrez v\'{e}rifier que $A\bigtriangleup B\bigtriangleup C$ peut \^{e}%
tre repr\'{e}sent\'{e} par:


\begin{center}
  \begin{tikzpicture}
\draw (-1.5,-1.5) rectangle (3,1.75);
\draw[filled, even odd rule] \A [left] node {$A$}
                               \B [right] node {$B$}
                                 \Cc [above] node{$C$};
    \node[anchor=north]     at      (current     bounding     box.south)
    {\textcolor{blue}{$A \bigtriangleup B \bigtriangleup C$}};
\end{tikzpicture}
\end{center}


\begin{remarque}
La diff\'{e}rence sym\'{e}trique correspond au \og ou exclusif\fg{}.\vspace{0.3cm}
\end{remarque}



\subsection{Complémentaire}


\begin{definition}
$A$ d\'{e}signant une partie de $E,$ le \textbf{compl\'{e}mentaire} de $A$
par rapport \`{a} $E$ ou le compl\'{e}mentaire de $A$ dans $E$ est
l'ensemble not\'{e} $\complement_{E}A$ d\'{e}fini par 
$$
\complement_{E}A=E-A=\Bigl\{ x\in E\mid x\notin A\Bigr\}
$$
\end{definition}





\begin{center}
\begin{tikzpicture}
    \begin{scope}
        \clip \Uni;
        \draw[filled, even odd rule] \Uni 
                                     \A  ;
    \end{scope}
  \draw[outline] \Uni
                   \A node {$A$};
    \node[anchor=north] at (current bounding box.south) {\textcolor{blue}{$\complement_EA$}};
\end{tikzpicture}
\end{center}



S'il n'y a pas d'ambigu\"{\i}t\'{e} sur le r\'{e}f\'{e}rentiel $E$, $%
\complement _{E}A$ est not\'{e} $\overline{A}$ et $\overline{\overline{A}}=A$.%


\subsection{Lois de \textsc{De Morgan}}

\begin{theoreme}[Lois de \textsc{De Morgan} ]
 $$ 
\overline{\left( \bigcup\limits_{i=1}^{n}A_{i}\right) }=\bigcap%
\limits_{i=1}^{n}\overline{A_{i}} \qquad \qquad\text{et}\qquad \qquad
\overline{\left( \bigcap\limits_{i=1}^{n}A_{i}\right) }=\bigcup%
\limits_{i=1}^{n}\overline{A_{i}}%
$$
\end{theoreme}


Ceci  s'exprime en fran\c{c}ais courant de la fa\c{c}on suivante:

\begin{itemize}
\item Le compl\'{e}mentaire d'une union est \'{e}gale \`{a} l'intersection
des compl\'{e}mentaires.

\item Le compl\'{e}mentaire d'une intersection est \'{e}gale \`{a} la r\'{e}%
union des compl\'{e}mentaires.
\end{itemize}

\begin{remarque}
$A-B=A\cap \overline{B}$ et $A\bigtriangleup B=\left( A\cap \overline{B}\right) \cup
\left( \overline{A}\cap B\right) .$
\end{remarque}



\subsection{Dualité}



Regroupons les  lois algébriques vues  précédemment dans un  tableau. On
considère des parties A, B et C d'un ensemble E.


\begin{center}
             \begin{tabularx}{\linewidth}{Y{1}}
	     \whline
             Idempotence & $A\cup A= A$ & $A\cap A = A$ \\
             \hline
             Associativité & $(A\cup B)\cup C=A\cup(B\cup C)$ & $(A\cap B)\cap C=A\cup(B\cap C)$\\
             \hline
             Commutativité & $A\cup B=B\cup A$& $A\cap B=B\cap A$\\
             \hline
             Distributivité & $A\cup(B\cap  C)= (A\cup B)\cap (A\cup C)$
             & $A\cap(B\cup C)= (A\cap B)\cup (A\cap C)$\\
             \hline
             Identité & $A\cup \bigl\{\bigr\}=A$ & $A\cap E= A$\\
             \hline
             Involution & $\overline{\overline{A}}=A$& \\
             \hline
             Complémentaire & $A\cup \overline{A}=E$ & $A\cap
             \overline{A}=\bigl\{\bigr\}$\\
             &                             $\overline{E}=\bigl\{\bigr\}$&
             $\overline{\bigl\{\bigr\}}=E$\\
             \hline
             De Morgan & $\overline{A\cup B} = \overline{A} \cap \overline{B}$& $\overline{A\cap B} = \overline{A} \cup \overline{B}$\\
             \whline
             \end{tabularx}
             \end{center}

Soit  $e$  une  équation  algébrique  définie  sur  $\PR(E)$.  La  duale
$e^\star$ de $e$ est l'équation  obtenue en remplaçant $\cap$, $\cup$, E
et $\bigl\{\bigr\}$  respectivement par $\cup$,  $\cap$ $\bigl\{\bigr\}$
et $E$.

Le \textit{principe  de dualité} affirme  si $e$ est vérifiée  pour tout
élément de $\PR(E)$, alors sa duale $e^\star$ aussi.



\subsection{Appartenance d'un élément à un ensemble}

Cette fonction sera très utile en programmation. On prend un élément $x$
et un ensemble en argument et on renvoie un élément de $\BR_2$.


\section{Partition d'un ensemble}


$E$ d\'{e}signant ici un ensemble non vide. Soit $P$, une partie non vide de 
$\mathcal{P}(E)$ (on a donc $P\subseteq \mathcal{P}\left( E\right) $ et $%
P\neq \emptyset )$ $P$ est un ensemble non vide de parties de $E$. On dit
que $P$ est une \textbf{partition} de $E$ si, et seulement si,

\begin{enumerate}
\item tout \'{e}l\'{e}ment de $P$ est non vide,

\item deux \'{e}l\'{e}ments distincts quelconques de $P$ sont disjoints,

\item tout \'{e}l\'{e}ment de $E$ appartient \`{a} l'un des \'{e}l\'{e}ments
de $P.$
\end{enumerate}

Si $E$ est fini toute partition $P$ de $E$ est du type $P=\left\{
A_{1},A_{2},\ldots ,A_{k}\right\} $ avec 
$$
A_{i}\subseteq E,A_{i}\neq \emptyset ,A_{i}\cap A_{j}=\emptyset \text{ si }%
i\neq j\text{ et }\bigcup\limits_{i=1}^{k}A_{i}=E
$$%


 On peut imaginer une partition de $E$ comme un d\'{e}coupage\ de $E,$ aucun
des morceaux n'\'{e}tant vide, les morceaux \'{e}tant tous disjoints deux 
\`{a} deux. Par exemple 
\begin{equation*}
\left\{ \left\{ \beta \right\} ,\left\{ \alpha ,\delta \right\} \left\{
\varepsilon ,\gamma \right\} \right\}
\end{equation*}
est une partition de l'ensemble $\left\{ \alpha ,\beta ,\gamma ,\delta
,\varepsilon \right\} .$


Pour vous distraire, voici un exercice extrait de mon livre de CE1:




%\begin{figure}
\begin{center}
  \includegraphics{CE1_partition}
\end{center}
%\end{figure}

\begin{recherche}
Ce  qui va  nous intéresser  informatiquement, c'est  une
fonction qui crée  une partition d'un ensemble selon  une propriété, par
exemple pour  regrouper les entiers  pairs parmi les  entiers de 0  à 10
dans un ensemble et les autres entiers dans un deuxième ensemble.

À vous de l'imaginer, récursivement bien sûr!
\end{recherche}

\section{Fonction caractéristique}\label{carac}


 Nous avons d\'{e}j\`{a} indiqu\'{e} quelques propri\'{e}t\'{e}s des op\'{e}%
rations que nous venons de pr\'{e}senter, le plus souvent sans d\'{e}%
monstration car ces derni\`{e}res sont assez fastidieuses lorsque, pour d%
\'{e}montrer l'\'{e}galit\'{e} de deux ensembles, il faut envisager
plein de cas. Les diagrammes de Venn peuvent nous aiguiller vers une d%
\'{e}monstration mais ne peuvent en aucun cas la remplacer. Nous allons,
ici, pr\'{e}senter un outil tr\`{e}s efficace qui permet de faire beaucoup
de d\'{e}monstrations sans trop de peine.




Soit $E$ un ensemble. Pour toute partie $A$ de $E$ on d\'{e}finit
la fonction caract\'{e}ristique $\indi{A}$ de $A$
dans $E$ par : 


$$
 \indi{A}\ \colon \begin{array}{rll} E & \to & \bigl\{0;1\bigr\}\\
   x & \mapsto &
   \begin{cases}
     1\quad \text{ si } x\in A\\
     0\quad \text{ si } x\not\in A
   \end{cases}
 \end{array}
 $$





Une propri\'{e}t\'{e} essentielle de cette notion est donn\'{e}e par l'\'{e}%
quivalence%
$$
\indi{A}=\indi{B}\Longleftrightarrow A=B
$$


 Vous ne voyez peut-être pas trop où se trouve la simplification!

   Un   informaticien   utilise   un   \og   \textit{computer}\fg{},
c'est-à-dire    un    calculateur.    Nous   voudrons    donc    pouvoir
\textit{calculer} avec des ensembles.


\begin{notation}
Pour simplifier  les écritures, nous utiliserons des  opérations sur ces
applications caractéristiques:

\begin{itemize}
\item $\indi{A}.\indi{B}$ ou $\indi{A}\indi{B}$ d\'{e}finie pour tout $x$ de $E$ par $\left( \indi{A}\indi{B}\right) \left( x\right) =\indi{A}\left( x\right)\times \indi{B}\left( x\right)$;

\item  $1-\indi{A}$ d\'{e}finie par $\left( 1-\indi{A}\right) \left( x\right) =1-\indi{A}\left( x\right) $;

 \item  $\indi{A}+ \indi{B}$ d\'{e}finie par $\left( \indi{A}+ \indi{B}\right) \left( x\right) =\indi{A}\left( x\right) + \indi{B}\left( x\right) .$
\end{itemize}
\end{notation}



On voudrait maintenant exprimer $\indi{\overline{A}},$ 
$\indi{A\cap B},$ $\indi{A-B},$ $\indi{A\cup B}$ et $\indi{A\bigtriangleup B}$
\`{a} l'aide de $\indi{A}$ et de $\indi{B}$.

Je vous donne un coup de main:

\begin{itemize}
\item $\indi{\overline{A}}=1-\indi{A},$ c'est \'{e}vident, ces deux
applications co\"{\i}ncident sur $E.$

\item $\indi{A\cap B}=\indi{A}\indi{B},$ c'est tout aussi \'{e}%
vident, elles co\"{\i}ncident sur $E$ ; on en d\'{e}duit que $\indi{A\cap A}=\indi{A}\indi{A}=\indi{A}.$

\item $\indi{A-B}=\indi{A}-\indi{A}\indi{B}.$ On peut le d%
\'{e}montrer en v\'{e}rifiant la co\"{\i}ncidence de ces deux applications
sur $E$ mais il est plus judicieux de remarquer que $A-B=A\cap \overline{B}$
et du coup%
$$
\indi{A-B}=\indi{A\cap \overline{B}}=\indi{A}\indi{\overline{%
B}}=\indi{A}\left( 1-\indi{B}\right) =\indi{A}-\indi{A}\indi{B}
$$

\item Concernant $\indi{A\cup B},$ pour trouver une formule similaire
aux pr\'{e}c\'{e}dentes, il faut faire preuve d'un peu d'imagination : nous
utilisons le r\'{e}sultat\footnote{%
C'est une des formules de De Morgan.} $\overline{X\cup Y}=\overline{X}\cap 
\overline{Y}$ que nous d\'{e}montrons \`{a} l'aide du tableau suivant%
$$
\begin{tabular}{|c|c|c|c|}
\hline
$x\in X$ & $x\in Y$ & $x\in \overline{X\cup Y}$ & $\overset{}{x\in \overline{%
X}\cap \overline{Y}}$ \\ \hline
non & non & oui & oui \\ \hline
non & oui & non & non \\ \hline
oui & non & non & non \\ \hline
oui & oui & non & non \\ \hline
\end{tabular}%
\medskip
$$%
\smallskip Ceci \'{e}tant, $A\cup B=\overline{\overline{A\cup B}}=\overline{%
\overline{A}\cap \overline{B}}$ ; on obtient alors 
$$
\indi{A\cup B}=\indi{\overline{\overline{A}\cap \overline{B}}%
}=1-\indi{\overline{A}\cap \overline{B}}
$$%
soit $\indi{A\cup B}=1-\left( 1-\indi{A}\right) \left( 1-\indi{B}\right) $ qui se d\'{e}veloppe en 
$$
\indi{A\cup B}=\indi{A}+\indi{B}-\indi{A}\indi{B}
$$

\item
 Pour $\indi{A\bigtriangleup B}$ je vous laisse prouver que : $\indi{A\bigtriangleup
B}=\indi{A}+\indi{B}-2\indi{A}\indi{B}$.

\end{itemize}






\begin{recherche}
Voici quelques propri\'{e}t\'{e}s (en vrac) importantes qu'il faut conna%
\^{\i}tre, certaines sont \'{e}videntes et d'autres pas, nous reprenons des r%
\'{e}sultats d\'{e}j\`{a} \'{e}nonc\'{e}s et nous ne donnons que quelques d%
\'{e}monstrations, le lecteur \'{e}tant invit\'{e} \`{a} les reprendre et 
\`{a} en faire d'autres. Il doit \^{e}tre clair que tous les ensembles utilis%
\'{e}s sont des parties de l'ensemble $E$ !
\end{recherche}




\begin{itemize}
\item $\cup $ et $\cap $ sont associatives et commutatives. D\'{e}montrons
l'associativit\'{e} de l'inter\-section. Pour cela choisissons trois parties
quelconques $A,$ $B$ et $C$ de $\mathcal{P}\left( E\right) .$ Il nous faut d%
\'{e}montrer l'\'{e}galit\'{e} des ensembles $U=A\cap \left( B\cap C\right) $
et $V=\left( A\cap B\right) \cap C$ et pour cela il suffit de prouver l'\'{e}%
galit\'{e} des applications caract\'{e}ristiques de $U$ et $V$ dans $E.$
Allons-y : $\indi{U}=\indi{A\cap \left( B\cap C\right) }=\indi{A}\indi{B\cap C}=\indi{A}\indi{B}\indi{C}=\indi{A\cap
B}\indi{C}=\indi{V}.$ L'associativit\'{e} de $\cap $ et $\cup $
permet d'utiliser les notations, lorsque $k\mathbb{\in N}^{\ast },$%
 $$
\begin{array}{l}
\bigcup\limits_{i=1}^{k}A_{i}=A_{1}\cup A_{2}\cup \ldots \cup A_{n} \\ 
\bigcap\limits_{i=1}^{k}A_{i}=A_{1}\cap A_{2}\cap \ldots \cap A_{n}%
\end{array}%
$$

\item $A\subseteq B\Longleftrightarrow A\cup B=B\Longleftrightarrow A\cap
B=A\Longleftrightarrow A-B=\{\} $

\item $A\subseteq (A\cup B),(A\cap B)\subseteq A$

\item $A-A=A\bigtriangleup A=A\cap \{\} =\{\} $

\item $A\cap A=A\cup A=A\cup \{\} =A\cap E=A\bigtriangleup \{\} =A$

\item $A\cap \left( A\cup B\right) =A=A\cup \left( A\cap B\right) $

\item $\overline{\left( \overline{A}\right) }=A,\overline{A}\cap A=\{\}
,\overline{A}\cup A=E,\complement _{E}\{\} =\overline{\{\} }%
=E,\complement _{E}E=\overline{E}=\{\} $

\item $\cap $ et $\cup $ sont distributives l'une par rapport \`{a} l'autre :%

\begin{eqnarray*}
A\cap \left( B\cup C\right) &=&\left( A\cap B\right) \cup \left( A\cap
C\right) \\
A\cup \left( B\cap C\right) &=&\left( A\cup B\right) \cap \left( A\cup
C\right)
\end{eqnarray*}%


La d\'{e}monstration se fait, soit en v\'{e}rifiant la double inclusion
(c'est un bon exercice), soit en utilisant les applications caract\'{e}%
ristiques.

\item La diff\'{e}rence sym\'{e}trique est associative et commutative. D\'{e}%
montrons l'associa\-tivit\'{e} toujours \`{a} l'aide des applications caract%
\'{e}ristiques :%
 $$
\indi{A\bigtriangleup \left( B\bigtriangleup C\right) }=\indi{A}+\indi{B\bigtriangleup
C}-2\indi{A}\indi{B\bigtriangleup C}\text{ avec }\indi{B\bigtriangleup
C}=\indi{B}+\indi{C}-2\indi{B}\indi{C}
$$%
donne%
 $$
\indi{A\bigtriangleup \left( B\bigtriangleup C\right) }=\indi{A}+\indi{B}+\indi{C}-2\indi{A}\indi{B}-2\indi{A}\indi{C}-2\indi{B}\indi{C}+4\indi{A}\indi{B}\indi{C}
$$%
On v\'{e}rifie que $\indi{\left( A\bigtriangleup B\right) \bigtriangleup C}$ s'exprime
de la m\^{e}me fa\c{c}on.

\item Rappelons les lois de De Morgan%
 $$
\left\{ 
\begin{array}{l}
\overline{\left( \bigcup\limits_{i=1}^{n}A_{i}\right) }=\bigcap%
\limits_{i=1}^{n}\overline{A_{i}} \\ 
\overline{\left( \bigcap\limits_{i=1}^{n}A_{i}\right) }=\bigcup%
\limits_{i=1}^{n}\overline{A_{i}}%
\end{array}%
\right.
$$%
Nous avons d\'{e}j\`{a} d\'{e}montr\'{e} $\overline{A_{1}\cup A_{2}}=%
\overline{A_{1}}\cap \overline{A_{2}},$ pour d\'{e}montrer%
 $$
\overline{\left( \bigcup\limits_{i=1}^{n}A_{i}\right) }=\bigcap%
\limits_{i=1}^{n}\overline{A_{i}}
$$%
une r\'{e}currence imm\'{e}diate suffit :%
 $$
\overline{\left( \bigcup\limits_{i=1}^{n+1}A_{i}\right) }=\overline{\left(
\left( \bigcup\limits_{i=1}^{n}A_{i}\right) \cup A_{n+1}\right) }=\overline{%
\left( \bigcup\limits_{i=1}^{n}A_{i}\right) }\cap \overline{A}_{n+1}=\left(
\bigcap\limits_{i=1}^{n}\overline{A_{i}}\right) \cap \overline{A}_{n+1}
$$%
et l'associativit\'{e} de l'intersection permet de conclure. Dans la formule%
 $$
\overline{\left( \bigcup\limits_{i=1}^{n}A_{i}\right) }=\bigcap%
\limits_{i=1}^{n}\overline{A_{i}}
$$%
rempla\c{c}ons chaque $A_{i}$ par $\overline{A_{i}}$ :%
 $$
\overline{\left( \bigcup\limits_{i=1}^{n}\overline{A_{i}}\right) }%
=\bigcap\limits_{i=1}^{n}\overline{\overline{A_{i}}}=\bigcap A_{i}
$$%
et en \'{e}crivant l'\'{e}galit\'{e} des compl\'{e}mentaires de chaque
membre il vient 
 $$
\overline{\left( \bigcap\limits_{i=1}^{n}A_{i}\right) }=\bigcup%
\limits_{i=1}^{n}\overline{A_{i}}
$$
\end{itemize}







\begin{remarque}
  L'intérêt    des   fonctions    caractéristiques   est    de   pouvoir
  effectuer des calculs sur des  ensembles comme avec les nombres ce qui
  facilite la programmation des opérations ensemblistes..
\end{remarque}

\section{Produit cartésien}

Cette partie  va nous  permettre d'introduire des  notions informatiques
fondamentales, notamment dans le traitement des bases de données.

 Vous êtes embauché(e) dans un restaurant. Vous disposez de
trois ensembles:

\begin{itemize}
\item l'ensemble des entrées: $$E=\bigl\{\text{Cuisses de sauterelles panées}, \text{ \oe uf mou},
  \text{ huîtres de l'Erdre}\bigr\}$$
\item  l'ensemble  des   plats  de  résistance:  $$P=\bigl\{\text{Turbot  à
    l'huile  de  ricin},  \text{  Chien  à  l'andalouse},  \text{  Soupe
    d'orties}\bigr\}$$
\item l'ensemble des desserts: $$D=\bigl\{\text{Pomme}, \text{Banane}, \text{Noix}\bigr\}$$
\end{itemize}


Vous  avez  envie   de  créer  un  nouvel  ensemble,   celui  des  menus
possibles. Une première idée consiste à regrouper tout le monde en
prenant $E\cup P \cup D$.

  Je  sais   bien  que  la  gastronomie  n'est   pas  la  principale
préoccupation des jeunes au  palet perverti par les tristes fastefoudes
mais en général  on commande UNE entrée SUIVIE  D'UN plat de résistance
SUIVI D'UN dessert  or la simple union que vous  avez proposée peut vous
faire choisir un menu 
totalement  différent: cinq  desserts et  vingt entrées,  dans n'importe
quel ordre, par exemple.

Nous  avons  besoin  de  créer   un  \og  objet\fg{}  ordonné  de  trois
composantes, chacune étant choisie respectivement dans $E$, $P$ et $D$.

Par exemple, (\oe uf mou, chien à l'andalouse, pomme) est un menu. C'est
un  triplet, à  ne pas  confondre avec  l'ensemble $\bigl\{$\oe  uf mou,
chien à l'andalouse, pomme $\bigr\}$ qui n'est pas ordonné.







Généralisons sans trop entrer dans les détails. La
notion de couple se g\'{e}n\'{e}ralise naturellement en notion de triplet,
de quadruplet,\ldots , de $n$-uplet, un $n$-uplet \'{e}tant not\'{e} $%
\underset{n\text{ \'{e}l\'{e}ments}}{\underbrace{\left( a_{1},a_{2},\cdots
,a_{n}\right) }}.$ L'\'{e}galit\'{e} de deux $n$-uplets \'{e}tant d\'{e}%
finie par%
$$
\bigl( a_{1},a_{2},\cdots ,a_{n}\bigr) =\left( a_{1}^{\prime
},a_{2}^{\prime },\cdots ,a_{n}^{\prime }\right) \Leftrightarrow
a_{i}=a_{i}^{\prime }\text{ pour tout }i
$$

$E_{1}$ et $E_{2}$ d\'{e}signant deux ensembles, nous admettons que
l'ensemble des couples $\left( a_{1},a_{2}\right) $ avec $a_{1}\in E_{1}$ et 
$a_{2}\in E_{2}$ est bien un ensemble que l'on note $E_{1}\times E_{2}$ appel%
\'{e} \textbf{produit cart\'{e}sien} des ensembles $E_{1}$ et $E_{2}$, une 
\'{e}criture en pseudo compr\'{e}hension \'{e}tant%

$$
E_{1}\times E_{2}=\bigl\{ \left( a_{1},a_{2}\right) \mid a_{1}\in E_{1}\text{
et }a_{2}\in E_{2}\bigr\}
$$

On d\'{e}finit de m\^{e}me le produit cart\'{e}sien des $n$ ensembles $%
\left( n\in \mathbb{N}^{\ast }\text{ et }n\geq 2\right) $ $E_{i\in \left\{
1,2,3,\cdots ,n\right\} }$ comme \'{e}tant l'ensemble :%

$$
E_{1}\times E_{2}\times \cdots \times
E_{n}=\prod\limits_{i=1}^{n}E_{i}=\bigl\{ \left( a_{1},a_{2},\cdots
,a_{n}\right) \mid a_{i}\in E_{i}\bigr\}
$$

et lorsque tous les ensembles $E_{i}$ sont \'{e}gaux \`{a} $E$ on note $%
E\times E\times \cdots \times E$ par $E^{n}.$

Pour se repr\'{e}senter le produit cart\'{e}sien $E\times F$ avec $%
E=\left\{ a,b,c\right\} $ et $F=\left\{ 1,2,3,4,5\right\} ,$ on peut \'{e}%
videmment l'\'{e}crire en extension: il poss\`{e}de $3\times 5=15$ \'{e}l%
\'{e}ments (voir \`{a} ce sujet le paragraphe suivant).%


$$
E\times F=\bigl\{ \left( a,1\right) ,\left( a,2\right) ,\cdots ,\left(
c,5\right) \bigr\}
$$


mais il est souvent pr\'{e}f\'{e}rable de faire appel \`{a} un tableau du
type suivant :%
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
$\times $ & $\bm{1}$ & $\bm{2}$ & $\bm{3}$ & $\bm{4}$ & $%
\bm{5}$ \\ \hline
$\bm{a}$ & $\left( a,1\right) $ & $\left( a,2\right) $ & $\left(
a,3\right) $ & $\left( a,4\right) $ & $\left( a,5\right) $ \\ \hline
$\bm{b}$ & $\left( b,2\right) $ & $\left( b,2\right) $ & $\left(
b,3\right) $ & $\left( b,4\right) $ & $\left( b,5\right) $ \\ \hline
$\bm{c}$ & $\left( c,1\right) $ & $\left( c,2\right) $ & $\left(
c,3\right) $ & $\left( c,4\right) $ & $\left( c,5\right) $ \\ \hline
\end{tabular}%
\end{center}


Avec notre menu, il faudrait un tableau en 3D! 

 On utilise plutôt dans ce cas un arbre:

\tikzstyle{lien}=[->,>=stealth,rounded corners=5pt,thick]
\tikzset{individu/.style={draw,thick,fill=#1!25},
individu/.default={green}}

{\footnotesize

\begin{tikzpicture}
[level 1/.style={sibling distance=4.5cm},
level 2/.style={sibling distance=1.5cm},
level 3/.style={sibling distance=0.4cm}]
\node [individu=gray] {Menus}
child{ node [individu=blue]{Cuisses}
       child{ node [individu=red]{Turbot}
            child{ node [individu=green]{P}
                 }
            child{ node [individu=green]{B}
                 }
            child{ node [individu=green]{N}
                 }
            }
       child{ node [individu=red]{Chien}
            child{ node [individu=green]{P}
                 }
            child{ node [individu=green]{B}
                 }
            child{ node [individu=green]{N}
                 }
            }
       child{ node [individu=red]{Soupe}
            child{ node [individu=green]{P}
                 }
            child{ node [individu=green]{B}
                 }
            child{ node [individu=green]{N}
                 }
            }
     }
child{ node [individu=blue]{\OE uf}
       child{ node [individu=red]{Turbot}
            child{ node [individu=green]{P}
                 }
            child{ node [individu=green]{B}
                 }
            child{ node [individu=green]{N}
                 }
            }
       child{ node [individu=red]{Chien}
            child{ node [individu=green]{P}
                 }
            child{ node [individu=green]{B}
                 }
            child{ node [individu=green]{N}
                 }
            }
       child{ node [individu=red]{Soupe}
            child{ node [individu=green]{P}
                 }
            child{ node [individu=green]{B}
                 }
            child{ node [individu=green]{N}
                 }
            }
     }
child{ node [individu=blue]{Huîtres}
       child{ node [individu=red]{Turbot}
            child{ node [individu=green]{P}
                 }
            child{ node [individu=green]{B}
                 }
            child{ node [individu=green]{N}
                 }
            }
       child{ node [individu=red]{Chien}
            child{ node [individu=green]{P}
                 }
            child{ node [individu=green]{B}
                 }
            child{ node [individu=green]{N}
                 }
            }
       child{ node [individu=red]{Soupe}
            child{ node [individu=green]{P}
                 }
            child{ node [individu=green]{B}
                 }
            child{ node [individu=green]{N}
                 }
            }
     };
\end{tikzpicture}


}

Un menu  est donc  un triplet  élément de $E\times  P\times D$.  On peut
ensuite  s'intéresser  aux menus  végétariens,  aux  menus sans  viande,
etc. Nous nous intéresserons par la  suite à la manière de les extraire,
de les compter, etc.


\begin{recherche}
  Comment définir  récursivement le produit cartésien  de deux ensembles
  $E_1$ et $E_2$? Cela nous sera utile pour programmer en \textsc{Caml}...
\end{recherche}



% \begin{extra}

% \`{A} partir de deux \'{e}l\'{e}ments $a$ et $b,$ non n\'{e}cessairement
% distincts, on peut construire les deux ensembles suivants :

% \begin{enumerate}
% \item La paire $\left\{ a,b\right\} =\left\{ b,a\right\} $ qui se transforme
% en le singleton $\left\{ a\right\} $ si $a=b$ (nous avons d\'{e}j\`{a} signal%
% \'{e} que l'\'{e}criture fautive $\left\{ a,a\right\} $ d\'{e}signe le
% singleton $\left\{ a\right\} ).$

% \item La paire $\left\{ \left\{ a\right\} ,\left\{ a,b\right\} \right\} $
% qui se transforme, si $a=b,$ en le singleton 
% $$
% \left\{ \left\{ a\right\} ,\left\{ a,a\right\} \right\} =\left\{ \left\{
% a\right\} ,\left\{ a\right\} \right\} =\left\{ \left\{ a\right\} \right\}
% $$
% \end{enumerate}

% Si $a\neq b$ les deux paires $\left\{ \left\{ a\right\} ,\left\{ a,b\right\}
% \right\} $ et $\left\{ \left\{ b\right\} ,\left\{ a,b\right\} \right\} $
% sont distinctes, cette \'{e}criture permet de d\'{e}finir un ordre car pour
% chacune de ces paires un seul \'{e}l\'{e}ment est inclus dans l'autre. Nous d%
% \'{e}cidons de noter une telle paire $\left\{ \left\{ a\right\} ,\left\{
% a,b\right\} \right\} $ par $\left( a,b\right) $ ou $\left( a;b\right) $ appel%
% \'{e} couple, le couple $\left( a,a\right) $ d\'{e}signant l'ensemble $%
% \left\{ \left\{ a\right\} \right\} .$ Cette d\'{e}finition compliqu\'{e}e
% d'un couple permet de s'assurer que l'ensemble de tels couples est bien un
% ensemble et nous donne les r\'{e}sultats indispensables suivants :

% \begin{enumerate}
% \item Nous avons d\'{e}j\`{a} indiqu\'{e} que si $a=b,$ le couple $\left(
% a,b\right) =\left( a,a\right) $ est le singleton $\left\{ \left\{ a\right\}
% \right\} .$ R\'{e}ciproquement si le couple $\left( a,b\right) =\left\{
% \left\{ a\right\} ,\left\{ a,b\right\} \right\} $ est un singleton c'est que 
% $\left\{ a\right\} =\left\{ a,b\right\} $ et qu'en cons\'{e}quence $b\in
% \left\{ a\right\} $ soit $b=a.$

% \item Pour que les deux couples $\left( a,b\right) $ et $\left( c,d\right) $
% soient \'{e}gaux, il faut et il suffit que $a=c$ et $b=d.$ D\'{e}montrons-le
% : $\left( a,b\right) =\left\{ \left\{ a\right\} ,\left\{ a,b\right\}
% \right\} $ et $\left( c,d\right) =\left\{ \left\{ c\right\} ,\left\{
% c,d\right\} \right\} ,$ si $a=b$ le couple $\left( a,a\right) =\left\{
% \left\{ a\right\} \right\} $ est un sigleton et par cons\'{e}quent le couple 
% $\left( c,d\right) $ aussi ; on en d\'{e}duit que $c=d$ et $\left(
% a,a\right) =\left( c,c\right) =\left\{ \left\{ a\right\} \right\} =\left\{
% \left\{ c\right\} \right\} $ donnent $a=c.$ Si $a\neq b$ n\'{e}cessairement $%
% a=c$ et $\left\{ a,b\right\} =\left\{ c,d\right\} $ et comme $b$ ne peut 
% \^{e}tre \'{e}gal \`{a} $c$ sinon on aurait $a=b,$ on obtient $b=d.$
% \end{enumerate}

% On d\'{e}finit le triplet $\left( a,b,c\right) $ comme l'ensemble $\left\{
% \left\{ a\right\} \left\{ a,b\right\} \left\{ a,b,c\right\} \right\} $, etc.
% \end{extra}


\section{Notion de cardinal}\label{cardinal}

  Le  cardinal  d'un  ensemble,  c'est  en gros  le  nombre  de  ses
éléments.  La notion  de cardinal  est intimement  liée à  la  notion de
fonction  et   à  l'ensemble  $\bm{N}$  des  entiers   naturels  que  nous
détaillerons  plus tard. Nous  nous contenterons  dans un  premier temps
d'une approche intuitive. 
 Le cardinal de $E$
est indiff\'{e}remment not\'{e}:%

$$
\card\left( E\right) \text{ ou }\left\vert E\right\vert \text{ ou }%
\#E
$$
Par exemple $\left\vert \emptyset \right\vert =0,$ cette notation ne devra
bien s\^{u}r pas \^{e}tre confondue avec la valeur absolue d'un r\'{e}el ou
bien le module d'un nombre complexe. Quoi qu'il en soit, le contexte
permettra g\'{e}n\'{e}ralement de lever l'ambigu\"{\i}t\'{e}.





Nous admettons les r\'{e}sulats suivants qui ne concernent que des ensembles 
\textbf{finis}:


\begin{proprietes}
  \begin{itemize}
  \item Si $A\subseteq B$ alors $\bigl| A\bigr| \leq \bigl| B\bigr| .$ Une cons\'{e}quence int\'{e}ressante est celle ci
: si $A\subseteq B$ avec $\bigl| A\bigr| =\bigl| B\bigr| $ alors $A=B.$

\item $\bigl| A-B\bigr| \leq \bigl| A\bigr| .$

\item $\bigl| A\cup B\bigr| =\bigl| A\bigr| +%
\bigl| B\bigr| -\bigl| A\cap B\bigr| $

\item \textbf{Si on a} $E_{i}\cap E_{j}=\emptyset $ \textbf{lorsque} $i\neq
j,$ alors $\left| \bigcup\limits_{i=1}^{n}E_{i}\right|
=\sum\limits_{i=1}^{n}\bigl| E_{i}\bigr| $.

\item $\bigl| E_{1}\times E_{2}\bigr| =\bigl|
E_{1}\bigr| .\bigl| E_{2}\bigr| $ et 
\begin{eqnarray*}
\bigl| E_{1}\times E_{2}\times \cdots \times E_{n}\bigr| &=&%
\bigl| E_{1}\bigr| .\bigl| E_{2}\bigr| .\cdots
.\bigl| E_{n}\bigr| \\
\bigl| E^{n}\bigr| &=&\bigl( | E|
\bigr) ^{n}
\end{eqnarray*}

\item La formule suivante est absolument \`{a} conna\^{\i}tre :%
$$
\bigl| \mathcal{P}\left( E\right) \bigr| =2^{| E| }
$$
Nous la d\'{e}montrerons en exercice.
  \end{itemize}
\end{proprietes}



\begin{recherche}
  Comment calculer récursivement le cardinal d'un ensemble?
\end{recherche}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\modeexercice % entre en mode exercice
\section{EXERCICES}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\small
%\begin{listeexercices}


\subsection{Papier - crayon}

  \begin{exercice}
    Parmi les ensembles suivants, quels sont ceux qui sont égaux?
    \begin{multicols}{2}
\begin{enumerate}
\item $A=\bigl\{x\mid x\in \bbr \text{ et } x^2-4x+3=0\bigr\}$
\item $B=\bigl\{x\mid x\in\bbr \text{ et } x^2-3x+2=0\bigr\}$
\item $C=\bigl\{x\mid x\in\bbn \text{ et } x<3 \bigr\}$
\item $D=\bigl\{x\mid x\in\bbn  \text{ et } x<5 \text{  et }x \text{ est
      impair }\bigr\}$
\item $E=\bigl\{1,2\bigr\}$
\item $F=\bigl\{1,2,1\bigr\}$
\item $G=\bigl\{3,1\bigr\}$
\item $H=\bigl\{1,1,3\bigr\}$
\end{enumerate} 
\end{multicols}
  \end{exercice}

%


\begin{exercice}
$E=\left\{ 0,1,2,3,4,5,6\right\} .$ D\'{e}finir en extension les ensembles
suivants :
 \begin{multicols}{3}
\begin{enumerate}
\item $A_{1}=\left\{ x\in \mathbb{N}\mid x^{2}\in E\right\} $

\item $A_{2}=\left\{ x\in \mathbb{R}\mid x^{2}\in E\right\} $

\item $A_{3}=\left\{ x\in E\mid x^{2}\in E\right\} $

\item $A_{4}=\left\{ x\in E\mid \sqrt{x}\in E\right\} $

\item $A_{5}=\left\{ x\in E\mid 2x\in E\right\} $

\item $A_{6}=\left\{ x\in E\mid \frac{x}{2}\in E\right\} $
\end{enumerate}
\end{multicols}
\end{exercice}

%




\begin{exercice}
$E=\left\{ 0,1,2,3,4\right\} .$ Compl\'{e}ter, lorsque c'est possible, par
un des symboles (il peut y avoir plusieurs solutions, mais on s'obligera 
\`{a} choisir celle qui donne le plus \og de renseignements\fg{}): 
$$
\in ,\ni ,\subseteq ,\supseteq ,=,\neq ,\varsubsetneq
,\cdots$$



 $2\cdots E,$ $\left\{ 2,3\right\} \cdots E,$ $\left\{ 2\right\} \cdots
E$

 $\left\{ 2,3,4\right\} \cdots \left\{ 4,3,2\right\} ,$ $\left\{
2,3,4\right\} \cdots \left\{ 4,3,0\right\} $

 $\{\}  \cdots E,$ $E\cdots E,$ $E\cdots \left\{ E\right\} ,$ $%
\{\}  \cdots \left\{ E\right\} $

 $E\cdots \left\{ 0,1,2,3,\ldots ,10\right\} ,$ $\left\{
0,1,2,3,4,5\right\} \cdots E$



\end{exercice}






%


  \begin{exercice}
    Soit    $A=\bigl\{1,2,...,8,9\bigr\}$,    $B=\bigl\{2,4,6,8\bigr\}$,
    $C=\bigl\{1,3,5,7,9\bigr\}$,        $D=\bigl\{3,4,5\bigr\}$,
    $E=\bigl\{3,5\bigr\}$ et $\Omega=\bigl\{A,B,C,D,E\bigr\}$.

Écrivez les ensembles suivants en extension de manière formelle puis Déterminez les éléments de $\Omega$ qui vérifient les conditions suivantes:

\begin{multicols}{4}
  \begin{enumerate}
  \item X et B sont disjoints;
  \item $X\subseteq D$ et $X\not\subseteq B$;
  \item $X\subseteq A$ et $X\not\subseteq C$;
  \item $X\subseteq C$ et $X\not\subseteq A$.
  \end{enumerate}
  
\end{multicols}



  \end{exercice}

%



  \begin{exercice}
Simplifiez au maximum les égalités suivantes:
\begin{multicols}{2}
\begin{enumerate}
\item $(A\cap B)\cup(A\cap \overline{B})$
\item $(A \cap \overline{B})\cup(\overline{A}\cap B)\cup(A\cap B)$
\end{enumerate}
\end{multicols}
\end{exercice}

%

\begin{exercice}
On considère les parties de $\bbn$ suivantes:
$A=\bigl\{n\mid  n \leqslant  6\bigr\}$, $B=\bigl\{n\mid  4  \leqslant n
\leqslant        9\bigr\}$,        $C=\bigl\{1,3,5,7,9\bigr\}$        et
$D=\bigl\{2,3,5,7,8\bigr\}$. Déterminez:
\begin{multicols}{4}
  \begin{enumerate}
  \item $A\Delta B$
\item $B\Delta C$
\item $A\cap(B\Delta D)$
\item $(A\cap B)\Delta(A\cap D)$
  \end{enumerate}
\end{multicols}
\end{exercice}

%





\begin{exercice}
On définit un opérateur $\nand$ sur les ensembles de la manière
suivante:
$$
A \nand B = \overline{(A \cap B)}
$$
Démontrer les égalités suivantes:

\begin{enumerate}
\item $A \nand A = \overline{A}$;
\item $(A \nand A)  \nand (B \nand B) =A \cup
  B$;
\item  $(A \nand  B) \nand  (A \nand  B)  = A
  \ ???\ B$.
\item $\nand$ est-il associatif?
\end{enumerate}

\end{exercice}



%


\begin{exercice}
  Démontrer que  la différence symétrique  est commutative, associative,
  simplifiable à gauche (si $A\Delta B=A\Delta C$ alors $B=C$) et 
  que l'intersection est distributive sur la différence symétrique.
\end{exercice}

%




\begin{exercice}
  Expliciter $\mathcal{P}(\mathbb{N}_{n})$ pour pour $n\in \left\{
1,2,3\right\}$.         On          rappelle         la         notation
$\mathbb{N}_{n}=\left\{ 1,2,3,...,n\right\}= \llbracket 1,n\rrbracket.$
\end{exercice}


%

\begin{exercice}
Expliciter $\mathcal{P}\left( \left\{ a,\left\{ a\right\} \right\} \right) .$
\end{exercice}

%

\begin{exercice}
Expliciter $\mathcal{P}(\{\} ),$ $\mathcal{P}\left( \mathcal{P}%
(\{\} )\right) .$
\end{exercice}

%

\begin{exercice}
Expliciter $\mathcal{P}\left( \mathcal{P}(\mathbb{N}_{2})\right) .$
\end{exercice}

%

\begin{exercice}
Donner cinq \'{e}l\'{e}ments de $\mathcal{P}\left( \mathcal{P}\left( 
\mathcal{P}\left( \left\{ a,b,c\right\} \right) \right) \right) .$
\end{exercice}

%

\begin{exercice}
D\'{e}montrer par r\'{e}currence que si 
$E$ possède $n$ \'{e}l\'{e}ments alors $\mathcal{P}(E)$ poss\`{e}de $2^{n}$ \'{e}l\'{e}ments.

\end{exercice}

%

\begin{exercice}
Combien d'\'{e}l\'{e}ments $\mathcal{P}\left( \mathcal{P}\left( \mathcal{P}%
\left( \left\{ a,b,c\right\} \right) \right) \right) $ contient-il ?
\end{exercice}



%

\begin{exercice}
  \begin{enumerate}
  \item  Soit  $A=\bigl\{0,1\bigr\}$.  Déterminer  $\left(A^2\setminus
        \bigl\{(0,0)\bigr\}\right)\times A$.
    \item            Soit           $A=\bigl\{3,5,7\bigr\}$           et
          $B=\bigl\{a,b\bigr\}$. Déterminer $A^2$, $B^2$, $A\times B$,
          $B\times A$, $B^2\times A$.
  \end{enumerate}
\end{exercice}



%


\begin{exercice}
$A=\left\{ 0,1,2,3\right\} ,$ $B=\left\{ a,b\right\} $ et $C=\left\{
1,2\right\} .$ Donner quelques \'{e}l\'{e}ments de:

\begin{enumerate}
\item $A\times B,$ $\left( A\times B\right) \times C,A\times B\times C,$ $%
A\times \left( B\times C\right) ,$ $C\times \left( A\cup B\right) ,$ $A^{5}$

\item $\mathcal{P}(A)\times \mathcal{P}(B)$

\item $\mathcal{P}(A\times B)$

\item $\{\}  \times A,$ $A\times \left( \{\}  \times B\right) ,$ $%
\left\{ \{\}  \right\} \times B$
\end{enumerate}
\end{exercice}

%



\begin{exercice}
  $A$, $B$ et $C$ sont trois ensembles tous diff\'{e}rents de l'ensemble vide.
D\'{e}montrer que $$\left( A\cap B\right) \times C=\left( A\times C\right)
\cap \left( B\times C\right) .$$
\end{exercice}


%


\begin{exercice}
  $E=\left\{ a,b,c,d,e\right\} $


\begin{enumerate}
\item {Donner 4 partitions de }$E$\textit{.}

\item {Vrai ou Faux , }$\left\{ \{\}  ,\left\{ a\right\} ,\left\{
b,c,e\right\} ,\left\{ d\right\} \right\} ${ est une partition de }$%
E.$

\item {Vrai ou Faux , }$\left\{ \left\{ a\right\} ,\left\{
b,c\right\} ,\left\{ d\right\} \right\} ${\ est une partition de }$E.$
\end{enumerate}


\end{exercice}

%



\begin{exercice}
  \begin{enumerate}
  \item On pose $A=\bigl\{a,b\bigr\}$ et $B=\bigl\{b,c\bigr\}$.
    \begin{enumerate}
    \item Comparer $\PR(A)\cap \PR(B)$ et $\PR(A\cap B)$.
    \item Comparer $\PR(A)\cup \PR(B)$ et $\PR(A\cup B)$.
    \end{enumerate}
  \item Répondre aux mêmes questions avec A et B des ensembles quelconques.
  \end{enumerate}
\end{exercice}

\subsection{Avec \textsc{Caml}}

On rappelle que l'on part d'un type construit:

\begin{lstlisting}[caption={}]
type 'a ens =
  | Vide 
  | Ens of ('a * 'a ens);;
\end{lstlisting}


et donc que l'ensemble $e=\bigl\{1,2,3\bigr\}$ se construit ainsi:

\begin{lstlisting}[caption={}]
# let e = Ens(3,Ens(2,Ens(1,Vide)));;
val e : int ens = Ens (3, Ens (2, Ens (1, Vide)))
\end{lstlisting}

et l'on peut construire $\bigl\{1,2,3,4\bigr\}$ à partir de $e$:

\begin{lstlisting}[caption={}]
# Ens(4,e);;
- : int ens = Ens (4, Ens (3, Ens (2, Ens (1, Vide))))
\end{lstlisting}



Nous  (vous...) allons  (allez...) construire  différentes  fonctions en
rapport avec le cours.


Dans ma  grande bonté, je vous  donne un premier  exemple d'une fonction
fondamentale:  celle qui  va  tester l'appartenance  d'un  élément à  un
ensemble.


Nous commençons par spécifier la fonction:

{\ttfamily
appartient  : un élément,  un ensemble  d'éléments $\mathtt  \longrightarrow$ un
booléen
(* appartient(x,E) $\mathtt{\Leftrightarrow x\in E}$ *)
}

Nous   allons  ensuite   raisonner  récursivement   suivant   la  taille
décroissante de l'ensemble:

\begin{itemize}
\item {\ttfamily appartient(x,\{\}) = FAUX}
\item  {\ttfamily  appartient(x,$\mathtt{t\oplus Q}$)  =  (t=x) ou  bien
      appartient(x,Q)}
\end{itemize}

Cela se traduit en \textsc{Caml} de la manière suivante:

\begin{lstlisting}[caption={}]
let rec appartient el ensemble =
  match ensemble with
    |Vide -> false
    |Ens(t,q) ->
      if t = el then true
      else appartient el q;;
\end{lstlisting}

Ainsi, en reprenant l'exemple précédent:


\begin{lstlisting}[caption={}]
# appartient 3 e;;
- : bool = true
# appartient 5 e;;
- : bool = false
\end{lstlisting}

À vous de jouer avec les fonctions suivantes:

\begin{enumerate}
\item  \texttt{ajoute  el  ens}   qui  ajoute  l'élément  \texttt{el}  à
      l'ensemble \texttt{ens}. On testera si l'élément appartient déjà à
      l'ensemble.
\item \texttt{union ens1 ens2} qui renvoie la réunion des deux ensembles
      \texttt{ens1} et \texttt{ens2}.
\item   \texttt{cardinal}  qui  calcule   le  cardinal   d'un  ensemble:
      attention aux répétitions!
\item  \texttt{max2 a  b} qui  renvoie  le maximum  entre \texttt{a}  et
      \texttt{b} puis \texttt{max ens} qui renvoie le plus grand élément
      de l'ensemble \texttt{ens}.
\item  \texttt{applique f  ens} qui  renvoie l'ensemble  des  images des
      éléments de \texttt{ens} par \texttt{f}. 
\item  \texttt{parties  ens}  qui  renvoie  l'ensemble  des  parties  de
      l'ensemble \texttt{ens}.
\item \texttt{retire  el ens} qui renvoie  l'ensemble \texttt{ens} privé
      de l'élément \texttt{el}.
\item  On  rappelle qu'un  prédicat  est  une  fonction à  valeurs  dans
      $\BR_2$.
Par exemple, \og est positif \fg{} se traduira par:
\begin{lstlisting}[caption={}]
fun x -> x >= 0
\end{lstlisting}

Déterminez une  fonction \texttt{selec pred ens}  qui renvoie l'ensemble
des éléments de \texttt{ens} satisfaisant le prédicat \texttt{pred}.

Vous obtiendrez par exemple:

\begin{lstlisting}[caption={}]
# selec (fun x -> x>1) e;;
- : int ens = Ens (3, Ens (2, Vide))
\end{lstlisting}

\item  \texttt{parties\_taille\_n  ens n}  qui  renvoie  les parties  de
      \texttt{ens} de cardinal \texttt{n}.

\item \texttt{existe pred  ens} qui renvoie VRAI si  au moins un élément
      de \texttt{ens} satisfait le prédicat \texttt{pred} et FAUX sinon.

\item \texttt{pour\_tout pred ens} qui renvoie VRAI si tous les éléments
      de \texttt{ens} satisfont le prédicat \texttt{pred} et FAUX sinon.

\item  \texttt{partition   pred  ens}  qui  renvoie   une  partition  de
      \texttt{ens} sous forme d'un couple de deux ensembles: la première
      composante est l'ensemble des éléments satisfaisant le prédicat et
      la deuxième est l'ensemble des autres éléments.
\item   \texttt{inter   ens1  ens2}   qui   renvoie  l'intersection   de
      \texttt{ens1} et \texttt{ens2}.
\item \texttt{complement  ens univers} qui renvoie  le complémentaire de
      \texttt{ens} dans \texttt{univers}.
\item   \texttt{difference   ens1   ens1}  qui   renvoie   \texttt{ens1}
      $\setminus$ \texttt{ens2}.
\item  \texttt{est\_inclus ens1  ens2}  qui teste  si \texttt{ens1}  est
      inclus dans \texttt{ens2}.
\item \texttt{est\_egal  ens1 ens2} qui  teste cette fois  l'égalité des
      deux ensembles. Comparez avec le \texttt{=} de \textsc{Caml}.
\item  \texttt{couples el  ens} qui  renvoie l'ensemble  des  couples de
      première  composante  \texttt{el} et  de  deuxième composante  les
      éléments de \texttt{ens}.
Par exemple:
\begin{lstlisting}[caption={}]
# couples 5 e;;
- : (int * int) ens = Ens ((5, 3), Ens ((5, 2), Ens ((5, 1), Vide)))
\end{lstlisting}
\item En déduire \texttt{produit\_cart ens1 ens2} qui renvoie l'ensemble
      $\mathtt{ens1 \times ens2}$.

\item \texttt{ens} étant un  ensemble de couples, \texttt{assoc cle ens}
      renvoie  la deuxième  composante  du premier  couple rencontré  de
      première composante \texttt{cle}.

Par exemple:

\begin{lstlisting}[caption={}]
# let base = Ens(("albert","12"),Ens(("barnabe","11"),Ens(("claude","12"),Ens(("desire","13"),Ens(("barnabe","rugby"),Vide)))));;
val base : (string * string) ens =
  Ens
   (("albert", "12"),
    Ens
     (("barnabe", "11"),
      Ens
       (("claude", "12"),
        Ens (("desire", "13"), Ens (("barnabe", "rugby"), Vide)))))
# assoc "barnabe" base;;
- : string = "11"
\end{lstlisting}

\item \texttt{ens\_assoc cle ens} qui renvoie l'ensemble des composantes
      associées à \texttt{cle} dans \texttt{ens}:

      \begin{lstlisting}[caption={}]
# ens_assoc "barnabe" base;;
- : string ens = Ens ("11", Ens ("rugby", Vide))
      \end{lstlisting}

\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\end{listeexercices}
\modenormal % restaure les définitions de sections, sous-sections, etc.

%%% Local Variables: 
%%% TeX-master: "Poly_ERCB_2012"
%%% End: 
