partiels/S2_0905/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]{graphicx}
  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, juin 2009.\\
  22 Durée : 3 heures.}
  23 \date{}
  24 \geometry{hmargin=1cm, vmargin= 1cm}
  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; téléphones et calculatrices sont
  32 interdits.
  33
  34 \section{QCM (1h45)}
  35
  36
  37 % Q. 1. Une formule propositionnelle $F$ a pour conséquence logique une tautologie.
  38 %        L'affirmation suivante est-elle vraie:
  39 % \og  On ne peut donc rien dire de $F$ \fg{}?
  40
  41
  42 Q. 1.  L'affirmation \og il fait beau aujourd'hui  donc il ne pleuvra pas dans dix jours \fg{}
  43 est-elle une proposition?
  44
  45
  46 Q. 2.
  47 Soit la démonstration  syntaxique suivante: \newline
  48 \begin{tabular}{lll}
  49 \multicolumn{3}{l}{Démonstration}\\
  50 1.&$\neg B \Rightarrow \neg A$ &$H_1$ \\
  51 2.&$A$ &$H_2$ \\
  52 3.&\_\_\_\_\_ &\_\_\_\_\_ \\
  53 4.&\_\_\_\_\_ &\_\_\_\_\_ \\
  54 5.&$\neg\neg B$ &réduction de l'absurde entre 4. et 1. \\
  55 6.&$\neg \neg B \Rightarrow B $ &Axiome 9.\\
  56 7.& B &mp entre 5. et 6.
  57 \end{tabular}
  58 La démonstration est correcte si en 3. et 4. on a: \newline
  59 \begin{tabular}{lll}
  60 3.&$\neg \neg A \Rightarrow  \neg \neg B $ &théoreme de la contraposée sur 1. \\
  61 4.&$\neg \neg A \Rightarrow A $ &Axiome 9.
  62 \end{tabular}
  63 \\
  64
  65 Q. 3.
  66 \og \emph{Si la paix survient, alors il y aura une crise économique
  67 à moins que le pays se dote d'armes nouvelles ou bien exécute
  68 un large programme d'investissement intérieur dans les secteurs de
  69 l'enseignement, de la santé et de la lutte contre la pauvreté.
  70 Il n'est pas possible de se mettre d'accord sur les objectifs
  71 que peut se donner un large programme d'investissement intérieur.
  72 Donc si la paix survient et qu'il n'y a pas de crise économique,
  73 le pays doit se doter d'armes nouvelles.} \fg{}
  74          Le raisonnement proposé est-il correct?
  75
  76
  77 Q. 4. La relation $\{P,Q\} \vdash R$  se lit-elle
  78 \og $R$ est une conséquence logique de l'ensemble
  79                      $\{P,Q\}$ \fg{}?
  80
  81
  82 Q. 5.  Soit $p$, $q$, $r$ trois variables propostionnelles.
  83         L'énoncé suivant est-il une tautologie?
  84 $  (p \lor q) \land (p \lor r) \Rightarrow p \lor (q \land r)$.
  85
  86
  87 Q. 6.  Soit $p$ et $q$, deux variables propostionnelles.
  88         L'énoncé suivant est-il une tautologie?
  89 $
  90 (p \Rightarrow q) \Rightarrow
  91 \left(
  92 (q \Rightarrow p)
  93 \Rightarrow
  94 (q \Leftrightarrow p)
  95 \right)$.
  96
  97
  98 Q. 7. La formule
  99 $\forall x \,.\, x > 0 \Rightarrow
 100   (\exists y \, . \, e^y = x )
 101 $
 102 est vraie sur l'univers $\mathds{R}$.
 103 L'assertion proposée est vraie ou fausse ?
 104
 105 Q. 8. \og $A$ à moins que  $B$ \fg{}
 106 peut-elle être représentée par $ \neg A \Rightarrow B$?
 107
 108
 109 Q. 9.
 110 Soit $x$ et $y$ des entiers naturels.
 111 $\exists x \, .\, ( \forall y \, . \,  y  \neq x \Rightarrow  x  <1 )$
 112 est vraie.
 113 L'assertion proposée est vraie ou fausse ?
 114
 115 % Q. 11.
 116 % On considère la base de connaissance suivante:
 117 % \begin{scriptsize}
 118 % \begin{verbatim}
 119 % a_une_baguette(harry).
 120 % joueur_de_Quidditch(harry).
 121 % sorcier(ron).
 122 % sorcier(X) :- a_un_balai(X), a_une_baguette(X).
 123 % a_un_balai(X) :- joueur_de_Quidditch(X).
 124 % \end{verbatim}
 125 % \end{scriptsize}
 126
 127 % Lorsqu'on soumet successivement les requêtes suivantes:
 128
 129 % \begin{scriptsize}
 130 % \begin{verbatim}
 131 % ?- sorcier(ron).
 132 % ?- sorciere(ron).
 133 % ?- sorcier(hermione).
 134 % ?- sorciere(hermione).
 135 % ?- sorcier(harry).
 136 % \end{verbatim}
 137 % \end{scriptsize}
 138
 139 % Prolog répond deux fois vrai.
 140 %  L'assertion proposée est vraie ou fausse ?
 141
 142
 143 Q. 10.
 144 Soit
 145 $f$, $g$ des symboles de fonctions binaire,
 146 $R$ un symbole de relation binaire.
 147 Soit $A$ la formule
 148 $$
 149 \left(\forall z \, .\, R(x,z) \land R(z,y) \right)
 150 \Rightarrow
 151 \left(\exists z \, .\, R(z,y) \lor R(x,z) \right).
 152 $$
 153 Soit $u$, $v$ les termes définis par
 154 $u= f(z,x)$ et
 155 $v= g(x,z)$
 156
 157 Alors on a
 158 $$
 159 A(v/y)(u/x) \equiv
 160 A(u/x)(v(u/x)/y)
 161 $$
 162  L'assertion proposée est vraie ou fausse ?
 163
 164
 165 Q. 11.  Soit $p$, $q$, $r$ trois variables propostionnelles.
 166         La relation $\{p \Rightarrow \neg q , q \} \models \neg p$ est-elle vraie ?
 167
 168
 169 Q. 12.
 170 Dans les clauses
 171 \begin{scriptsize}
 172 \begin{verbatim}
 173 pere_de(Y,Z) :- homme(Y),a_pour_fils(Y,Z).
 174 pere_de(Y,Z) :- homme(Y),a_pour_fille(Y,Z).
 175 \end{verbatim}
 176 \end{scriptsize}
 177
 178 La première clause se traduit en
 179 $$
 180 \forall y,z \, . \, \textit{pere}(y,z) \Leftrightarrow \textit{homme}(y)
 181 \land \textit{a\_pour\_fils}(y,z).
 182 $$
 183  L'assertion proposée est vraie ou fausse ?
 184
 185
 186 % Q. 15. Soit $p$ et $q$ les variables propositionnelles correspondant respectivement à \og il est grand \fg{} et \og il est beau \fg{}.
 187 %       \og{} Il est grand mais il n'est pas beau\fg{}
 188 % peut-elle se traduire par $p \lor \neg q$?
 189
 190
 191 Q. 13. \og $A$ à moins que  $B$ \fg{}
 192 peut-elle être représentée par $ \neg B \lor A $?
 193
 194
 195 Q. 14.  Soit $p$ et $q$, deux variables propostionnelles.
 196         L'énoncé suivant est-il une tautologie?
 197 $
 198 \left((p \Rightarrow q) \Rightarrow (q \Rightarrow p) \right)
 199 \Rightarrow
 200 (q \Leftrightarrow p)$.
 201
 202
 203 Q. 15.
 204 On considère les prédicats Prolog
 205 \verb+parent(X,Y)+, qui est vrai si \verb+X+
 206 est le père ou la mère de \verb+Y+ et
 207 \verb+femme(X)+, qui est vrai si \verb+X+
 208 est est une femme.
 209
 210 \og \verb+X+ est la soeur de \verb+Y+ \fg{} se traduit en prolog par
 211 \begin{scriptsize}
 212 \begin{verbatim}
 213 est_la_soeur_de(X,Y) :- parent(Z,X), parent(Z,Y), femme(X).
 214 \end{verbatim}
 215 \end{scriptsize}
 216
 217  L'assertion proposée est vraie ou fausse ?
 218
 219
 220 Q. 16. \og Il est faux que sa mère est anglaise ou que son père est français \fg{}
 221 est-elle suffisante pour affirmer que
 222 \og sa mère est anglaise ou  son père n'est pas français \fg{}?
 223
 224
 225 Q. 17.
 226 On considère les prédicats Prolog
 227 \verb+parent(X,Y)+, qui est vrai si \verb+X+
 228 est le père ou la mère de \verb+Y+ et
 229 \verb+femme(X)+, qui est vrai si \verb+X+
 230 est est une femme.
 231
 232 \og \verb+X+ est la fille de \verb+Y+ \fg{} se traduit en prolog par
 233 \begin{scriptsize}
 234 \begin{verbatim}
 235 fille(X,Y) :- parent(X,Y), femme(X).
 236 \end{verbatim}
 237 \end{scriptsize}
 238
 239  L'assertion proposée est vraie ou fausse ?
 240
 241
 242 % Q. 21. Soit $p$ et $q$ les variables propositionnelles correspondant respectivement à \og il est grand \fg{} et \og il est beau \fg{}.
 243 %       \og Il n'est ni grand, ni beau \fg{} peut-elle s'écrire $\neg (p \land q )$?
 244
 245
 246 Q. 18.
 247 Dans la formule
 248 $(\forall x \, . \, x \ge 5) \land (\exists y \, . \, y \ge x)$
 249 la variable $x$ est liée.
 250 L'assertion proposée est vraie ou fausse ?
 251
 252 % Q. 23. Une formule propositionnelle $F$ est conséquence logique d'une tautologie.
 253 %        L'affirmation suivante est-elle vraie:
 254 % \og  $F$ est donc une antilogie \fg{}?
 255
 256
 257 Q. 19.  On note $A$ la proposition \og les chiens aboient \fg{} et
 258 $P$ la proposition \og la caravane passe \fg{}. La proposition
 259 \og les chiens aboient à moins que la caravane ne passe \fg{}
 260 peut-elle être représentée par $ \neg P \Rightarrow A $?
 261
 262
 263 Q. 20.  Soit $p$, $q$, $r$ trois variables propostionnelles.
 264         La relation $\{r\} \models p \land q  \Rightarrow r$ est-elle vraie?
 265
 266
 267 Q. 21.
 268 Soit $a$ et $b$ des symboles de constante,
 269 $f$ un symbole de fonction unaire,
 270 $g$ un symbole de fonction binaire et
 271 $S$ un symbole de relation binaire. On donne les expressions suivantes:
 272 \begin{enumerate}
 273 \item \label{enum:term1} $g(a,f(b))$
 274 \item \label{enum:term3} $S(f(a),g(x,f(y)))$
 275 \end{enumerate}
 276
 277 L'expression \ref{enum:term1} contient 1 seul terme
 278  L'assertion proposée est vraie ou fausse ?
 279
 280
 281 Q. 22. On considère les prédicats et constantes suivants avec leur interprétation sur un univers constitué d'individus humains.
 282
 283 \begin{center}
 284 \begin{tabular}{|r|l|}
 285 \hline
 286  prédicat & sens \\
 287 \hline
 288 $\textit{aime}(x,y)$                 & $x$ aime $y$ \\
 289 $\textit{maries}(x,y)$                & $x$ et $y$ sont mariés  \\
 290 $\textit{femme}(x)$                  & $x$ est une femme \\
 291 $\textit{homme}(x)$                  & $x$ est un  homme \\
 292 $\textit{fidele}(x)$                 & $x$ est fidèle \\
 293 $\textit{honete}(x)$                 & $x$ dit la vérité \\
 294 $a$                                  & Alice \\
 295 $b$                                  & Bob \\
 296 $c$                                  & Clinton \\
 297 \hline
 298 \end{tabular}
 299 \end{center}
 300
 301 \og L'époux qui aime son épouse lui est fidèle \fg peut se traduire en
 302
 303 $$
 304 \forall x,y \, . \,
 305 \textit{homme}(x) \land
 306 \textit{femme}(y) \land
 307 \textit{maries}(x,y) \land
 308 \textit{aime}(x,y) \land
 309 \textit{aime}(y,x)
 310 $$
 311
 312
 313
 314 L'assertion proposée est vraie ou fausse ?
 315
 316 Q. 23. On considère les prédicats et constantes suivants avec leur interprétation sur un univers constitué d'individus humains.
 317
 318
 319 \begin{center}
 320 \begin{tabular}{|r|l|}
 321 \hline
 322  prédicat & sens \\
 323 \hline
 324 $\textit{aime}(x,y)$                 & $x$ aime $y$ \\
 325 $\textit{maries}(x,y)$                & $x$ et $y$ sont mariés  \\
 326 $\textit{femme}(x)$                  & $x$ est une femme \\
 327 $\textit{homme}(x)$                  & $x$ est un  homme \\
 328 $\textit{fidele}(x)$                 & $x$ est fidèle \\
 329 $\textit{honete}(x)$                 & $x$ dit la vérité \\
 330 $a$                                  & Alice \\
 331 $b$                                  & Bob \\
 332 $c$                                  & Clinton \\
 333 \hline
 334 \end{tabular}
 335 \end{center}
 336
 337
 338 \og Les femmes aiment toujours les hommes fidèles et qui disent la vérité \fg peut se traduire en
 339
 340 $$
 341 \forall x,y \, . \,
 342 (\textit{homme}(x) \land
 343 \textit{femme}(y) \land
 344 \textit{fidele}(x) \land
 345 \textit{honete}(x)
 346 ) \Rightarrow
 347 \textit{aime}(y,x)
 348 $$
 349
 350 L'assertion proposée est vraie ou fausse ?
 351
 352 Q. 24. On considère les prédicats et constantes suivants avec leur interprétation sur un univers constitué d'individus humains.
 353
 354 \begin{center}
 355 \begin{tabular}{|r|l|}
 356 \hline
 357  prédicat & sens \\
 358 \hline
 359 $\textit{aime}(x,y)$                 & $x$ aime $y$ \\
 360 $\textit{maries}(x,y)$                & $x$ et $y$ sont mariés  \\
 361 $\textit{femme}(x)$                  & $x$ est une femme \\
 362 $\textit{homme}(x)$                  & $x$ est un  homme \\
 363 $\textit{fidele}(x)$                 & $x$ est fidèle \\
 364 $\textit{honete}(x)$                 & $x$ dit la vérité \\
 365 $a$                                  & Alice \\
 366 $b$                                  & Bob \\
 367 $c$                                  & Clinton \\
 368 \hline
 369 \end{tabular}
 370 \end{center}
 371
 372
 373 $$
 374 \exists x \, . \, (\forall y \, . \,
 375   \textit{homme}(x) \land
 376  (\textit{femme}(y) \Rightarrow
 377   \textit{aime}(x,y))
 378 $$
 379
 380 peut se traduire en \og certains hommes sont aimés de toutes les femmes \fg.
 381
 382
 383 L'assertion proposée est vraie ou fausse ?
 384
 385 Q. 25.  L'affirmation \og le Vesuve a ravagé la ville de Pompei en 1999 \fg{}
 386 est-elle une proposition?
 387
 388
 389 Q. 26.
 390 Soit \textit{dodec} le prédicat unaire qui est vrai si son paramètre est un dodécaèdre,
 391 \textit{cube} le prédicat unaire qui est vrai si son paramètre est un cube,
 392 \textit{petit} le prédicat unaire qui est vrai si son paramètre est petit,
 393 \textit{entre} le prédicat ternaire qui est vrai si son premier paramètre est entre le second et le troisième
 394 et
 395 \textit{devant} le prédicat unaire qui est vrai si son premier paramètre est devant son second paramètre.
 396
 397 \og si un cube a quelque chose devant lui alors il est petit \fg{} peut-elle se traduire en
 398 $$
 399 \forall x\, .\,
 400 ( \exists y \, . \, cube(x) \land devant(x,y))
 401 \Rightarrow
 402 petit(x)
 403 $$
 404  L'assertion proposée est vraie ou fausse?
 405
 406
 407 Q. 27.  Soit $p$, $q$, $r$ trois variables propostionnelles.
 408         L'énoncé suivant est-il une tautologie?
 409 $(q \Leftrightarrow p) \Rightarrow
 410 (p \Rightarrow q) \land
 411 (q \Rightarrow p)$.
 412
 413
 414 Q. 28.
 415 Soit \textit{dodec} le prédicat unaire qui est vrai si son paramètre est un dodécaèdre,
 416 \textit{cube} le prédicat unaire qui est vrai si son paramètre est un cube,
 417 \textit{petit} le prédicat unaire qui est vrai si son paramètre est petit,
 418 \textit{entre} le prédicat ternaire qui est vrai si son premier paramètre est entre le second et le troisième
 419 et
 420 \textit{devant} le prédicat unaire qui est vrai si son premier paramètre est devant son second paramètre.
 421 Dans la formule suivante toutes les occurences de x sont liées.
 422 $$
 423 \forall x \, . \,
 424 \textit{dodec}(x) \lor  devant(x, y) \Rightarrow
 425 (
 426 (\exists y \, .\, cube(y) \land \neg devant(x, y))
 427 \land  entre(u,y,x)
 428 )
 429 $$
 430  L'assertion proposée est vraie ou fausse?
 431
 432
 433 % Q. 34. Soit $p$, $q$  les variables propositionnelles correspondant respectivement à \og il est grand \fg{} et \og il est beau \fg{}.
 434 % De plus, \og il  est petit \fg{} signifie qu'il n'est pas grand et
 435 % \og il est moche \fg{} signifie qu'il n'est pas beau.
 436 %       \og il est faux qu'il est petit ou moche \fg{} peut-elle s'écrire
 437 % $ p \land q $.
 438
 439
 440 Q. 29.  Soit $p$, $q$, $r$ trois variables propostionnelles.
 441         L'ensemble $\{p \land q\}$ a-t-il pour conséquence logique $p \lor q$?
 442
 443
 444 Q. 30. \og $B$ est une condition nécessaire pour $A$ \fg{}
 445 peut-elle être représentée par $ \neg B \Rightarrow \neg A$ ?
 446
 447
 448 Q. 31. \og $B$ seulement si  $A$ \fg{}
 449 peut-elle être représentée par $ \neg A \Rightarrow B $?
 450
 451
 452 Q. 32.
 453 En logique des propositions, $P$ se déduit syntaxiquement de
 454 $H_1$, \ldots, $H_n$ si et seulement si
 455 $P$ est une conséquence logique de $H_1$, \ldots, $H_n$.
 456 L'assertion proposée est vraie ou fausse ?
 457
 458 Q. 33. \og $B$ seulement si  $A$ \fg{}
 459 peut-elle être représentée par $ A \lor \neg B$?
 460
 461
 462 % Q. 40. Soit $p$ et $q$ les variables propositionnelles correspondant respectivement à \og il est grand \fg{} et \og il est beau \fg{}.
 463 %       Sachant que \og il  est petit \fg{} signifie qu'il n'est pas grand,
 464 % \og il est grand ou il est petit et beau \fg{} peut-elle s'écrire
 465 % $ (p \lor \neg p) \land q $?
 466
 467
 468 Q. 34.
 469 Soit la démonstration  syntaxique suivante: \newline
 470 \begin{tabular}{lll}
 471 \multicolumn{3}{l}{Démonstration}\\
 472 1.&$\neg B \Rightarrow \neg A$ &$H_1$ \\
 473 2.&$A$ &$H_2$ \\
 474 3.&\_\_\_\_\_ &\_\_\_\_\_ \\
 475 4.&\_\_\_\_\_ &\_\_\_\_\_ \\
 476 5.&$\neg\neg B$ &réduction de l'absurde entre 4. et 1. \\
 477 6.&$\neg \neg B \Rightarrow B $&Axiome 9.\\
 478 7.& $B$ &mp entre 5. et 6.
 479 \end{tabular}
 480 Si elle était complète cela permetrait
 481 démontrer syntaxiquement le théorème de la contraposée. Vrai ou faux ?
 482
 483
 484 Q. 35.  Soit $p$, $q$, $r$ trois variables propostionnelles.
 485         La relation $\{ p \Rightarrow q \lor r ,  \neg q \} \models  p \lor r $ est-elle vraie?
 486
 487
 488 Q. 36.
 489 On considère la base de connaissances suivante:
 490 \begin{scriptsize}
 491 \begin{verbatim}
 492 parent(pam,bob).
 493 parent(tom,bob).
 494 parent(tom,liz).
 495 parent(bob,ann).
 496 parent(bob,pat).
 497 parent(pat,jim).
 498
 499 ancetre(X,Z) :- parent(X,Z).
 500 ancetre(X,Z) :- parent(X,Y),ancetre(Y,Z).
 501 \end{verbatim}
 502 \end{scriptsize}
 503
 504 On soumet la requête:
 505 \begin{scriptsize}
 506 \begin{verbatim}
 507 ?- ancetre(pam,X).
 508 \end{verbatim}
 509 \end{scriptsize}
 510
 511 Prolog donne 4 réponses distinctes et échoue.
 512  L'assertion proposée est vraie ou fausse ?
 513
 514
 515 Q. 37. \og Il est faux que sa mère est anglaise ou que son père est français \fg{}
 516 est-elle équivalente à
 517 \og sa mère est anglaise ou son père n'est pas français \fg{}?
 518
 519
 520 Q. 38.  Soit $p$, $q$, $r$ trois variables propostionnelles.
 521         L'énoncé suivant est-il une tautologie?
 522 $(p \lor q) \land r \Leftarrow (p \lor r) \land (q \lor r)$.
 523
 524
 525 Q. 39. \og $B$ seulement si $A$ \fg{}
 526 peut-elle être représentée par $ A \Rightarrow B$ ?
 527
 528
 529 % Q. 47. Soit $p$, $q$  les variables propositionnelles correspondant respectivement à \og il est grand \fg{} et \og il est beau \fg{}.
 530 % De plus, \og il  est petit \fg{} signifie qu'il n'est pas grand et
 531 % \og il est moche \fg{} signifie qu'il n'est pas beau.
 532 %       \og il est faux qu'il est petit ou moche \fg{} peut-elle s'écrire
 533 % $ \neg (\neg p \lor \neg q)$?
 534
 535
 536 Q. 40. \og $A$ à moins que  $B$ \fg{}
 537 peut-elle être représentée par $ B \lor A $?
 538
 539
 540 Q. 41.  La négation de \og ce triangle est rectangle donc ce triangle possède un angle droit \fg{}
 541 est-elle  \og ce triangle ne possède pas un angle droit et pourtant il est rectangle\fg{}
 542
 543
 544 Q. 42.
 545 Soit \textit{dodec} le prédicat unaire qui est vrai si son paramètre est un dodécaèdre,
 546 \textit{cube} le prédicat unaire qui est vrai si son paramètre est un cube,
 547 \textit{petit} le prédicat unaire qui est vrai si son paramètre est petit,
 548 \textit{entre} le prédicat ternaire qui est vrai si son premier paramètre est entre le second et le troisième
 549 et
 550 \textit{devant} le prédicat unaire qui est vrai si son premier paramètre est devant son second paramètre.
 551
 552 Les formules
 553 $$
 554 \exists x\, .\,  dodec(x) \land petit(x) \textrm{ et }
 555 \exists x \, .\, dodec(x) \Rightarrow petit(x)
 556 $$
 557 n'ont jamais la même valeur de vérité.
 558  L'assertion proposée est vraie ou fausse?
 559
 560
 561 Q. 43.
 562 Dans la formule
 563 $P(a) \Rightarrow Q(a)$
 564 la variable $a$ n'est pas liée.
 565 L'assertion proposée est vraie ou fausse ?
 566
 567 Q. 44.  Soit $p$, $q$, $r$ trois variables propostionnelles.
 568         L'ensemble $p \land q $ est-elle une  conséquence logique de $\{p,q\}$?
 569
 570
 571 Q. 45.
 572 Dans les clauses
 573 \begin{scriptsize}
 574 \begin{verbatim}
 575 pere_de(Y,Z) :- homme(Y),a_pour_fils(Y,Z).
 576 pere_de(Y,Z) :- homme(Y),a_pour_fille(Y,Z).
 577 \end{verbatim}
 578 \end{scriptsize}
 579
 580 L'ensemble des deux clauses se traduit en
 581 $$
 582 \forall y,z \, . \, \textit{pere}(y,z) \Leftarrow
 583 (\textit{homme}(y) \land \textit{a\_pour\_fils}(y,z))
 584 \lor
 585 (\textit{homme}(y) \land \textit{a\_pour\_fille}(y,z))
 586 $$
 587  L'assertion proposée est vraie ou fausse ?
 588
 589
 590 Q. 46.
 591 On considère la base de connaissance suivante:
 592 \begin{scriptsize}
 593 \begin{verbatim}
 594 parent(pam,bob).
 595 parent(tom,bob).
 596 parent(tom,liz).
 597 parent(bob,ann).
 598 parent(bob,pat).
 599 parent(pat,jim).
 600 \end{verbatim}
 601 \end{scriptsize}
 602
 603 Au requètes successives:
 604
 605 \begin{scriptsize}
 606 \begin{verbatim}
 607 ?- parent(jim,X).
 608 ?- parent(X,jim).
 609 ?- parent(pam,X), parent(X,pat).
 610 ?- parent(pam,X), parent(X,Y), parent(Y,jim).
 611 \end{verbatim}
 612 \end{scriptsize}
 613
 614 Prolog répond au moins deux fois faux
 615  L'assertion proposée est vraie ou fausse ?
 616
 617
 618 Q. 47.
 619 Soit $a$ et $b$ des symboles de constante,
 620 $f$ un symbole de fonction unaire,
 621 $g$ un symbole de fonction binaire et
 622 $S$ un symbole de relation binaire. On donne les expressions suivantes:
 623 \begin{enumerate}
 624 \item \label{enum:term1a} $g(a,f(b))$
 625 \item \label{enum:term3a} $S(f(a),g(x,f(y)))$
 626 \end{enumerate}
 627
 628 L'expression \ref{enum:term3a} est un terme complexe.
 629  L'assertion proposée est vraie ou fausse ?
 630
 631
 632 % Q. 56. Une formule propositionnelle $F$ a pour conséquence logique une tautologie.
 633 %        L'affirmation suivante est-elle vraie:
 634 % \og  $F$ est donc une antilogie \fg{}?
 635
 636
 637 Q. 48.
 638 Une base de connaissance Prolog est un ensemble de faits, de règles
 639 et de requêtes.
 640  L'assertion proposée est vraie ou fausse ?
 641
 642
 643 Q. 49. On considère les prédicats et constantes suivants avec leur interprétation sur un univers constitué d'individus humains.
 644
 645 \begin{center}
 646 \begin{tabular}{|r|l|}
 647 \hline
 648  prédicat & sens \\
 649 \hline
 650 $\textit{aime}(x,y)$                 & $x$ aime $y$ \\
 651 $\textit{maries}(x,y)$                & $x$ et $y$ sont mariés  \\
 652 $\textit{femme}(x)$                  & $x$ est une femme \\
 653 $\textit{homme}(x)$                  & $x$ est un  homme \\
 654 $\textit{fidele}(x)$                 & $x$ est fidèle \\
 655 $\textit{honete}(x)$                 & $x$ dit la vérité \\
 656 $a$                                  & Alice \\
 657 $b$                                  & Bob \\
 658 $c$                                  & Clinton \\
 659 \hline
 660 \end{tabular}
 661 \end{center}
 662
 663 $$
 664 \forall x \, . \,
 665  \textit{femme}(x) \Rightarrow
 666  (\textit{aime}(x,b) \lor
 667   \textit{aime}(x,c))
 668 $$
 669
 670 peut se traduire en \og Si une femme n'aime pas Clinton, alors elle aime Bob \fg.
 671
 672
 673 L'assertion proposée est vraie ou fausse ?
 674
 675 % Q. 59. Une formule propositionnelle $F$ est conséquence logique d'une tautologie.
 676 %        L'affirmation suivante est-elle vraie:
 677 % \og  $F$ est donc une tautologie \fg{}?
 678
 679
 680 Q. 50.
 681 Soit $a$ et $b$ des symboles de constante,
 682 $f$ un symbole de fonction unaire,
 683 $g$ un symbole de fonction binaire et
 684 $S$ un symbole de relation binaire. On donne les expressions suivantes:
 685 \begin{enumerate}
 686 \item \label{enum:term1b} $g(a,f(b))$
 687 \item \label{enum:term3b} $S(f(a),g(x,f(y)))$
 688 \end{enumerate}
 689
 690 L'expression \ref{enum:term1} contient quatre termes
 691  L'assertion proposée est vraie ou fausse ?
 692
 693
 694 Q. 51.
 695 Soit
 696 $f$, $g$ des symboles de fonctions binaire,
 697 $R$ un symbole de relation binaire.
 698 Soit $A$ la formule
 699 $$
 700 \left(\forall z \, .\, R(x,z) \land R(z,y) \right)
 701 \Rightarrow
 702 \left(\exists z \, .\, R(z,y) \lor R(x,z) \right).
 703 $$
 704 Soit $u$, $v$ les termes définis par
 705 $u= f(z,x)$ et
 706 $v= g(x,z)$
 707
 708 Alors on a
 709 $$
 710 A(u/x)(v/y) \equiv
 711 A(v/y)(u(v/y)/x)
 712 $$
 713  L'assertion proposée est vraie ou fausse ?
 714
 715
 716 Q. 52. Si je travaille, je ne peux pas étudier;
 717 Soit je travaille, soit je suis reçu en mathématiques;
 718 j'ai été reçu en mathématiques.
 719 Donc j'ai étudié.
 720  Le raisonnement proposé est-il incorrect?
 721
 722
 723 Q. 53.
 724 Soit \textit{dodec} le prédicat unaire qui est vrai si son paramètre est un dodécaèdre,
 725 \textit{cube} le prédicat unaire qui est vrai si son paramètre est un cube,
 726 \textit{petit} le prédicat unaire qui est vrai si son paramètre est petit,
 727 \textit{entre} le prédicat ternaire qui est vrai si son premier paramètre est entre le second et le troisième
 728 et
 729 \textit{devant} le prédicat unaire qui est vrai si son premier paramètre est devant son second paramètre.
 730 Dans la formule suivante $y$ et $u$ ont des occurences libres
 731 $$
 732 \forall x \, . \,
 733 \textit{dodec}(x) \lor  devant(x, y) \Rightarrow
 734 (
 735 (\exists y \, .\, cube(y) \land \neg devant(x, y))
 736 \land  entre(u,y,x)
 737 )
 738 $$
 739  L'assertion proposée est vraie ou fausse?
 740
 741
 742 % Q. 64. Une formule propositionnelle $F$ a pour conséquence logique une antilogie.
 743 %       On ne peut donc rien dire de $F$.
 744
 745
 746 Q. 54. \og $A$ à moins que  $B$ \fg{}
 747 peut-elle être représentée par $ B \Rightarrow A $?
 748
 749
 750 Q. 55.  L'affirmation \og le Vesuve ferra une irruption en 2010\fg{}
 751 est-elle une proposition?
 752
 753
 754 Q. 56.
 755 \og Il est faux qu'il ne fait pas froid ou qu'il pleut \fg{}
 756 est-elle équivalente à   \og il fait froid mais il ne pleut pas \fg{}?
 757
 758
 759 % Q. 68. Soit $p$ et $q$ les variables propositionnelles correspondant respectivement à \og il est grand \fg{} et \og il est beau \fg{}.
 760 %       Sachant que \og il  est petit \fg{} signifie qu'il n'est pas grand,
 761 % \og il est grand ou il est petit et beau \fg{} peut-elle s'écrire
 762 % $ p \lor q $?
 763
 764
 765 % Q. 69. Une formule propositionnelle $F$ est conséquence logique d'une tautologie.
 766 %        L'affirmation suivante est-elle vraie:
 767 % \og  On ne peut donc rien dire de $F$ \fg{}?
 768
 769
 770 % Q. 70.
 771 % Les termes $p(f(X),X)$ et $p(Y,Y)$ sont  unifiables.
 772 %  L'assertion proposée est vraie ou fausse ?
 773
 774
 775 % Q. 71.
 776 % Soit \textit{dodec} le prédicat unaire qui est vrai si son paramètre est un dodécaèdre,
 777 % \textit{cube} le prédicat unaire qui est vrai si son paramètre est un cube,
 778 % \textit{petit} le prédicat unaire qui est vrai si son paramètre est petit,
 779 % \textit{entre} le prédicat ternaire qui est vrai si son premier paramètre est entre le second et le troisième
 780 % et
 781 % \textit{devant} le prédicat unaire qui est vrai si son premier paramètre est devant son second paramètre.
 782
 783 % \og les seuls grands cubes sont b et c \fg{} peut-elle se traduire en
 784 % $$
 785 % \forall x \, .\,
 786 % (\neg petit(x) \land cube(x))
 787 % \leftrightarrow
 788 %  ( x = b \lor  x = c)
 789 % $$
 790 %  L'assertion proposée est vraie ou fausse?
 791
 792
 793 % Q. 72.
 794 % On considère la base de connaissances suivante:
 795 % \begin{scriptsize}
 796 % \begin{verbatim}
 797 % parent(pam,bob).
 798 % parent(tom,bob).
 799 % parent(tom,liz).
 800 % parent(bob,ann).
 801 % parent(bob,pat).
 802 % parent(pat,jim).
 803
 804 % ancetre(X,Z) :- parent(X,Z).
 805 % ancetre(X,Z) :- parent(X,Y),ancetre(Y,Z).
 806 % \end{verbatim}
 807 % \end{scriptsize}
 808
 809 % On soumet la requête:
 810 % \begin{scriptsize}
 811 % \begin{verbatim}
 812 % ?- ancetre(pam,X).
 813 % \end{verbatim}
 814 % \end{scriptsize}
 815
 816 % Prolog donne 1 réponse et échoue.
 817 %  L'assertion proposée est vraie ou fausse ?
 818
 819
 820 % Q. 73.
 821 % On considère la base de connaissance suivante:
 822 % \begin{scriptsize}
 823 % \begin{verbatim}
 824 % a_une_baguette(harry).
 825 % joueur_de_Quidditch(harry).
 826 % sorcier(ron).
 827 % sorcier(X) :- a_un_balai(X), a_une_baguette(X).
 828 % a_un_balai(X) :- joueur_de_Quidditch(X).
 829 % \end{verbatim}
 830 % \end{scriptsize}
 831
 832 % Lorsqu'on soumet successivement les requêtes suivantes:
 833
 834 % \begin{scriptsize}
 835 % \begin{verbatim}
 836 % ?- sorcier(ron).
 837 % ?- sorciere(ron).
 838 % ?- sorcier(hermione).
 839 % ?- sorciere(hermione).
 840 % ?- sorcier(harry).
 841 % \end{verbatim}
 842 % \end{scriptsize}
 843
 844 % Prolog répond trois fois faux.
 845 %  L'assertion proposée est vraie ou fausse ?
 846
 847
 848 % Q. 74. \og $A$ à moins que  $B$ \fg{}
 849 % peut-elle être représentée par $ B \Rightarrow A $?
 850
 851
 852 % Q. 75.
 853 % Soit \textit{dodec} le prédicat unaire qui est vrai si son paramètre est un dodécaèdre,
 854 % \textit{cube} le prédicat unaire qui est vrai si son paramètre est un cube,
 855 % \textit{petit} le prédicat unaire qui est vrai si son paramètre est petit,
 856 % \textit{entre} le prédicat ternaire qui est vrai si son premier paramètre est entre le second et le troisième
 857 % et
 858 % \textit{devant} le prédicat unaire qui est vrai si son premier paramètre est devant son second paramètre.
 859
 860 % \og Il y a au moins deux objets qui n’ont rien derrière eux \fg{} peut-elle se traduire en
 861 % $$
 862 % \exists x,y\, .\,
 863 % x \neq y \land
 864 %  (\forall w\, .\, (w = x \lor  w = y) \rightarrow (\forall z  ¬devant(z, w)))
 865 % $$
 866 %  L'assertion proposée est vraie ou fausse?
 867
 868
 869 % Q. 76. Une formule propositionnelle $F$ a pour conséquence logique une antilogie.
 870 %       L'affirmation suivante est-elle vraie:
 871 % \og $F$ est donc une tautologie \fg{}?
 872
 873
 874 % Q. 77. \og $B$ est une condition nécessaire pour $A$ \fg{}
 875 % peut-elle être représentée par $ B \Rightarrow A$ ?
 876
 877
 878 % Q. 78.  Soit $p$, $q$, $r$ trois variables propostionnelles.
 879 %       La relation $\{\neg p \Rightarrow q \lor r , \neg r, \neg q \} \models \neg p $ est-elle vraie?
 880
 881
 882 % Q. 79.
 883 % Soit la démonstration  syntaxique suivante: \newline
 884 % \begin{tabular}{lll}
 885 % \multicolumn{3}{l}{Démonstration}\\
 886 % 1.&$\neg B \Rightarrow \neg A$ &$H_1$ \\
 887 % 2.&$A$ &$H_2$ \\
 888 % 3.&\_\_\_\_\_ &\_\_\_\_\_ \\
 889 % 4.&\_\_\_\_\_ &\_\_\_\_\_ \\
 890 % 5.&$\neg\neg B$ &réduction de l'absurde entre 4. et 1. \\
 891 % 6.&$\neg \neg B \Rightarrow B$ &Axiome 9.\\
 892 % 7.& $B$ &mp entre 5. et 6.
 893 % \end{tabular}
 894 % Si elle était complète cela permetrait de
 895 % démontrer syntaxiquement
 896 % $(\neg B \Rightarrow \neg A) \Rightarrow (A \Rightarrow B)
 897 % $.
 898 %  L'assertion proposée est vraie ou fausse ?
 899
 900
 901 % Q. 80. Une formule propositionnelle $F$ est conséquence logique d'une antilogie.
 902 %        L'affirmation suivante est-elle vraie:
 903 % \og  On ne peut donc rien dire de $F$ \fg{}?
 904
 905
 906 \section{Raisonnements écrits (1h15)}
 907
 908 \subsection{Calcul des prédicats}
 909 Dans la série suivante, chaque formule est logiquement équivalente à une et
 910 une seule autre. Retrouver les paires équivalentes et justifier.
 911 \begin{eqnarray}
 912 & \forall x\, . \, \neg p(x) \land q(x) &  \\
 913 & \neg (\forall x\, . \, p(x) \Rightarrow q(x) ) &  \\
 914 & \exists x\, . \, \neg p(x) \lor \neg  q(x)  &  \\
 915 & \exists x\, . \, \neg p(x) \lor  q(x)  &  \\
 916 & (\exists x\, . \, \neg p(x)) \lor (\exists x\, . \,  q(x))  &  \\
 917 & (\exists x\, . \, \neg p(x)) \lor \neg (\exists x\, . \,\neg  q(x))  &  \\
 918 & \neg (\exists x\, . \, p(x)) \land (\forall x\, . \,  q(x))  &  \\
 919 & \exists x\, . \, p(x) \Rightarrow \neg q(x)  &  \\
 920 & \neg (\forall x\, . \, p(x)) \lor (\forall x\, . \,  q(x))  &  \\
 921 & \exists x\, . \, p(x) \land \neg  q(x)  &
 922 \end{eqnarray}
 923
 924
 925 % initiation à la logique formelle, lucas, berlanger...
 926
 927 \subsection{Prolog}
 928 \subsubsection{Graphe}
 929 \begin{figure}
 930 \begin{center}
 931 \includegraphics[width=3cm]{graph.eps}
 932 \end{center}
 933 \caption{Graphe à modéliser en Prolog }
 934 \label{Fig:graph}
 935 \end{figure}
 936
 937 On considère le graphe donné à la figure~\ref{Fig:graph}.
 938 \begin{enumerate}
 939 \item Modéliser ce graphe à l'aide du prédicat $\textit{arc}(X,Y)$ qui est
 940   vrai s'il existe un arc depuis le noeud $X$ vers le noeud $Y$.
 941 \item Construire le prédicat $\textit{chemin}(X,Y)$ qui est vrai
 942 s'il existe un chemin, c'est à dire une suite continue et éventuellement vide
 943 d'arcs entre les noeuds $X$ et $Y$ du graphe.
 944 \item Quelle requête Prolog effectueriez-vous pour obtenir tous les noeuds
 945   accessibles à partir du noeud a.
 946 \end{enumerate}
 947
 948 \subsubsection{Liste d'entiers naturels}
 949 \begin{enumerate}
 950 \item Définir un prédicat $\textit{pair}(X)$ qui est vrai si $X$ est un
 951   nombre pair.
 952
 953 \item Définir un prédicat $\textit{membres\_pairs}(L,Lp)$ qui est vrai
 954   si la liste $Lp$ est composée des éléments pairs de la liste
 955   $L$ et dans le même ordre.
 956
 957 \item On considère le prédicat Prolog $\textit{append}(L1,L2,L3)$ qui est
 958 est vrai si $L3$ est la concaténation des listes $L1$ et $L2$.
 959 Définir le prédicat $\textit{inverse}(L,Lp)$ qui est vrai si $Lp$ est la liste
 960 $L$ retournée.
 961 \end{enumerate}
 962
 963 \subsection{Déduction syntaxique}
 964 Dans ce qui suit, $A$, $B$, $C$ et $D$ sont quatre variables propositionnelles.
 965
 966 \begin{enumerate}
 967 \item Démontrer le théorème suivant par déduction syntaxique:
 968 $$
 969 (
 970 A \Rightarrow ( B \land C)
 971 )
 972 \Rightarrow
 973 (A \Rightarrow B) \land
 974 (A \Rightarrow C)
 975 $$
 976 On pourra utiliser le théorème de transitivité de l'implication.
 977
 978 \item Effectuer la démonstration sous hypothèse suivante:
 979 $$
 980 \{
 981 C \Rightarrow \neg B ,
 982 C \lor D,
 983 D \Rightarrow \neg B,
 984 A \Rightarrow B
 985 \}
 986 \vdash \neg A
 987 $$
 988 On pourra utiliser le théorème de la contraposée et la règle de disjonction
 989 des cas.
 990
 991 \end{enumerate}
 992 \newpage
 993 \section*{Réponses au QCM}
 994 \noindent Nom:............................\\
 995 \noindent Prénom:............................\\
 996
 997
 998 \begin{Huge}
 999
1000 \begin{center}
1001 \begin{tabular}{|l|c|c||l|c|c||l|c|c|}
1002 \hline
1003 Numéro & V & F & Numéro & V & F & Numéro & V & F \\
1004 \hline
1005 Q. 1 & &  & Q. 2 & &  & Q. 3 & &  \\
1006 \hline
1007 Q. 4 & &  & Q. 5 & &  & Q. 6 & &  \\
1008 \hline
1009 Q. 7 & &  & Q. 8 & &  & Q. 9 & &  \\
1010 \hline
1011 Q. 10 & &  & Q. 11 & &  & Q. 12 & &  \\
1012 \hline
1013 Q. 13 & &  & Q. 14 & &  & Q. 15 & &  \\
1014 \hline
1015 Q. 16 & &  & Q. 17 & &  & Q. 18 & &  \\
1016 \hline
1017 Q. 19 & &  & Q. 20 & &  & Q. 21 & &  \\
1018 \hline
1019 Q. 22 & &  & Q. 23 & &  & Q. 24 & &  \\
1020 \hline
1021 Q. 25 & &  & Q. 26 & &  & Q. 27 & &  \\
1022 \hline
1023 Q. 28 & &  & Q. 29 & &  & Q. 30 & &  \\
1024 \hline
1025 Q. 31 & &  & Q. 32 & &  & Q. 33 & &  \\
1026 \hline
1027 Q. 34 & &  & Q. 35 & &  & Q. 36 & &  \\
1028 \hline
1029 Q. 37 & &  & Q. 38 & &  & Q. 39 & &  \\
1030 \hline
1031 Q. 40 & &  & Q. 41 & &  & Q. 42 & &  \\
1032 \hline
1033 Q. 43 & &  & Q. 44 & &  & Q. 45 & &  \\
1034 \hline
1035 Q. 46 & &  & Q. 47 & &  & Q. 48 & &  \\
1036 \hline
1037 Q. 49 & &  & Q. 50 & &  & Q. 51 & &  \\
1038 \hline
1039 Q. 52 & &  & Q. 53 & &  & Q. 54 & &  \\
1040 \hline
1041 Q. 55 & &  & Q. 56 & &  & & &  \\
1042 \hline
1043
1044 \end{tabular}
1045 \end{center}
1046
1047
1048
1049
1050 \end{Huge}
1051
1052 \end{document}