synthese ensemble13

[cours-maths-dis.git] / partiels / S2_0905 / partiel.tex

\documentclass[12pt]{article}
\usepackage[a4paper]{geometry}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage{a4}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{framed}
\usepackage{dsfont}
\usepackage[amsmath,thmmarks,thref,framed]{ntheorem}
\usepackage[dvips]{graphicx}
\usepackage{epsfig}
\usepackage{calc}
\usepackage{tabls}
\usepackage{slashbox}
\usepackage{times}
\usepackage{tabularx}
\usepackage{textcomp}
\title{
Partiel de mathématiques discrètes, semestre 2, juin 2009.\\
Durée : 3 heures.} 
\date{}
\geometry{hmargin=1cm, vmargin= 1cm}
\author{\sc{Couchot}, J.-F.}
\begin{document}
\maketitle



Les supports  de TDs et de TP sont autorisés; téléphones et calculatrices sont
interdits.

\section{QCM (1h45)}


% Q. 1. Une formule propositionnelle $F$ a pour conséquence logique une tautologie.
%        L'affirmation suivante est-elle vraie:
% \og  On ne peut donc rien dire de $F$ \fg{}?
         

Q. 1.  L'affirmation \og il fait beau aujourd'hui  donc il ne pleuvra pas dans dix jours \fg{}
est-elle une proposition?
         

Q. 2. 
Soit la démonstration  syntaxique suivante: \newline
\begin{tabular}{lll}
\multicolumn{3}{l}{Démonstration}\\
1.&$\neg B \Rightarrow \neg A$ &$H_1$ \\
2.&$A$ &$H_2$ \\
3.&\_\_\_\_\_ &\_\_\_\_\_ \\
4.&\_\_\_\_\_ &\_\_\_\_\_ \\
5.&$\neg\neg B$ &réduction de l'absurde entre 4. et 1. \\
6.&$\neg \neg B \Rightarrow B $ &Axiome 9.\\
7.& B &mp entre 5. et 6.
\end{tabular}
La démonstration est correcte si en 3. et 4. on a: \newline
\begin{tabular}{lll}
3.&$\neg \neg A \Rightarrow  \neg \neg B $ &théoreme de la contraposée sur 1. \\
4.&$\neg \neg A \Rightarrow A $ &Axiome 9.
\end{tabular}
\\ 

Q. 3. 
\og \emph{Si la paix survient, alors il y aura une crise économique
à moins que le pays se dote d'armes nouvelles ou bien exécute
un large programme d'investissement intérieur dans les secteurs de
l'enseignement, de la santé et de la lutte contre la pauvreté.
Il n'est pas possible de se mettre d'accord sur les objectifs
que peut se donner un large programme d'investissement intérieur.
Donc si la paix survient et qu'il n'y a pas de crise économique,
le pays doit se doter d'armes nouvelles.} \fg{}
         Le raisonnement proposé est-il correct?
         

Q. 4. La relation $\{P,Q\} \vdash R$  se lit-elle
\og $R$ est une conséquence logique de l'ensemble
                     $\{P,Q\}$ \fg{}?
                      

Q. 5.  Soit $p$, $q$, $r$ trois variables propostionnelles.
        L'énoncé suivant est-il une tautologie?
$  (p \lor q) \land (p \lor r) \Rightarrow p \lor (q \land r)$.
         

Q. 6.  Soit $p$ et $q$, deux variables propostionnelles.
        L'énoncé suivant est-il une tautologie?
$
(p \Rightarrow q) \Rightarrow
\left(
(q \Rightarrow p)
\Rightarrow
(q \Leftrightarrow p)
\right)$.
         

Q. 7. La formule
$\forall x \,.\, x > 0 \Rightarrow
  (\exists y \, . \, e^y = x )
$
est vraie sur l'univers $\mathds{R}$.
L'assertion proposée est vraie ou fausse ? 

Q. 8. \og $A$ à moins que  $B$ \fg{}
peut-elle être représentée par $ \neg A \Rightarrow B$?
         

Q. 9. 
Soit $x$ et $y$ des entiers naturels.
$\exists x \, .\, ( \forall y \, . \,  y  \neq x \Rightarrow  x  <1 )$
est vraie.
L'assertion proposée est vraie ou fausse ? 

% Q. 11. 
% On considère la base de connaissance suivante:
% \begin{scriptsize}
% \begin{verbatim}
% a_une_baguette(harry).
% joueur_de_Quidditch(harry).
% sorcier(ron).
% sorcier(X) :- a_un_balai(X), a_une_baguette(X).
% a_un_balai(X) :- joueur_de_Quidditch(X).
% \end{verbatim}
% \end{scriptsize}

% Lorsqu'on soumet successivement les requêtes suivantes:

% \begin{scriptsize}
% \begin{verbatim}
% ?- sorcier(ron).
% ?- sorciere(ron).
% ?- sorcier(hermione).
% ?- sorciere(hermione).
% ?- sorcier(harry).
% \end{verbatim}
% \end{scriptsize}

% Prolog répond deux fois vrai.
%  L'assertion proposée est vraie ou fausse ?
   

Q. 10. 
Soit
$f$, $g$ des symboles de fonctions binaire,
$R$ un symbole de relation binaire.
Soit $A$ la formule
$$
\left(\forall z \, .\, R(x,z) \land R(z,y) \right)
\Rightarrow
\left(\exists z \, .\, R(z,y) \lor R(x,z) \right).
$$
Soit $u$, $v$ les termes définis par
$u= f(z,x)$ et
$v= g(x,z)$

Alors on a
$$
A(v/y)(u/x) \equiv
A(u/x)(v(u/x)/y)
$$
 L'assertion proposée est vraie ou fausse ?
   

Q. 11.  Soit $p$, $q$, $r$ trois variables propostionnelles.
        La relation $\{p \Rightarrow \neg q , q \} \models \neg p$ est-elle vraie ?
         

Q. 12. 
Dans les clauses
\begin{scriptsize}
\begin{verbatim}
pere_de(Y,Z) :- homme(Y),a_pour_fils(Y,Z).
pere_de(Y,Z) :- homme(Y),a_pour_fille(Y,Z).
\end{verbatim}
\end{scriptsize}

La première clause se traduit en
$$
\forall y,z \, . \, \textit{pere}(y,z) \Leftrightarrow \textit{homme}(y)
\land \textit{a\_pour\_fils}(y,z).
$$
 L'assertion proposée est vraie ou fausse ?
   

% Q. 15. Soit $p$ et $q$ les variables propositionnelles correspondant respectivement à \og il est grand \fg{} et \og il est beau \fg{}.
%       \og{} Il est grand mais il n'est pas beau\fg{}
% peut-elle se traduire par $p \lor \neg q$?
                 

Q. 13. \og $A$ à moins que  $B$ \fg{} 
peut-elle être représentée par $ \neg B \lor A $?
         

Q. 14.  Soit $p$ et $q$, deux variables propostionnelles.
        L'énoncé suivant est-il une tautologie?
$
\left((p \Rightarrow q) \Rightarrow (q \Rightarrow p) \right)
\Rightarrow
(q \Leftrightarrow p)$.
         

Q. 15. 
On considère les prédicats Prolog
\verb+parent(X,Y)+, qui est vrai si \verb+X+
est le père ou la mère de \verb+Y+ et
\verb+femme(X)+, qui est vrai si \verb+X+
est est une femme.

\og \verb+X+ est la soeur de \verb+Y+ \fg{} se traduit en prolog par
\begin{scriptsize}
\begin{verbatim}
est_la_soeur_de(X,Y) :- parent(Z,X), parent(Z,Y), femme(X).
\end{verbatim}
\end{scriptsize}

 L'assertion proposée est vraie ou fausse ?
   

Q. 16. \og Il est faux que sa mère est anglaise ou que son père est français \fg{}
est-elle suffisante pour affirmer que
\og sa mère est anglaise ou  son père n'est pas français \fg{}?
         

Q. 17. 
On considère les prédicats Prolog
\verb+parent(X,Y)+, qui est vrai si \verb+X+
est le père ou la mère de \verb+Y+ et
\verb+femme(X)+, qui est vrai si \verb+X+
est est une femme.

\og \verb+X+ est la fille de \verb+Y+ \fg{} se traduit en prolog par
\begin{scriptsize}
\begin{verbatim}
fille(X,Y) :- parent(X,Y), femme(X).
\end{verbatim}
\end{scriptsize}

 L'assertion proposée est vraie ou fausse ?
   

% Q. 21. Soit $p$ et $q$ les variables propositionnelles correspondant respectivement à \og il est grand \fg{} et \og il est beau \fg{}.
%       \og Il n'est ni grand, ni beau \fg{} peut-elle s'écrire $\neg (p \land q )$?
         

Q. 18. 
Dans la formule
$(\forall x \, . \, x \ge 5) \land (\exists y \, . \, y \ge x)$
la variable $x$ est liée.
L'assertion proposée est vraie ou fausse ? 

% Q. 23. Une formule propositionnelle $F$ est conséquence logique d'une tautologie.
%        L'affirmation suivante est-elle vraie:
% \og  $F$ est donc une antilogie \fg{}?
         

Q. 19.  On note $A$ la proposition \og les chiens aboient \fg{} et
$P$ la proposition \og la caravane passe \fg{}. La proposition
\og les chiens aboient à moins que la caravane ne passe \fg{} 
peut-elle être représentée par $ \neg P \Rightarrow A $?
         

Q. 20.  Soit $p$, $q$, $r$ trois variables propostionnelles.
        La relation $\{r\} \models p \land q  \Rightarrow r$ est-elle vraie?
         

Q. 21. 
Soit $a$ et $b$ des symboles de constante,
$f$ un symbole de fonction unaire,
$g$ un symbole de fonction binaire et
$S$ un symbole de relation binaire. On donne les expressions suivantes:
\begin{enumerate}
\item \label{enum:term1} $g(a,f(b))$
\item \label{enum:term3} $S(f(a),g(x,f(y)))$
\end{enumerate}

L'expression \ref{enum:term1} contient 1 seul terme
 L'assertion proposée est vraie ou fausse ?
   

Q. 22. On considère les prédicats et constantes suivants avec leur interprétation sur un univers constitué d'individus humains.

\begin{center}
\begin{tabular}{|r|l|}
\hline
 prédicat & sens \\
\hline
$\textit{aime}(x,y)$                 & $x$ aime $y$ \\
$\textit{maries}(x,y)$                & $x$ et $y$ sont mariés  \\
$\textit{femme}(x)$                  & $x$ est une femme \\
$\textit{homme}(x)$                  & $x$ est un  homme \\
$\textit{fidele}(x)$                 & $x$ est fidèle \\
$\textit{honete}(x)$                 & $x$ dit la vérité \\
$a$                                  & Alice \\
$b$                                  & Bob \\
$c$                                  & Clinton \\
\hline
\end{tabular}
\end{center}

\og L'époux qui aime son épouse lui est fidèle \fg peut se traduire en

$$
\forall x,y \, . \,
\textit{homme}(x) \land
\textit{femme}(y) \land
\textit{maries}(x,y) \land
\textit{aime}(x,y) \land
\textit{aime}(y,x)
$$



L'assertion proposée est vraie ou fausse ? 

Q. 23. On considère les prédicats et constantes suivants avec leur interprétation sur un univers constitué d'individus humains.


\begin{center}
\begin{tabular}{|r|l|}
\hline
 prédicat & sens \\
\hline
$\textit{aime}(x,y)$                 & $x$ aime $y$ \\
$\textit{maries}(x,y)$                & $x$ et $y$ sont mariés  \\
$\textit{femme}(x)$                  & $x$ est une femme \\
$\textit{homme}(x)$                  & $x$ est un  homme \\
$\textit{fidele}(x)$                 & $x$ est fidèle \\
$\textit{honete}(x)$                 & $x$ dit la vérité \\
$a$                                  & Alice \\
$b$                                  & Bob \\
$c$                                  & Clinton \\
\hline
\end{tabular}
\end{center}


\og Les femmes aiment toujours les hommes fidèles et qui disent la vérité \fg peut se traduire en

$$
\forall x,y \, . \,
(\textit{homme}(x) \land
\textit{femme}(y) \land
\textit{fidele}(x) \land
\textit{honete}(x)
) \Rightarrow
\textit{aime}(y,x)
$$

L'assertion proposée est vraie ou fausse ? 

Q. 24. On considère les prédicats et constantes suivants avec leur interprétation sur un univers constitué d'individus humains.

\begin{center}
\begin{tabular}{|r|l|}
\hline
 prédicat & sens \\
\hline
$\textit{aime}(x,y)$                 & $x$ aime $y$ \\
$\textit{maries}(x,y)$                & $x$ et $y$ sont mariés  \\
$\textit{femme}(x)$                  & $x$ est une femme \\
$\textit{homme}(x)$                  & $x$ est un  homme \\
$\textit{fidele}(x)$                 & $x$ est fidèle \\
$\textit{honete}(x)$                 & $x$ dit la vérité \\
$a$                                  & Alice \\
$b$                                  & Bob \\
$c$                                  & Clinton \\
\hline
\end{tabular}
\end{center}


$$
\exists x \, . \, (\forall y \, . \,
  \textit{homme}(x) \land
 (\textit{femme}(y) \Rightarrow
  \textit{aime}(x,y))
$$

peut se traduire en \og certains hommes sont aimés de toutes les femmes \fg.


L'assertion proposée est vraie ou fausse ? 

Q. 25.  L'affirmation \og le Vesuve a ravagé la ville de Pompei en 1999 \fg{}
est-elle une proposition?
         

Q. 26. 
Soit \textit{dodec} le prédicat unaire qui est vrai si son paramètre est un dodécaèdre, 
\textit{cube} le prédicat unaire qui est vrai si son paramètre est un cube, 
\textit{petit} le prédicat unaire qui est vrai si son paramètre est petit,
\textit{entre} le prédicat ternaire qui est vrai si son premier paramètre est entre le second et le troisième
et 
\textit{devant} le prédicat unaire qui est vrai si son premier paramètre est devant son second paramètre. 

\og si un cube a quelque chose devant lui alors il est petit \fg{} peut-elle se traduire en 
$$
\forall x\, .\, 
( \exists y \, . \, cube(x) \land devant(x,y)) 
\Rightarrow  
petit(x)
$$
 L'assertion proposée est vraie ou fausse?
   

Q. 27.  Soit $p$, $q$, $r$ trois variables propostionnelles.
        L'énoncé suivant est-il une tautologie?
$(q \Leftrightarrow p) \Rightarrow
(p \Rightarrow q) \land
(q \Rightarrow p)$.
 

Q. 28. 
Soit \textit{dodec} le prédicat unaire qui est vrai si son paramètre est un dodécaèdre, 
\textit{cube} le prédicat unaire qui est vrai si son paramètre est un cube, 
\textit{petit} le prédicat unaire qui est vrai si son paramètre est petit,
\textit{entre} le prédicat ternaire qui est vrai si son premier paramètre est entre le second et le troisième
et 
\textit{devant} le prédicat unaire qui est vrai si son premier paramètre est devant son second paramètre. 
Dans la formule suivante toutes les occurences de x sont liées.
$$
\forall x \, . \, 
\textit{dodec}(x) \lor  devant(x, y) \Rightarrow 
(
(\exists y \, .\, cube(y) \land \neg devant(x, y)) 
\land  entre(u,y,x)
)
$$
 L'assertion proposée est vraie ou fausse?
   

% Q. 34. Soit $p$, $q$  les variables propositionnelles correspondant respectivement à \og il est grand \fg{} et \og il est beau \fg{}.
% De plus, \og il  est petit \fg{} signifie qu'il n'est pas grand et
% \og il est moche \fg{} signifie qu'il n'est pas beau.
%       \og il est faux qu'il est petit ou moche \fg{} peut-elle s'écrire
% $ p \land q $.
         

Q. 29.  Soit $p$, $q$, $r$ trois variables propostionnelles.
        L'ensemble $\{p \land q\}$ a-t-il pour conséquence logique $p \lor q$?
         

Q. 30. \og $B$ est une condition nécessaire pour $A$ \fg{}
peut-elle être représentée par $ \neg B \Rightarrow \neg A$ ?
         

Q. 31. \og $B$ seulement si  $A$ \fg{}
peut-elle être représentée par $ \neg A \Rightarrow B $?
         

Q. 32. 
En logique des propositions, $P$ se déduit syntaxiquement de
$H_1$, \ldots, $H_n$ si et seulement si
$P$ est une conséquence logique de $H_1$, \ldots, $H_n$.
L'assertion proposée est vraie ou fausse ? 

Q. 33. \og $B$ seulement si  $A$ \fg{}
peut-elle être représentée par $ A \lor \neg B$?
         

% Q. 40. Soit $p$ et $q$ les variables propositionnelles correspondant respectivement à \og il est grand \fg{} et \og il est beau \fg{}.
%       Sachant que \og il  est petit \fg{} signifie qu'il n'est pas grand,
% \og il est grand ou il est petit et beau \fg{} peut-elle s'écrire
% $ (p \lor \neg p) \land q $?
         

Q. 34. 
Soit la démonstration  syntaxique suivante: \newline
\begin{tabular}{lll}
\multicolumn{3}{l}{Démonstration}\\
1.&$\neg B \Rightarrow \neg A$ &$H_1$ \\
2.&$A$ &$H_2$ \\
3.&\_\_\_\_\_ &\_\_\_\_\_ \\
4.&\_\_\_\_\_ &\_\_\_\_\_ \\
5.&$\neg\neg B$ &réduction de l'absurde entre 4. et 1. \\
6.&$\neg \neg B \Rightarrow B $&Axiome 9.\\
7.& $B$ &mp entre 5. et 6.
\end{tabular}
Si elle était complète cela permetrait
démontrer syntaxiquement le théorème de la contraposée. Vrai ou faux ?
 

Q. 35.  Soit $p$, $q$, $r$ trois variables propostionnelles.
        La relation $\{ p \Rightarrow q \lor r ,  \neg q \} \models  p \lor r $ est-elle vraie?
         

Q. 36. 
On considère la base de connaissances suivante:
\begin{scriptsize}
\begin{verbatim}
parent(pam,bob).
parent(tom,bob).
parent(tom,liz).
parent(bob,ann).
parent(bob,pat).
parent(pat,jim).

ancetre(X,Z) :- parent(X,Z).
ancetre(X,Z) :- parent(X,Y),ancetre(Y,Z).
\end{verbatim}
\end{scriptsize}

On soumet la requête:
\begin{scriptsize}
\begin{verbatim}
?- ancetre(pam,X).
\end{verbatim}
\end{scriptsize}

Prolog donne 4 réponses distinctes et échoue.
 L'assertion proposée est vraie ou fausse ?
   

Q. 37. \og Il est faux que sa mère est anglaise ou que son père est français \fg{}
est-elle équivalente à
\og sa mère est anglaise ou son père n'est pas français \fg{}?
         

Q. 38.  Soit $p$, $q$, $r$ trois variables propostionnelles.
        L'énoncé suivant est-il une tautologie?
$(p \lor q) \land r \Leftarrow (p \lor r) \land (q \lor r)$.
         

Q. 39. \og $B$ seulement si $A$ \fg{}
peut-elle être représentée par $ A \Rightarrow B$ ?
         

% Q. 47. Soit $p$, $q$  les variables propositionnelles correspondant respectivement à \og il est grand \fg{} et \og il est beau \fg{}.
% De plus, \og il  est petit \fg{} signifie qu'il n'est pas grand et
% \og il est moche \fg{} signifie qu'il n'est pas beau.
%       \og il est faux qu'il est petit ou moche \fg{} peut-elle s'écrire
% $ \neg (\neg p \lor \neg q)$?
         

Q. 40. \og $A$ à moins que  $B$ \fg{} 
peut-elle être représentée par $ B \lor A $?
         

Q. 41.  La négation de \og ce triangle est rectangle donc ce triangle possède un angle droit \fg{}
est-elle  \og ce triangle ne possède pas un angle droit et pourtant il est rectangle\fg{}
         

Q. 42. 
Soit \textit{dodec} le prédicat unaire qui est vrai si son paramètre est un dodécaèdre, 
\textit{cube} le prédicat unaire qui est vrai si son paramètre est un cube, 
\textit{petit} le prédicat unaire qui est vrai si son paramètre est petit,
\textit{entre} le prédicat ternaire qui est vrai si son premier paramètre est entre le second et le troisième
et 
\textit{devant} le prédicat unaire qui est vrai si son premier paramètre est devant son second paramètre. 

Les formules
$$
\exists x\, .\,  dodec(x) \land petit(x) \textrm{ et } 
\exists x \, .\, dodec(x) \Rightarrow petit(x)
$$
n'ont jamais la même valeur de vérité.
 L'assertion proposée est vraie ou fausse?
   

Q. 43. 
Dans la formule
$P(a) \Rightarrow Q(a)$
la variable $a$ n'est pas liée.
L'assertion proposée est vraie ou fausse ? 

Q. 44.  Soit $p$, $q$, $r$ trois variables propostionnelles.
        L'ensemble $p \land q $ est-elle une  conséquence logique de $\{p,q\}$?
         

Q. 45. 
Dans les clauses
\begin{scriptsize}
\begin{verbatim}
pere_de(Y,Z) :- homme(Y),a_pour_fils(Y,Z).
pere_de(Y,Z) :- homme(Y),a_pour_fille(Y,Z).
\end{verbatim}
\end{scriptsize}

L'ensemble des deux clauses se traduit en
$$
\forall y,z \, . \, \textit{pere}(y,z) \Leftarrow
(\textit{homme}(y) \land \textit{a\_pour\_fils}(y,z))
\lor
(\textit{homme}(y) \land \textit{a\_pour\_fille}(y,z))
$$
 L'assertion proposée est vraie ou fausse ?
   

Q. 46. 
On considère la base de connaissance suivante:
\begin{scriptsize}
\begin{verbatim}
parent(pam,bob).
parent(tom,bob).
parent(tom,liz).
parent(bob,ann).
parent(bob,pat).
parent(pat,jim).
\end{verbatim}
\end{scriptsize}

Au requètes successives:

\begin{scriptsize}
\begin{verbatim}
?- parent(jim,X).
?- parent(X,jim).
?- parent(pam,X), parent(X,pat).
?- parent(pam,X), parent(X,Y), parent(Y,jim).
\end{verbatim}
\end{scriptsize}

Prolog répond au moins deux fois faux
 L'assertion proposée est vraie ou fausse ?
   

Q. 47. 
Soit $a$ et $b$ des symboles de constante,
$f$ un symbole de fonction unaire,
$g$ un symbole de fonction binaire et
$S$ un symbole de relation binaire. On donne les expressions suivantes:
\begin{enumerate}
\item \label{enum:term1a} $g(a,f(b))$
\item \label{enum:term3a} $S(f(a),g(x,f(y)))$
\end{enumerate}

L'expression \ref{enum:term3a} est un terme complexe.
 L'assertion proposée est vraie ou fausse ?
   

% Q. 56. Une formule propositionnelle $F$ a pour conséquence logique une tautologie.
%        L'affirmation suivante est-elle vraie:
% \og  $F$ est donc une antilogie \fg{}?
         

Q. 48. 
Une base de connaissance Prolog est un ensemble de faits, de règles
et de requêtes.
 L'assertion proposée est vraie ou fausse ?
 

Q. 49. On considère les prédicats et constantes suivants avec leur interprétation sur un univers constitué d'individus humains.

\begin{center}
\begin{tabular}{|r|l|}
\hline
 prédicat & sens \\
\hline
$\textit{aime}(x,y)$                 & $x$ aime $y$ \\
$\textit{maries}(x,y)$                & $x$ et $y$ sont mariés  \\
$\textit{femme}(x)$                  & $x$ est une femme \\
$\textit{homme}(x)$                  & $x$ est un  homme \\
$\textit{fidele}(x)$                 & $x$ est fidèle \\
$\textit{honete}(x)$                 & $x$ dit la vérité \\
$a$                                  & Alice \\
$b$                                  & Bob \\
$c$                                  & Clinton \\
\hline
\end{tabular}
\end{center}

$$
\forall x \, . \,
 \textit{femme}(x) \Rightarrow
 (\textit{aime}(x,b) \lor
  \textit{aime}(x,c))
$$

peut se traduire en \og Si une femme n'aime pas Clinton, alors elle aime Bob \fg.


L'assertion proposée est vraie ou fausse ? 

% Q. 59. Une formule propositionnelle $F$ est conséquence logique d'une tautologie.
%        L'affirmation suivante est-elle vraie:
% \og  $F$ est donc une tautologie \fg{}?
         

Q. 50. 
Soit $a$ et $b$ des symboles de constante,
$f$ un symbole de fonction unaire,
$g$ un symbole de fonction binaire et
$S$ un symbole de relation binaire. On donne les expressions suivantes:
\begin{enumerate}
\item \label{enum:term1b} $g(a,f(b))$
\item \label{enum:term3b} $S(f(a),g(x,f(y)))$
\end{enumerate}

L'expression \ref{enum:term1} contient quatre termes
 L'assertion proposée est vraie ou fausse ?
   

Q. 51. 
Soit
$f$, $g$ des symboles de fonctions binaire,
$R$ un symbole de relation binaire.
Soit $A$ la formule
$$
\left(\forall z \, .\, R(x,z) \land R(z,y) \right)
\Rightarrow
\left(\exists z \, .\, R(z,y) \lor R(x,z) \right).
$$
Soit $u$, $v$ les termes définis par
$u= f(z,x)$ et
$v= g(x,z)$

Alors on a
$$
A(u/x)(v/y) \equiv
A(v/y)(u(v/y)/x)
$$
 L'assertion proposée est vraie ou fausse ?
   

Q. 52. Si je travaille, je ne peux pas étudier;
Soit je travaille, soit je suis reçu en mathématiques;
j'ai été reçu en mathématiques.
Donc j'ai étudié.
 Le raisonnement proposé est-il incorrect?
         

Q. 53. 
Soit \textit{dodec} le prédicat unaire qui est vrai si son paramètre est un dodécaèdre, 
\textit{cube} le prédicat unaire qui est vrai si son paramètre est un cube, 
\textit{petit} le prédicat unaire qui est vrai si son paramètre est petit,
\textit{entre} le prédicat ternaire qui est vrai si son premier paramètre est entre le second et le troisième
et 
\textit{devant} le prédicat unaire qui est vrai si son premier paramètre est devant son second paramètre. 
Dans la formule suivante $y$ et $u$ ont des occurences libres
$$
\forall x \, . \, 
\textit{dodec}(x) \lor  devant(x, y) \Rightarrow 
(
(\exists y \, .\, cube(y) \land \neg devant(x, y)) 
\land  entre(u,y,x)
)
$$
 L'assertion proposée est vraie ou fausse?
   

% Q. 64. Une formule propositionnelle $F$ a pour conséquence logique une antilogie.
%       On ne peut donc rien dire de $F$.
         

Q. 54. \og $A$ à moins que  $B$ \fg{} 
peut-elle être représentée par $ B \Rightarrow A $?
         

Q. 55.  L'affirmation \og le Vesuve ferra une irruption en 2010\fg{}
est-elle une proposition?
         

Q. 56. 
\og Il est faux qu'il ne fait pas froid ou qu'il pleut \fg{}
est-elle équivalente à   \og il fait froid mais il ne pleut pas \fg{}?
         

% Q. 68. Soit $p$ et $q$ les variables propositionnelles correspondant respectivement à \og il est grand \fg{} et \og il est beau \fg{}.
%       Sachant que \og il  est petit \fg{} signifie qu'il n'est pas grand,
% \og il est grand ou il est petit et beau \fg{} peut-elle s'écrire
% $ p \lor q $?
         

% Q. 69. Une formule propositionnelle $F$ est conséquence logique d'une tautologie.
%        L'affirmation suivante est-elle vraie:
% \og  On ne peut donc rien dire de $F$ \fg{}?
         

% Q. 70. 
% Les termes $p(f(X),X)$ et $p(Y,Y)$ sont  unifiables.
%  L'assertion proposée est vraie ou fausse ?
   

% Q. 71. 
% Soit \textit{dodec} le prédicat unaire qui est vrai si son paramètre est un dodécaèdre, 
% \textit{cube} le prédicat unaire qui est vrai si son paramètre est un cube, 
% \textit{petit} le prédicat unaire qui est vrai si son paramètre est petit,
% \textit{entre} le prédicat ternaire qui est vrai si son premier paramètre est entre le second et le troisième
% et 
% \textit{devant} le prédicat unaire qui est vrai si son premier paramètre est devant son second paramètre. 

% \og les seuls grands cubes sont b et c \fg{} peut-elle se traduire en 
% $$
% \forall x \, .\, 
% (\neg petit(x) \land cube(x)) 
% \leftrightarrow 
%  ( x = b \lor  x = c)
% $$
%  L'assertion proposée est vraie ou fausse?
   

% Q. 72. 
% On considère la base de connaissances suivante:
% \begin{scriptsize}
% \begin{verbatim}
% parent(pam,bob).
% parent(tom,bob).
% parent(tom,liz).
% parent(bob,ann).
% parent(bob,pat).
% parent(pat,jim).

% ancetre(X,Z) :- parent(X,Z).
% ancetre(X,Z) :- parent(X,Y),ancetre(Y,Z).
% \end{verbatim}
% \end{scriptsize}

% On soumet la requête:
% \begin{scriptsize}
% \begin{verbatim}
% ?- ancetre(pam,X).
% \end{verbatim}
% \end{scriptsize}

% Prolog donne 1 réponse et échoue.
%  L'assertion proposée est vraie ou fausse ?
   

% Q. 73. 
% On considère la base de connaissance suivante:
% \begin{scriptsize}
% \begin{verbatim}
% a_une_baguette(harry).
% joueur_de_Quidditch(harry).
% sorcier(ron).
% sorcier(X) :- a_un_balai(X), a_une_baguette(X).
% a_un_balai(X) :- joueur_de_Quidditch(X).
% \end{verbatim}
% \end{scriptsize}

% Lorsqu'on soumet successivement les requêtes suivantes:

% \begin{scriptsize}
% \begin{verbatim}
% ?- sorcier(ron).
% ?- sorciere(ron).
% ?- sorcier(hermione).
% ?- sorciere(hermione).
% ?- sorcier(harry).
% \end{verbatim}
% \end{scriptsize}

% Prolog répond trois fois faux.
%  L'assertion proposée est vraie ou fausse ?
   

% Q. 74. \og $A$ à moins que  $B$ \fg{} 
% peut-elle être représentée par $ B \Rightarrow A $?
         

% Q. 75. 
% Soit \textit{dodec} le prédicat unaire qui est vrai si son paramètre est un dodécaèdre, 
% \textit{cube} le prédicat unaire qui est vrai si son paramètre est un cube, 
% \textit{petit} le prédicat unaire qui est vrai si son paramètre est petit,
% \textit{entre} le prédicat ternaire qui est vrai si son premier paramètre est entre le second et le troisième
% et 
% \textit{devant} le prédicat unaire qui est vrai si son premier paramètre est devant son second paramètre. 

% \og Il y a au moins deux objets qui n’ont rien derrière eux \fg{} peut-elle se traduire en 
% $$
% \exists x,y\, .\,  
% x \neq y \land
%  (\forall w\, .\, (w = x \lor  w = y) \rightarrow (\forall z  ¬devant(z, w)))
% $$
%  L'assertion proposée est vraie ou fausse?
   

% Q. 76. Une formule propositionnelle $F$ a pour conséquence logique une antilogie.
%       L'affirmation suivante est-elle vraie:
% \og $F$ est donc une tautologie \fg{}?
         

% Q. 77. \og $B$ est une condition nécessaire pour $A$ \fg{}
% peut-elle être représentée par $ B \Rightarrow A$ ?
         

% Q. 78.  Soit $p$, $q$, $r$ trois variables propostionnelles.
%       La relation $\{\neg p \Rightarrow q \lor r , \neg r, \neg q \} \models \neg p $ est-elle vraie?
         

% Q. 79. 
% Soit la démonstration  syntaxique suivante: \newline
% \begin{tabular}{lll}
% \multicolumn{3}{l}{Démonstration}\\
% 1.&$\neg B \Rightarrow \neg A$ &$H_1$ \\
% 2.&$A$ &$H_2$ \\
% 3.&\_\_\_\_\_ &\_\_\_\_\_ \\
% 4.&\_\_\_\_\_ &\_\_\_\_\_ \\
% 5.&$\neg\neg B$ &réduction de l'absurde entre 4. et 1. \\
% 6.&$\neg \neg B \Rightarrow B$ &Axiome 9.\\
% 7.& $B$ &mp entre 5. et 6.
% \end{tabular}
% Si elle était complète cela permetrait de
% démontrer syntaxiquement
% $(\neg B \Rightarrow \neg A) \Rightarrow (A \Rightarrow B)
% $.
%  L'assertion proposée est vraie ou fausse ?
 

% Q. 80. Une formule propositionnelle $F$ est conséquence logique d'une antilogie.
%        L'affirmation suivante est-elle vraie:
% \og  On ne peut donc rien dire de $F$ \fg{}?
         

\section{Raisonnements écrits (1h15)}

\subsection{Calcul des prédicats}
Dans la série suivante, chaque formule est logiquement équivalente à une et 
une seule autre. Retrouver les paires équivalentes et justifier.
\begin{eqnarray}
& \forall x\, . \, \neg p(x) \land q(x) &  \\
& \neg (\forall x\, . \, p(x) \Rightarrow q(x) ) &  \\
& \exists x\, . \, \neg p(x) \lor \neg  q(x)  &  \\
& \exists x\, . \, \neg p(x) \lor  q(x)  &  \\
& (\exists x\, . \, \neg p(x)) \lor (\exists x\, . \,  q(x))  &  \\
& (\exists x\, . \, \neg p(x)) \lor \neg (\exists x\, . \,\neg  q(x))  &  \\
& \neg (\exists x\, . \, p(x)) \land (\forall x\, . \,  q(x))  &  \\
& \exists x\, . \, p(x) \Rightarrow \neg q(x)  &  \\
& \neg (\forall x\, . \, p(x)) \lor (\forall x\, . \,  q(x))  &  \\
& \exists x\, . \, p(x) \land \neg  q(x)  &  
\end{eqnarray}


% initiation à la logique formelle, lucas, berlanger...

\subsection{Prolog}
\subsubsection{Graphe}
\begin{figure}
\begin{center}
\includegraphics[width=3cm]{graph.eps}
\end{center}
\caption{Graphe à modéliser en Prolog }
\label{Fig:graph}
\end{figure}

On considère le graphe donné à la figure~\ref{Fig:graph}.
\begin{enumerate}
\item Modéliser ce graphe à l'aide du prédicat $\textit{arc}(X,Y)$ qui est 
  vrai s'il existe un arc depuis le noeud $X$ vers le noeud $Y$.
\item Construire le prédicat $\textit{chemin}(X,Y)$ qui est vrai 
s'il existe un chemin, c'est à dire une suite continue et éventuellement vide 
d'arcs entre les noeuds $X$ et $Y$ du graphe.
\item Quelle requête Prolog effectueriez-vous pour obtenir tous les noeuds 
  accessibles à partir du noeud a.
\end{enumerate}

\subsubsection{Liste d'entiers naturels}
\begin{enumerate}
\item Définir un prédicat $\textit{pair}(X)$ qui est vrai si $X$ est un 
  nombre pair.

\item Définir un prédicat $\textit{membres\_pairs}(L,Lp)$ qui est vrai 
  si la liste $Lp$ est composée des éléments pairs de la liste 
  $L$ et dans le même ordre.

\item On considère le prédicat Prolog $\textit{append}(L1,L2,L3)$ qui est
est vrai si $L3$ est la concaténation des listes $L1$ et $L2$. 
Définir le prédicat $\textit{inverse}(L,Lp)$ qui est vrai si $Lp$ est la liste 
$L$ retournée.
\end{enumerate}  

\subsection{Déduction syntaxique}
Dans ce qui suit, $A$, $B$, $C$ et $D$ sont quatre variables propositionnelles.

\begin{enumerate}
\item Démontrer le théorème suivant par déduction syntaxique:
$$
(
A \Rightarrow ( B \land C)
)
\Rightarrow
(A \Rightarrow B) \land 
(A \Rightarrow C)
$$
On pourra utiliser le théorème de transitivité de l'implication.

\item Effectuer la démonstration sous hypothèse suivante:
$$
\{
C \Rightarrow \neg B ,
C \lor D,
D \Rightarrow \neg B,
A \Rightarrow B
\}
\vdash \neg A
$$
On pourra utiliser le théorème de la contraposée et la règle de disjonction 
des cas.

\end{enumerate}
\newpage
\section*{Réponses au QCM}
\noindent Nom:............................\\
\noindent Prénom:............................\\


\begin{Huge}

\begin{center}
\begin{tabular}{|l|c|c||l|c|c||l|c|c|}
\hline
Numéro & V & F & Numéro & V & F & Numéro & V & F \\ 
\hline
Q. 1 & &  & Q. 2 & &  & Q. 3 & &  \\ 
\hline
Q. 4 & &  & Q. 5 & &  & Q. 6 & &  \\ 
\hline
Q. 7 & &  & Q. 8 & &  & Q. 9 & &  \\ 
\hline
Q. 10 & &  & Q. 11 & &  & Q. 12 & &  \\ 
\hline
Q. 13 & &  & Q. 14 & &  & Q. 15 & &  \\ 
\hline
Q. 16 & &  & Q. 17 & &  & Q. 18 & &  \\ 
\hline
Q. 19 & &  & Q. 20 & &  & Q. 21 & &  \\ 
\hline
Q. 22 & &  & Q. 23 & &  & Q. 24 & &  \\ 
\hline
Q. 25 & &  & Q. 26 & &  & Q. 27 & &  \\ 
\hline
Q. 28 & &  & Q. 29 & &  & Q. 30 & &  \\ 
\hline
Q. 31 & &  & Q. 32 & &  & Q. 33 & &  \\ 
\hline
Q. 34 & &  & Q. 35 & &  & Q. 36 & &  \\ 
\hline
Q. 37 & &  & Q. 38 & &  & Q. 39 & &  \\ 
\hline
Q. 40 & &  & Q. 41 & &  & Q. 42 & &  \\ 
\hline
Q. 43 & &  & Q. 44 & &  & Q. 45 & &  \\ 
\hline
Q. 46 & &  & Q. 47 & &  & Q. 48 & &  \\ 
\hline
Q. 49 & &  & Q. 50 & &  & Q. 51 & &  \\ 
\hline
Q. 52 & &  & Q. 53 & &  & Q. 54 & &  \\ 
\hline
Q. 55 & &  & Q. 56 & &  & & &  \\ 
\hline
 
\end{tabular} 
\end{center} 




\end{Huge}

\end{document}