partiels/0812S2/partiel.tex

   1 \documentclass[12pt]{article}
   2 \usepackage[a4paper]{geometry}
   3 \usepackage[francais]{babel}
   4 \usepackage[utf8]{inputenc}
   5 \usepackage{a4}
   6 \usepackage{amsmath}
   7 \usepackage{amsfonts}
   8 \usepackage{amssymb}
   9 \usepackage{framed}
  10 \usepackage{dsfont}
  11 \usepackage[amsmath,thmmarks,thref,framed]{ntheorem}
  12 \usepackage[dvips]{graphics}
  13 \usepackage{epsfig}
  14 \usepackage{calc}
  15 \usepackage{tabls}
  16 \usepackage{slashbox}
  17 \usepackage{times}
  18 \usepackage{tabularx}
  19 \usepackage{textcomp}
  20 \title{
  21 Partiel de mathématiques discrètes, semestre 2, decembre 2008.\\
  22 Durée : 3 heures.}
  23 \date{}
  24 \geometry{hmargin=1.5cm, vmargin= 1.5cm}
  25 \author{\sc{Couchot}, J.-F}
  26 \begin{document}
  27 \maketitle
  28
  29
  30
  31 Les supports  de TDs et de TP sont autorisés; la calculatrice est interdite.
  32 Cette épreuve contient trois parties distinctes:
  33 un qcm, quelques démonstrations syntaxiques, et quelques programmes Prolog.
  34
  35
  36 \section{QCM (1h45)}
  37
  38 Q. 1.
  39 On considère la base de connaissance suivante:
  40 \begin{scriptsize}
  41 \begin{verbatim}
  42 parent(pam,bob).
  43 parent(tom,bob).
  44 parent(tom,liz).
  45 parent(bob,ann).
  46 parent(bob,pat).
  47 parent(pat,jim).
  48
  49 ancetre(X,Z) :- parent(X,Z).
  50 ancetre(X,Z) :- parent(X,Y),ancetre(Y,Z).
  51 \end{verbatim}
  52 \end{scriptsize}
  53
  54 On soumet la requête:
  55 \begin{scriptsize}
  56 \begin{verbatim}
  57 ?- ancetre(pam,X).
  58 \end{verbatim}
  59 \end{scriptsize}
  60
  61 Prolog donne 4 réponses distinctes et échoue. L'assertion proposée est vraie ou fausse ?
  62
  63
  64 Q. 2. Une formule propositionnelle $F$ a pour conséquence logique une tautologie.
  65 L'affirmation suivante est-elle vraie:
  66 \og  $F$ est donc une tautologie \fg{}?
  67
  68
  69 Q. 3. Si j'étudie, je n'échoue pas en maths,
  70 si je ne joue pas au basket-ball, alors j'étudie,
  71 mais j'ai échoué en mathématiques.
  72 Donc, j'ai joué au basket-ball.
  73  Le raisonnement proposé est-il incorrect?
  74
  75
  76 Q. 4. On considère les prédicats et constantes suivants avec leur interprétation sur un univers constitué d'individus humains.
  77 \begin{center}
  78 \begin{tabular}{|r|l|}
  79 \hline
  80 Prédicats & Sens \\
  81 \hline
  82 $\textit{aime}(x,y)$                 & $x$ aime $y$ \\
  83 $\textit{maries}(x,y)$                & $x$ et $y$ sont mariés  \\
  84 $\textit{femme}(x)$                  & $x$ est une femme \\
  85 $\textit{homme}(x)$                  & $x$ est un  homme \\
  86 $\textit{fidele}(x)$                 & $x$ est fidèle \\
  87 $\textit{honete}(x)$                 & $x$ dit la vérité \\
  88 $a$                                  & Alice \\
  89 $b$                                  & Bob \\
  90 $c$                                  & Clinton \\
  91 \hline
  92 \end{tabular}
  93 \end{center}
  94
  95 $$
  96 \exists x \, . \, (\forall y \, . \,
  97   \textit{homme}(x) \land
  98  (\textit{femme}(y) \Rightarrow
  99   \textit{aime}(x,y))
 100 $$
 101
 102 peut se traduire en \og certains hommes sont aimés de toutes les femmes \fg.
 103 L'assertion proposée est vraie ou fausse ?
 104
 105 Q. 5.  Soit $p$, $q$, $r$ trois variables propostionnelles.
 106         L'énoncé suivant est-il une tautologie?
 107 $(p \lor q) \land r \Leftarrow (p \lor r) \land (q \lor r)$.
 108
 109
 110 Q. 6.
 111 Soit $x$ et $y$ des entiers naturels.
 112 $\forall x \, .\, (\exists y \, .\, x +y \ge x +1 )$
 113 est vraie.
 114 L'assertion est-elle vraie?
 115
 116
 117
 118 Q. 7.
 119 Une base de connaissance Prolog est un ensemble de faits, de règles
 120 et de requêtes.
 121  L'assertion proposée est vraie ou fausse ?
 122
 123
 124 Q. 8. Soit $p$ et $q$ les variables propositionnelles correspondant respectivement à \og il est grand \fg{} et \og il est beau \fg{}.
 125         \og Il n'est ni grand, ni beau \fg{} peut-elle s'écrire $\neg (p \land q )$?
 126
 127
 128 Q. 9.  Soit $p$, $q$, $r$ trois variables propostionnelles.
 129         La relation $\{p \Rightarrow \neg q , q \} \models \neg p$ est-elle vraie ?
 130
 131
 132 Q. 10. \og $B$ seulement si  $A$ \fg{}
 133 peut-elle être représentée par $ \neg A \Rightarrow B $?
 134
 135
 136 Q. 11.  Soit $p$, $q$, $r$ trois variables propostionnelles.
 137         L'énoncé suivant est-il une tautologie?
 138 $
 139 (p \Rightarrow q) \lor p \lor r \Rightarrow q \lor r$.
 140
 141
 142 Q. 12. Soit $p$, $q$  les variables propositionnelles correspondant respectivement à \og il est grand \fg{} et \og il est beau \fg{}.
 143 De plus, \og il  est petit \fg{} signifie qu'il n'est pas grand et
 144 \og il est moche \fg{} signifie qu'il n'est pas beau.
 145         \og il est faux qu'il est petit ou moche \fg{} peut-elle s'écrire
 146 $ \neg (\neg p \lor \neg p)$?
 147
 148
 149 Q. 13. La formule
 150 $\forall x \,.\, x > 0 \Rightarrow
 151   (\exists y \, . \, e^y = x)
 152 $
 153 est vraie sur l'univers $\mathds{N}$.
 154 L'assertion  est-elle vraie?
 155
 156 Q. 14. Une formule  $F$ a pour conséquence logique une antilogie.
 157         On ne peut donc rien dire de $F$.
 158
 159
 160 Q. 15.
 161 Les termes $p(X,f(a,Y),X)$ et $p(f(U,U),Z,Z)$ sont-ils unifiables ?
 162
 163
 164
 165 Q. 16. Soit $p$ et $q$ les variables propositionnelles correspondant respectivement à \og il est grand \fg{} et \og il est beau \fg{}.
 166         Sachant que \og il  est petit \fg{} signifie qu'il n'est pas grand,
 167 \og il est grand ou il est petit et beau \fg{} peut-elle s'écrire
 168 $ p \lor q $?
 169
 170
 171
 172 Q. 17.
 173 Dans la formule
 174 $P(a) \Rightarrow Q(a)$
 175 la variable $a$ n'est pas liée.
 176 L'assertion est-elle vraie?
 177
 178 Q. 18. La formule
 179 $\forall x \,.\, x > 0 \Rightarrow
 180   (\exists y \, . \, e^y = x )
 181 $
 182 est-elle vraie sur l'univers $\mathds{R}$?
 183
 184
 185 Q. 19.  Soit $p$, $q$, $r$ trois variables propostionnelles.
 186         La relation $\{r\} \models p \land q  \Rightarrow r$ est-elle vraie?
 187
 188
 189 Q. 20.
 190 \og Il est faux qu'il ne fait pas froid ou qu'il pleut \fg{}
 191 est-elle équivalente à   \og il fait froid mais il ne pleut pas \fg{}?
 192
 193
 194 Q. 21.
 195 Soit la démonstration  syntaxique suivante:
 196
 197 \begin{tabular}{lll}
 198 \multicolumn{3}{l}{Démonstration}\\
 199 1.&$\neg B \Rightarrow \neg A$ &$H_1$ \\
 200 2.&$A$ &$H_2$ \\
 201 3.&\_\_\_\_\_ &\_\_\_\_\_ \\
 202 4.&\_\_\_\_\_ &\_\_\_\_\_ \\
 203 5.&$\neg\neg B$ &réduction de l'absurde entre 4. et 1. \\
 204 6.&$\neg \neg B \Rightarrow B$ &Axiome 9.\\
 205 7.& $B$ &mp entre 5. et 6.
 206 \end{tabular}
 207
 208 \noindent Si elle était correcte et complète, cette démonstration permetrait-elle
 209 de démontrer le théorème de la contraposée ?
 210
 211
 212 Q. 22.
 213 Soit la démonstration  syntaxique suivante:
 214
 215 \begin{tabular}{lll}
 216 \multicolumn{3}{l}{Démonstration}\\
 217 1.&$\neg B \Rightarrow \neg A$ &$H_1$ \\
 218 2.&$A$ &$H_2$ \\
 219 3.&\_\_\_\_\_ &\_\_\_\_\_ \\
 220 4.&\_\_\_\_\_ &\_\_\_\_\_ \\
 221 5.&$\neg\neg B$ &réduction de l'absurde entre 4. et 1. \\
 222 6.&$\neg \neg B \Rightarrow B$ &Axiome 9.\\
 223 7.& $B$ &mp entre 5. et 6.
 224 \end{tabular}
 225
 226 La démonstration est-elle correcte et complète si en 3. et 4. on a:
 227 \begin{tabular}{lll}
 228 3.&$\neg \neg A \Rightarrow  \neg \neg B $ &théoreme de la contraposé sur 1. \\
 229 4.&$\neg \neg A \Rightarrow A $ &Axiome 9 ?
 230 \end{tabular}
 231
 232
 233 Q. 23.
 234 On considère la base de connaissance suivante
 235 \begin{scriptsize}
 236 \begin{verbatim}
 237 a_une_baguette(harry).
 238 joueur_de_Quidditch(harry).
 239 sorcier(ron).
 240 sorcier(X) :- a_un_balai(X), a_une_baguette(X).
 241 a_un_balai(X) :- joueur_de_Quidditch(X).
 242 \end{verbatim}
 243 \end{scriptsize}
 244
 245 Lorsqu'on soumet successivement les requêtes suivantes
 246
 247 \begin{scriptsize}
 248 \begin{verbatim}
 249 ?- sorcier(ron).
 250 ?- sorciere(ron).
 251 ?- sorcier(hermione).
 252 ?- sorciere(hermione).
 253 ?- sorcier(harry).
 254 \end{verbatim}
 255 \end{scriptsize}
 256
 257 Prolog répond trois fois faux.
 258  L'assertion proposée est vraie ou fausse ?
 259
 260
 261 Q. 24. La relation $\{P,Q\} \vdash R$  se lit-elle
 262 \og $R$ est une conséquence logique de l'ensemble
 263                      $\{P,Q\}$ \fg{}?
 264
 265
 266 Q. 25.
 267 Dans les clauses
 268 \begin{scriptsize}
 269 \begin{verbatim}
 270 pere_de(Y,Z) :- homme(Y),a_pour_fils(Y,Z).
 271 pere_de(Y,Z) :- homme(Y),a_pour_fille(Y,Z).
 272 \end{verbatim}
 273 \end{scriptsize}
 274
 275 \noindent La première clause se traduit-elle en
 276 $
 277 \forall y,z \, . \, \textit{pere}(y,z) \Leftrightarrow \textit{homme}(y)
 278 \land \textit{a\_pour\_fils}(y,z)
 279 $
 280 ?
 281
 282
 283
 284
 285 Q. 26. Soit $p$ et $q$ les variables propositionnelles correspondant respectivement à \og il est grand \fg{} et \og il est beau \fg{}.
 286         \og{} Il est grand mais il n'est pas beau\fg{}
 287 peut-elle se traduire par $p \lor \neg q$?
 288
 289
 290 Q. 27.  Soit $p$, $q$, $r$ trois variables propostionnelles.
 291         L'énoncé suivant est-il une tautologie?
 292 $(p \lor q) \land r \Rightarrow (p \lor r) \land (q \lor r)$.
 293
 294
 295 Q. 28. \og $B$ seulement si  $A$ \fg{}
 296 peut-elle être représentée par $ A \Rightarrow B$ ?
 297
 298
 299 Q. 29.
 300 En logique des propositions,
 301 il est possible de déduire que $P$ est vraie chaque fois que
 302 $H_1$, \ldots, $H_n$ le sont par la méthode des tables de vérités sans
 303 qu'il n'existe nécessairement de démonstration syntaxique permettant
 304 d'établir $P$ à partir des hypothèses $H_1$, \ldots, $H_n$.
 305 L'assertion est-elle vraie?
 306
 307 Q. 30.
 308 Dans la formule
 309 $(\forall x \, . \, x \ge 5) \land (\exists y \, ; \, y \ge x)$
 310 la variable $x$ est-elle  liée?
 311
 312
 313 Q. 31. Soit $p$, $q$  les variables propositionnelles correspondant respectivement à \og il est grand \fg{} et \og il est beau \fg{}.
 314 De plus, \og il  est petit \fg{} signifie qu'il n'est pas grand et
 315 \og il est moche \fg{} signifie qu'il n'est pas beau.
 316         \og il est faux qu'il est petit ou moche \fg{} peut-elle s'écrire
 317 $ p \land q $.
 318
 319
 320 Q. 32.  Soit $p$ et $q$, deux variables propostionnelles.
 321         L'énoncé $
 322 (p \land ( p \lor q)) \Leftrightarrow p$
 323  est-il une tautologie?
 324
 325
 326 Q. 33.
 327 On considère les prédicats
 328 \verb+parent(X,Y)+, qui est vrai si \verb+X+
 329 est le père ou la mère de \verb+Y+ et
 330 \verb+femme(X)+, qui est vrai si \verb+X+
 331 est est une femme.
 332 L'assertion
 333 \og \verb+X+ est la fille de \verb+Y+ \fg{} se traduit-elle en prolog par
 334 %\begin{scriptsize}
 335 \verb+fille(X,Y) :- parent(X,Y), femme(X).+?
 336
 337
 338 %\end{scriptsize}
 339
 340
 341
 342 Q. 34. On considère les prédicats et constantes suivants avec leur interprétation sur un univers constitué d'individus humains.
 343
 344 \begin{center}
 345 \begin{tabular}{|r|l|}
 346 \hline
 347 Prédicat & Sens \\
 348 \hline
 349 $\textit{aime}(x,y)$                 & $x$ aime $y$ \\
 350 $\textit{maries}(x,y)$                & $x$ et $y$ sont mariés  \\
 351 $\textit{femme}(x)$                  & $x$ est une femme \\
 352 $\textit{homme}(x)$                  & $x$ est un  homme \\
 353 $\textit{fidele}(x)$                 & $x$ est fidèle \\
 354 $\textit{honete}(x)$                 & $x$ dit la vérité \\
 355 $a$                                  & Alice \\
 356 $b$                                  & Bob \\
 357 $c$                                  & Clinton \\
 358 \hline
 359 \end{tabular}
 360 \end{center}
 361
 362 \noindent Le prédicat
 363 $
 364 \exists x,y  \, . \, (
 365        \textit{maries}(x,y) \land
 366   \neg \textit{aime}(x,y) \land
 367   \neg \textit{aime}(y,x))
 368 $
 369 traduit-il que
 370 \og dans certains couples, un conjoint n'aime pas l'autre \fg.
 371
 372
 373 Q. 35.
 374   Soit $p$, $q$, $r$ trois variables propostionnelles.
 375         L'énoncé suivant est-il une tautologie?
 376 $p \lor (q \land r) \Rightarrow (p \lor q) \land (p \lor r)$.
 377
 378
 379 Q. 36. Une formule propositionnelle $F$ a pour conséquence logique une antilogie.
 380         L'affirmation suivante est-elle vraie:
 381 \og $F$ est donc une tautologie \fg{}?
 382
 383
 384 Q. 37.
 385 En logique des propositions, $P$ se déduit syntaxiquement de
 386 $H_1$, \ldots, $H_n$ si et seulement si
 387 $P$ est une conséquence logique de $H_1$, \ldots, $H_n$.
 388 L'assertion est-elle vraie?
 389
 390 Q. 38.  Soit $p$, $q$, $r$ trois variables propostionnelles.
 391         L'énoncé suivant est-il une tautologie?
 392 $
 393 (p \Rightarrow q) \land (p \lor r) \Rightarrow q \lor r$.
 394
 395
 396 Q. 39.
 397 Soit la démonstration  syntaxique suivante:
 398
 399 \begin{tabular}{lll}
 400 \multicolumn{3}{l}{Démonstration}\\
 401 1.&$\neg B \Rightarrow \neg A$ &$H_1$ \\
 402 2.&$A$ &$H_2$ \\
 403 3.&\_\_\_\_\_ & \_\_\_\_\_ \\
 404 4.&\_\_\_\_\_ &\_\_\_\_\_ \\
 405 5.&$\neg\neg B$ &réduction de l'absurde entre 4. et 1. \\
 406 6.&$\neg \neg B \Rightarrow B$ &Axiome 9.\\
 407 7.& B &mp entre 5. et 6.
 408 \end{tabular}
 409
 410 La démonstration est-elle correcte et complète si en 3. et 4. on a
 411
 412 \begin{tabular}{lll}
 413 3.&$A \Rightarrow (\neg B \Rightarrow A)$ &Axiome 1. \\
 414 4.&$\neg B \Rightarrow A $ &modus ponens entre 2. et 3.
 415 \end{tabular}
 416 ?
 417
 418
 419
 420
 421 Q. 40.  Soit $p$ et $q$, deux variables propostionnelles.
 422         L'énoncé suivant est-il une tautologie?
 423 $
 424 (p \Rightarrow q) \Rightarrow
 425 \left(
 426 (q \Rightarrow p)
 427 \Rightarrow
 428 (q \Leftrightarrow p)
 429 \right)$.
 430
 431
 432
 433
 434
 435
 436
 437 \section{Programmation Prolog (0h30)}
 438
 439 \subsection{Voyages}
 440 \begin{scriptsize}
 441 \begin{verbatim}
 442 voiture(auckland,hamilton).
 443 voiture(hamilton,raglan).
 444 voiture(valmont,saarbruecken).
 445 voiture(valmont,metz).
 446 train(metz,frankfurt).
 447 train(saarbruecken,frankfurt).
 448 train(metz,paris).
 449 train(saarbruecken,paris).
 450 avion(frankfurt,bangkok).
 451 avion(frankfurt,singapore).
 452 avion(paris,losAngeles).
 453 avion(bangkok,auckland).
 454 avion(losAngeles,auckland).
 455 \end{verbatim}
 456 \end{scriptsize}
 457
 458 Ecrire un prédicat \verb+voyage(X,Y)+
 459 qui détermine s'il est possible de voyager d'un endroit à
 460 l'autre en empruntant des voitures, des trains ou des avions.
 461 Par exemple votre programme doit répondre yes à la requête
 462 \verb+voyage(valmont, raglan)+.
 463
 464 \subsection{Codage des entiers naturels}
 465 Les entiers naturels peuvent être codés à l'aide de 0,
 466 du successeur de 0 (qui vaut 1), puis du sucesseur du successeur de 0
 467 (qui vaut 2) et ainsi de suite\ldots
 468 Le predicat $\textit{entier}$ est alors défini à l'aide de la constante 0
 469 et du symbol fonctionnel $\textit{succ}$ selon les clauses suivantes:
 470
 471 \begin{scriptsize}
 472 \begin{verbatim}
 473 entier(0).
 474 entier(X):- X=succ(Y), entier(Y).
 475 \end{verbatim}
 476 \end{scriptsize}
 477
 478 \begin{enumerate}
 479 \item Définir le predicat \verb+somme(X,Y,Z)+ qui est vrai si l'entier
 480 \verb+Z+ est la somme de \verb+X+ et de \verb+Y+, ces trois entiers étant
 481 codés dans cette logique.
 482 \item Définir le predicat \verb+plus_grand_que(X,Y)+ qui est vrai si l'entier
 483 \verb+X+ est plus grand que l'entier \verb+Y+, ces deux entiers étant
 484 codés dans cette logique.
 485 \end{enumerate}
 486
 487
 488
 489
 490 \section{Démonstration syntaxique (45min)}
 491
 492 Dans le système \og PR \fg{} et en se servant éventuellement des théorèmes
 493 déjà démontrés dans le cours, démontrer syntaxiquement
 494 les deux formules propositionnelles suivantes:
 495 \begin{enumerate}
 496 \item $(A \Rightarrow (B \Rightarrow C)) \Rightarrow
 497   ((A \Rightarrow B) \Rightarrow (A \Rightarrow C))$
 498 \item $(A \lor  (B \land C)) \Rightarrow ((A \lor B) \land (A \lor C))$
 499 \end{enumerate}
 500
 501
 502 \newpage
 503 \noindent Nom:\newline
 504 \noindent Prénom:
 505
 506 \begin{center}
 507 \begin{tabular}{|l|c|c||l|c|c||l|c|c|}
 508 \hline
 509 Numéro & V & F & Numéro & V & F & Numéro & V & F \\
 510 \hline
 511 Q. 1 & &  & Q. 2 & &  & Q. 3 & &  \\
 512 \hline
 513 Q. 4 & &  & Q. 5 & &  & Q. 6 & &  \\
 514 \hline
 515 Q. 7 & &  & Q. 8 & &  & Q. 9 & &  \\
 516 \hline
 517 Q. 10 & &  & Q. 11 & &  & Q. 12 & &  \\
 518 \hline
 519 Q. 13 & &  & Q. 14 & &  & Q. 15 & &  \\
 520 \hline
 521 Q. 16 & &  & Q. 17 & &  & Q. 18 & &  \\
 522 \hline
 523 Q. 19 & &  & Q. 20 & &  & Q. 21 & &  \\
 524 \hline
 525 Q. 22 & &  & Q. 23 & &  & Q. 24 & &  \\
 526 \hline
 527 Q. 25 & &  & Q. 26 & &  & Q. 27 & &  \\
 528 \hline
 529 Q. 28 & &  & Q. 29 & &  & Q. 30 & &  \\
 530 \hline
 531 Q. 31 & &  & Q. 32 & &  & Q. 33 & &  \\
 532 \hline
 533 Q. 34 & &  & Q. 35 & &  & Q. 36 & &  \\
 534 \hline
 535 Q. 37 & &  & Q. 38 & &  & Q. 39 & &  \\
 536 \hline
 537 Q. 40 & &  &       & &  &  & &  \\
 538 \hline
 539 \end{tabular}
 540 \end{center}
 541
 542 \end{document}