partiels/130311S2/main.tex

   1 \documentclass[12pt,a4paper,french]{article}
   2 \usepackage[francais]{babel}
   3 \usepackage[utf8]{inputenc}
   4 \usepackage{a4}
   5 \usepackage{amsmath}
   6 \usepackage{amsfonts}
   7 \usepackage{amssymb}
   8 \usepackage{framed}
   9 \usepackage{dsfont}
  10 \usepackage[amsmath,thmmarks,thref,framed]{ntheorem}
  11 \usepackage[dvips]{graphics}
  12 \usepackage{epsfig}
  13 \usepackage{calc}
  14 \usepackage{tabls}
  15 \usepackage{slashbox}
  16 \usepackage{times}
  17 \usepackage{multicol}
  18 \usepackage{tabularx}
  19 \usepackage{textcomp}
  20 \usepackage{pst-all}
  21 \usepackage[a4paper]{geometry}
  22 \input{symboles.sty}
  23
  24 \geometry{hmargin=1cm, vmargin=1.5cm}
  25 \title{Département d'informatique, partiel de Mathématiques discrètes\\
  26 Semestre 2, mars 2013, 2 heures.\\
  27 }
  28
  29 \date{}
  30
  31 \begin{document}
  32 \vspace{-7em}
  33 \maketitle
  34 \vspace{-5em}
  35
  36 \noindent Seule une fiche manuscrite RV de format A5 est autorisée.
  37
  38 \section*{Relations particulières}
  39
  40 \subsection*{Exercice 1 :}
  41     On note $A$ l'ensemble des entiers de 1 à 6 ($A=\{1,2,3,4,5,6\}$).\\
  42     Soit l'application $f:A\longrightarrow A$ définie par le système suivant :\\
  43     $$\left\lbrace
  44     \begin{array}{ll}
  45     f(n)=n+3 & \mbox{si $n \leq 3$}\\
  46     f(n)=7-n & \mbox{sinon}
  47     \end{array}
  48     \right.$$
  49
  50     En admettant que $f$ est une bijection, compléter les tableaux de valeurs suivants :\\
  51     \\
  52     $\begin{array}{cc}
  53      \begin{tabular}{|l|l|l|l|l|l|l|l|}
  54     \hline
  55     $n$ & 1&2&3&4&5&6 \\
  56     \hline
  57     $f(n)$&  &  &  &  &  &  \\
  58     \hline
  59     \end{tabular}
  60    &
  61    \begin{tabular}{|l|l|l|l|l|l|l|l|}
  62     \hline
  63     $n$ & 1&2&3&4&5&6 \\
  64     \hline
  65     $f^{-1}(n)$&  &  &  &  &  &  \\
  66     \hline
  67     \end{tabular}
  68
  69     \end{array}$
  70
  71
  72   \subsection*{Exercice 2 :}
  73   Dans cet exercice, on utilise l'application $f$ définie par :\\
  74   $$\begin{array}{clcl}
  75     f : & \mathbb{R} &\longrightarrow &\mathbb{R}\\
  76     \nonumber  & x &\longmapsto& \displaystyle{\frac{2x}{1+x^2}}
  77      \end{array}$$
  78
  79
  80     \begin{enumerate}
  81      \item Vérifier que $f$ est bien définie sur $\mathbb{R}$.
  82      \item Montrer que : \\
  83       $\forall x, x' \in \mathbb{R}, f(x')=f(x) \Rightarrow \left( \left( x'=x \right)
  84       \vee \left(\displaystyle{x'=\frac{1}{x}}\right) \right)$.
  85      \item L'application $f$ est-elle injective?
  86      \item Résoudre dans $\mathbb{R}$ l'équation $f(x)=3$.
  87      \item L'application $f$ est-elle surjective ?
  88     \end{enumerate}
  89
  90
  91 \section*{Logique des propositions}
  92
  93 \subsection*{Exercice 3:}
  94 %\subsection*{Tautologies, antilogie et autres}
  95 Pour chacun des propositions suivantes, dire si c'est une tautologie,
  96 une antilogie ou ni l'une ni l'autre. Justifier.
  97 \begin{enumerate}
  98 \item
  99 $
 100 \big( (\neg P \Rightarrow Q) \land
 101 (\neg P \Rightarrow \neg Q) \big)
 102 \Rightarrow P.$
 103 \item
 104 $
 105 P \lor Q \Rightarrow
 106 \big(
 107 P \land( Q \Rightarrow Q)
 108 \big).$
 109 \item
 110 $
 111 \big(
 112 ( \neg Q \land P ) \Rightarrow ( Q \lor P )
 113 \big)
 114 \Rightarrow
 115 \neg ( Q \lor P \lor \neg Q ).
 116 $
 117 \end{enumerate}
 118
 119 \subsection*{Exercice 4:}
 120 %\subsection*{Formalisation de connecteurs logiques}
 121 $A$ et $B$ sont des variables propositionnelles. Formaliser à l'aide
 122 de connecteurs logiques les énoncés suivants:
 123 \begin{enumerate}
 124 \item \og $A$ seulement si $B$. \fg{}
 125 \item \og $B$ à moins que $A$.\fg{}
 126 \item \og$B$, bien que $A$.\fg{}
 127 \item \og $B$ est une condition nécessaire pour $A$.\fg{}
 128 \end{enumerate}
 129
 130
 131
 132 \subsection*{Exercice 5:}
 133 %\subsection*{Vers la logique propositionnelle}
 134 Pour chaque phrase suivante, définir une variable propositionnelle pour
 135 chaque proposition élémentaire et formaliser ensuite la phrase
 136 en  logique propositionnelle.
 137 \begin{enumerate}
 138 \item  \og Si le système fonctionne normalement, le noyau est en état de marche.\fg{}
 139
 140 \item \og  Le fait que le système ne soit pas en mode ``multi-user''
 141   est une condition suffisante pour être en mode "interruption".\fg{}
 142 \item \og Le système est en mode ``multi-user'' seulement s'il fonctionne normalement.\fg{}
 143 \item \og  Soit le noyau est en état de marche, soit le système est en mode ``interruption''.\fg{}
 144 \end{enumerate}
 145
 146
 147
 148 %\subsection*{Exercice 6:}
 149 %\subsection*{Conséquences logiques}
 150 %Dire si chacune des deux propositions suivantes est vraie en justifiant:
 151 %\begin{enumerate}
 152 %\item $\{B \Rightarrow C\lor D,
 153 %  C \Rightarrow \neg A \land \neg B,
 154 %  \} \models
 155 %  B \Rightarrow \neg C \land  D.$
 156 %\item $\{A \Rightarrow B \land C,
 157 %  \neg D  \land \neg E \Rightarrow \neg B,
 158 %  D \Rightarrow \neg C \land B \} \models
 159 %  (E \Rightarrow \neg B) \Rightarrow \neg A.$
 160 %\end{enumerate}
 161
 162
 163
 164
 165
 166 \subsection*{Exercice 6:}
 167 %\subsection*{L'Île de Puro Pira}
 168 L'île de Puro Pira est peuplée
 169 de \emph{Purs} qui disent toujours la vérité et de
 170 de \emph{Pires} qui ne disent que des mensonges.
 171 Débarqué sur l'île, l'anthropologue Abercrombie rencontre trois indigènes Alice, Bernard et Chloé.
 172 \begin{enumerate}
 173 \item\label{item1} Alice affirme \og C’est moi le chef\fg{}.
 174 \item\label{item2} Bernard affirme aussi \og C’est moi le chef\fg{}.
 175 \item Quant à Chloé elle ajoute \og Au plus l’un de nous trois dit la vérité.\fg{}
 176 \end{enumerate}
 177 On sait de plus qu'il n'y a qu'un seul chef. Par la suite:
 178 \begin{itemize}
 179 \item $A$, $B$ et $C$ sont les variables propositionnelles qui valent chacune
 180   vrai si et seulement si Alice est un pur, Bernard est un pur et Chloé est un pur respectivement;
 181 \item $Ac$, $Bc$ et $Cc$ sont les variables propositionnelles qui
 182   valent chacune vrai si et seulement si Alice est un chef, Bernard est un chef
 183   et Chloé est un chef respectivement?
 184 \end{itemize}
 185
 186
 187 \begin{enumerate}
 188 \item Montrer que l'affirmation \og il n'y a qu'un seul chef \fg{}
 189   peut se représenter par la formule:
 190   $$ (Ac \lor Bc \lor Cc) \land
 191   \neg (Ac \land Bc) \land \neg (Ac \land Cc) \land \neg (Bc \land Cc).
 192   $$
 193 \item Montrer que l'affirmation de Chloé peut se représenter par la formule:
 194   $$
 195   (C \Rightarrow \neg A \land \neg B ) \land
 196   (\neg C \Rightarrow A \land B ).
 197   $$
 198 \item Traduire en logique propositionnelle les propositions des
 199   items~\ref{item1}. et~\ref{item2}. relatives aux affirmations d'Alice et
 200   Bernard.
 201 \item (Bonus) Montrer que le status en termes de chef, purs, pires,
 202   de chacun des indigène peut se déduire comme
 203   une conséquence logique de ces quatre formules.
 204 \end{enumerate}
 205
 206 \end{document}
 207