\documentclass[10pt]{article}
\usepackage{ifxetex}
\usepackage[T1]{fontenc}
\usepackage[mathletters]{ucs}
\usepackage[utf8x]{inputenc}
\usepackage[french]{babel}
\usepackage{geometry}
\usepackage[enonce]{exam}
%\usepackage[correction]{exam}

\usepackage{epsf,amsmath,amssymb,graphicx}
\newcommand\scr{}
\usepackage[boldsans]{ccfonts}
\usepackage[mathcal,mathbf]{euler}
%\usepackage{preambuleTrm}

\usepackage{tikz}
\usetikzlibrary{automata,fit,trees,matrix,arrows,decorations.pathmorphing,shapes.arrows,chains,positioning,intersections,backgrounds,calc,through,mindmap}
%\newcommand{\myunit}{1.1cm}
\usepackage{tkz-graph}
\input{patch-tkz-graph}
\usepackage{tikz-qtree}

\newcommand{\ve}[1]{\overrightarrow{#1}}

\usepackage{algo}

\renewcommand{\algocommentfont}{\small\ttfamily\itshape}

%transposee
\usepackage{fouridx}
\newcommand*{\transp}[1]{\fourIdx{{\rm t}}{}{}{}{#1}}
\newcommand\tr{\vphantom{}^{\rm t}}

\newcommand{\dd}{\text{ d}}


\paper{DS-M11} % <- do not include FC, FT etc
%\version{0}                     % <- for multiple choice exams
\title{DS - Mathématique discrète}
\time{quatre-vingts dix minutes / cent vingt en cas de tiers temps} % <- number of hours: default is three
\semester{Premier semestre}
\annee{2013-2014} % <- default is the current year

%\campus{City}
\note{\small  Vous justifierez vos réponses
    avec le  plus grand  soin. N'oubliez pas  qu'il serait  maladroit de
    copier sur  votre voisin(e) qui  a, de toute façon,  écrit n'importe
    quoi. Toute enfreinte à  cette règle entraîne l'obtention d'une note
   plutôt faible. Aucune calculatrice ni tout autre engin  relié
    à un  quelconque réseau et   pouvant faire office  de téléphone n'est
    autorisée.   Une feuille  de
    format A5  recto-verso manuscrite peut être  consultée pendant le
    DS sous réserve d'acceptation du jury.
Vous ne rendrez que les feuilles de réponses  (numérotées de 3 à 8): les pages 3
et 4  d'une part et  les pages 5  à 8 d'autre part,  en écrivant à  chaque fois
votre nom.
    %N'oubliez pas que c'est compilator qui corrigera votre script...
}
\begin{document} 










%1
\begin{exercice}
L'opérateur $\lnor$ est défini par $1\lnor 1=1\lnor 0=0\lnor 1=0$ et
  $0\lnor0=1$.
  \begin{enumerate}
  \item Exprimer $a\lnor b$ en n'utilisant que $a$, $b$, $\lnot$ et $\land$
    (sans parenthèses).
  \item Exprimer $\lnot p$ en n'utilisant que $p$ et $\lnor$.
  \item Soit $f\equiv \lnot (x\limp \lnot y) \lor (\lnot x \land \lnot z)$.
 Exprimer $f$ en n'utilisant que $x$, $y$, $z$, $\lnor$, ( et ).
  \end{enumerate}

\end{exercice}


%2
\begin{exercice}
2040, le monde mathématique est en émoi: Eudes \textsc{Chaprot}, un ancien étudiant du département de
\textsc{Gae} de  l'\textsc{Itu} de  Klow en Syldavie,  prétend avoir  démontré un
théorème révolutionnaire. Voici ce qu'il a publié dans \textit{Barbue magazine}:

%\begin{quote}
{\itshape \textbf{Énoncé :}Toute relation sur un ensemble qui est symétrique et transitive est
   réflexive.}

%\end{quote}
%\begin{quote}
{\itshape\textbf{Démonstration :} Soit $\mathcal R$ une relation définie sur un ensemble A et soit $a$
  un élément de A.
Considérons  un élément  $b$ de  $A$  tel que  $(a,b)$  soit dans  le graphe  de
$\mathcal R$.  Comme $\mathcal R$ est  symétrique, alors $(b,a)$ est  aussi dans
le graphe de $\mathcal R$.
Or la  relation est transitive donc  $(a\mathcal R b)\land (b\mathcal  R a)\limp
a\mathcal R a$ et on en déduit que $\mathcal R$ est réflexive.}

%\end{quote}

Y a-t-il un bug dans la démonstration? Si oui, trouvez-le..

\end{exercice}




% %3
% \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\}$, $\Omega=\bigl\{A,B,C,D,E\bigr\}$.

% Déterminez les éléments $X$ de $\Omega$ qui vérifient les conditions suivantes:

% \begin{multicols}{3}
%   \begin{enumerate}
%   \item $X \cup B=\emptyset$;
%   \item $X\subseteq D \land X\not\subseteq B$;
%   \item $X\subseteq A \land X\not\subseteq C$;
%   \item $X\subseteq C \land X\not\subseteq A$;
%   \item $X\cap C = X\cap D$
%   \end{enumerate}
% \end{multicols}
% \end{exercice}


%4
\begin{exercice}




  \begin{enumerate}
  \item  Soit  $E=\bigl\{0,1\bigr\}$.  Déterminer  $\left(E^2\setminus
        \bigl\{\langle 0,0\rangle \bigr\}\right)\otimes E$ (Rappel: $\otimes$ désigne l'opérateur du produit cartésien).
    \item            Soit           $A=\bigl\{3,7\bigr\}$           et
          $B=\bigl\{c,g\bigr\}$. Déterminer 
\begin{multicols}{5}

\begin{enumerate}
\item $A^2$,
\item $B^2$, 
\item $A\otimes B$,
\item $B\otimes A$, 
\item $B^2\otimes A$.
\end{enumerate}
\end{multicols}

\end{enumerate}

\end{exercice}


\vfill

\eject


%5
\begin{exercice}
On considère la relation définie sur $\bbz$ par $x\mathcal R y$ si, et seulement si,
$x-y$ est un multiple de $3$.

\begin{enumerate}

\item  Démontrez que  deux entiers  sont  en relation  par $\mathcal  R$ si,  et
  seulement si, leurs restes dans la division par 3 vérifie une certaine propriété.

\item Déterminez, en tentant d'être aussi  rigoureux que possible, l'ensemble quotient
de $\bbz$ modulo $\mathcal R$, noté $Q$.

\item Dans le langage \textbf{Gloup}, on dispose d'un type 
 \textbf{Ens a} pour désigner les ensembles dont les éléments sont de type \textbf{a}.

Le type  \textbf{Entier}  désigne les  entiers signés  en précision
infinie. Quel sera, dans ce langage, la signature
\begin{multicols}{4}
\begin{enumerate}
\item  de $\bbz$?
\item de $[2]_{\mathcal R}$?
\item de $Q$?
\end{enumerate}
\end{multicols}
\item Complétez avec le symbole le plus signifiant parmi $
\in ,\ni ,\subseteq ,\supseteq ,=,\neq ,\varsubsetneq, \varsupsetneq, \not\subseteq,\not\supseteq
$
\begin{multicols}{4}
\begin{enumerate}

\item $2\ ...\ [2]_{\mathcal R}$;
\item $\bbz \ ...\  [2]_{\mathcal R}$;
\item $\mathcal P(\bbz) \ ...\  [2]_{\mathcal R}$
\item $\mathcal P(\bbz) \ ...\  \bbz $
\item $Q \ ...\  \bbz $
\item $Q \ ...\  \mathcal P(\bbz)$
\item $Q \ ...\  [2]_{\mathcal R}$

\end{enumerate}
\end{multicols}
\end{enumerate}


\end{exercice}




%6
\begin{exercice}
On note:
 $a=\bigl\{1\bigr\}$,          $b=\bigl\{2\bigr\}$,         $c=\bigl\{3\bigr\}$,
 $d=\bigl\{1,2,3,5,8,9\bigr\}$,                         $e=\bigl\{1,2,6\bigr\}$,
 $f=\bigl\{1,2,3,5,6,8,9\bigr\}$,  $g=\bigl\{3,9\bigr\}$, $h=\bigl\{1,2\bigr\}$,
 $i=\bigl\{1,2,3,4,5,8,9\bigr\}$,                       $j=\bigl\{1,2,5\bigr\}$,
 $k=\bigl\{2,5\bigr\}$, $\ell=\bigl\{3,8,9\bigr\}$ et $m=\bigl\{1,2,5,6\bigr\}$.

On note enfin $Ω=\bigl\{a,b,c,d,e,f,g,h,i,j,k,l,m\bigr\}$.


\begin{enumerate}

\item Est-ce que $Ω$ est un ensemble totalement ordonné par $\subseteq$?
\item Déterminez, lorsque cela est possible:

\begin{multicols}{2}
\begin{enumerate}
\item les éléments minimaux de $Ω$;
\item les éléments maximaux de $Ω$;
\item le maximum de $Ω$;
\item le minimum de $Ω$;
\item les majorants de $\bigl\{a,b,c\bigr\}$ dans $Ω$;
\item les majorants de $\bigl\{g,\ell,j\bigr\}$ dans $Ω$;
\item les minorants de $\bigl\{g,\ell,j\bigr\}$ dans $Ω$;
\item la borne inférieure de $\bigl\{g,\ell,j\bigr\}$ dans $Ω$;
\item la borne supérieure de $\bigl\{a,b,c\bigr\}$ dans $Ω$.
\end{enumerate}
\end{multicols}
\item Déterminez le  diagramme de \textsc{Hasse} de la  relation $\subseteq$ sur
  $Ω$.

\item On considère la procédure suivante:

  \begin{algo}
\PROC{Exo6}{\pfarg{$E$}{Ensemble  muni d'un  ordre partiel}}
\STATE{$S$\recoit{} $E$}
\WHILE{$S\neq\emptyset$}
\STATE{$m$ \recoit{} un élément minimal de $S$ choisi selon un critère fixé}
\STATE{$S$\recoit{} $S\setminus \{m\}$}
\STATE{afficher $m$}
\ENDWHILE
%\END
  \end{algo}



Le critère fixé  de choix de l'élément  minimal lorsqu'il y en  a plusieurs sera
l'ordre alphabétique croissant. 

Appliquez alors cette procédure à l'ensemble $Ω$ précédent muni de l'ordre $\subseteq$: qu'affiche-t-il?




À votre avis, quel est le rôle de cette procédure?

\end{enumerate}


\end{exercice}








%%% réponses

\answersheet








%1
\begin{exercice}
\begin{enumerate}
\item \textcolor{white}{ . } 
\vspace{2cm}
\item \textcolor{white}{ . } 
\vspace{2cm}
\item \textcolor{white}{ . } 
\vspace{5cm}
\end{enumerate}
 
\end{exercice}


%2
\begin{exercice}
  \vspace{10cm}
\end{exercice}

\vfill

\eject


% %3

% \begin{exercice}
  
% \begin{enumerate}
% \item \textcolor{white}{ . } 
% \vspace{3cm}
% \item \textcolor{white}{ . } 
% \vspace{3cm}
% \item \textcolor{white}{ . } 
% \vspace{3cm}
% \item \textcolor{white}{ . } 
% \vspace{3cm}
% \item \textcolor{white}{ . } 
% \vspace{3cm}
% \end{enumerate}

% \end{exercice}


%4

\begin{exercice}
\begin{enumerate}
\item \textcolor{white}{ . } 
\vspace{3cm}
\item
\begin{enumerate}
\item \textcolor{white}{ . } 
\vspace{3cm}
\item \textcolor{white}{ . } 
\vspace{3cm}
\item \textcolor{white}{ . } 
\vspace{3cm}
\item \textcolor{white}{ . } 
\vspace{3cm}
\item \textcolor{white}{ . } 
\vspace{3cm}
\end{enumerate}
\end{enumerate}

\end{exercice}

\vfill

\eject

\answersheet
\setcounter{ex}{4}
%5
\begin{exercice}
  \begin{enumerate}
  \item \textcolor{white}{ . } 
    \vspace{4cm}
  \item \textcolor{white}{ . } 
    \vspace{4cm}
  \item 
    \begin{enumerate}
    \item \textcolor{white}{ . } 
      \vspace{2cm}
    \item \textcolor{white}{ . } 
      \vspace{2cm}
    \item \textcolor{white}{ . } 
      \vspace{2cm}
    \end{enumerate}
  \item 
    \begin{enumerate}
    \item \textcolor{white}{ . } 
      \vspace{2cm}
    \item \textcolor{white}{ . } 
      \vspace{2cm}
    \item \textcolor{white}{ . } 
      \vspace{2cm}
    \item \textcolor{white}{ . } 
      \vspace{2cm}
    \item \textcolor{white}{ . } 
      \vspace{2cm}
    \item \textcolor{white}{ . } 
      \vspace{2cm}
    \item \textcolor{white}{ . } 
      \vspace{2cm}
    \end{enumerate}
  \end{enumerate}
\end{exercice}






%6
\begin{exercice}
  
  \begin{enumerate}
  \item \textcolor{white}{ . } 
    \vspace{3cm}
  \item
    \begin{enumerate}
    \item \textcolor{white}{ . } 
      \vspace{2cm}
    \item \textcolor{white}{ . } 
      \vspace{2cm}
    \item \textcolor{white}{ . } 
      \vspace{2cm}
    \item \textcolor{white}{ . } 
      \vspace{2cm}
    \item \textcolor{white}{ . } 
      \vspace{2cm}
    \item \textcolor{white}{ . } 
      \vspace{2cm}
    \item \textcolor{white}{ . } 
      \vspace{2cm}
    \item \textcolor{white}{ . } 
      \vspace{2cm}
    \item \textcolor{white}{ . } 
      \vspace{2cm}
    \end{enumerate}



  \item \textcolor{white}{ . } 
    \vspace{8.5cm}


\vfill

\eject
  \item \textcolor{white}{ . } 
    \vspace{19.5cm}
  \end{enumerate}
\end{exercice}

\end{document}