]> AND Private Git Repository - cours-maths-dis.git/blob - partiels/130311S2/main.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
pgcd, euclide,...
[cours-maths-dis.git] / 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