\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]{graphics}
\usepackage{epsfig}
\usepackage{calc}
\usepackage{tabls}
\usepackage{slashbox}
\usepackage{times}
\usepackage{tabularx}
\usepackage{textcomp}
\title{
Partiel de mathématiques discrètes, semestre 2, decembre 2008.\\
Durée : 3 heures.} 
\date{}
\geometry{hmargin=1.5cm, vmargin= 1.5cm}
\author{\sc{Couchot}, J.-F}
\begin{document}
\maketitle



Les supports  de TDs et de TP sont autorisés; la calculatrice est interdite.
Cette épreuve contient trois parties distinctes: 
un qcm, quelques démonstrations syntaxiques, et quelques programmes Prolog. 


\section{QCM (1h45)}

Q. 1. 
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).

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. 2. Une formule propositionnelle $F$ a pour conséquence logique une tautologie. 
L'affirmation suivante est-elle vraie: 
\og  $F$ est donc une tautologie \fg{}?
         

Q. 3. Si j'étudie, je n'échoue pas en maths,
si je ne joue pas au basket-ball, alors j'étudie,
mais j'ai échoué en mathématiques. 
Donc, j'ai joué au basket-ball.
 Le raisonnement proposé est-il incorrect?
         

Q. 4. 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édicats & 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. 5.  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. 6. 
Soit $x$ et $y$ des entiers naturels.
$\forall x \, .\, (\exists y \, .\, x +y \ge x +1 )$
est vraie.
L'assertion est-elle vraie?



Q. 7. 
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. 8. 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. 9.  Soit $p$, $q$, $r$ trois variables propostionnelles.
	La relation $\{p \Rightarrow \neg q , q \} \models \neg p$ est-elle vraie ?
         

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

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

Q. 12. 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 p)$?
	 

Q. 13. La formule 
$\forall x \,.\, x > 0 \Rightarrow 
  (\exists y \, . \, e^y = x)
$
est vraie sur l'univers $\mathds{N}$.
L'assertion  est-elle vraie?

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

Q. 15. 
Les termes $p(X,f(a,Y),X)$ et $p(f(U,U),Z,Z)$ sont-ils unifiables ?

   

Q. 16. 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. 17. 
Dans la formule 
$P(a) \Rightarrow Q(a)$
la variable $a$ n'est pas liée.
L'assertion est-elle vraie?

Q. 18. La formule 
$\forall x \,.\, x > 0 \Rightarrow 
  (\exists y \, . \, e^y = x )
$
est-elle vraie sur l'univers $\mathds{R}$?


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

Q. 20. 
\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. 21. 
Soit la démonstration  syntaxique suivante:

\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}

\noindent Si elle était correcte et complète, cette démonstration permetrait-elle  
de démontrer le théorème de la contraposée ?


Q. 22. 
Soit la démonstration  syntaxique suivante:

\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-elle correcte et complète si en 3. et 4. on a: 
\begin{tabular}{lll}
3.&$\neg \neg A \Rightarrow  \neg \neg B $ &théoreme de la contraposé sur 1. \\
4.&$\neg \neg A \Rightarrow A $ &Axiome 9 ? 
\end{tabular} 


Q. 23. 
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. 24. La relation $\{P,Q\} \vdash R$  se lit-elle 
\og $R$ est une conséquence logique de l'ensemble
                     $\{P,Q\}$ \fg{}?
                      

Q. 25. 
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}

\noindent La première clause se traduit-elle en 
$
\forall y,z \, . \, \textit{pere}(y,z) \Leftrightarrow \textit{homme}(y) 
\land \textit{a\_pour\_fils}(y,z)
$
?
   



Q. 26. 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. 27.  Soit $p$, $q$, $r$ trois variables propostionnelles.
	L'énoncé suivant est-il une tautologie?
$(p \lor q) \land r \Rightarrow (p \lor r) \land (q \lor r)$. 
	 

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

Q. 29. 
En logique des propositions, 
il est possible de déduire que $P$ est vraie chaque fois que  
$H_1$, \ldots, $H_n$ le sont par la méthode des tables de vérités sans 
qu'il n'existe nécessairement de démonstration syntaxique permettant 
d'établir $P$ à partir des hypothèses $H_1$, \ldots, $H_n$. 
L'assertion est-elle vraie?

Q. 30. 
Dans la formule 
$(\forall x \, . \, x \ge 5) \land (\exists y \, ; \, y \ge x)$
la variable $x$ est-elle  liée?


Q. 31. 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. 32.  Soit $p$ et $q$, deux variables propostionnelles.
	L'énoncé $ 
(p \land ( p \lor q)) \Leftrightarrow p$ 
 est-il une tautologie?
	 

Q. 33. 
On considère les prédicats 
\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. 
L'assertion 
\og \verb+X+ est la fille de \verb+Y+ \fg{} se traduit-elle en prolog par
%\begin{scriptsize}
\verb+fille(X,Y) :- parent(X,Y), femme(X).+?


%\end{scriptsize}

   

Q. 34. 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}

\noindent Le prédicat 
$
\exists x,y  \, . \, (
       \textit{maries}(x,y) \land 
  \neg \textit{aime}(x,y) \land
  \neg \textit{aime}(y,x))
$
traduit-il que  
\og dans certains couples, un conjoint n'aime pas l'autre \fg.


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

Q. 36. 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. 37. 
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 est-elle vraie?

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

Q. 39. 
Soit la démonstration  syntaxique suivante:

\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-elle correcte et complète si en 3. et 4. on a 

\begin{tabular}{lll}
3.&$A \Rightarrow (\neg B \Rightarrow A)$ &Axiome 1. \\
4.&$\neg B \Rightarrow A $ &modus ponens entre 2. et 3. 
\end{tabular}
?


 

Q. 40.  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)$. 
	 






\section{Programmation Prolog (0h30)}

\subsection{Voyages}
\begin{scriptsize}
\begin{verbatim}
voiture(auckland,hamilton).
voiture(hamilton,raglan).
voiture(valmont,saarbruecken).
voiture(valmont,metz).
train(metz,frankfurt).
train(saarbruecken,frankfurt).
train(metz,paris).
train(saarbruecken,paris).
avion(frankfurt,bangkok).
avion(frankfurt,singapore).
avion(paris,losAngeles).
avion(bangkok,auckland).
avion(losAngeles,auckland).
\end{verbatim}
\end{scriptsize}  

Ecrire un prédicat \verb+voyage(X,Y)+ 
qui détermine s'il est possible de voyager d'un endroit à 
l'autre en empruntant des voitures, des trains ou des avions.
Par exemple votre programme doit répondre yes à la requête 
\verb+voyage(valmont, raglan)+.

\subsection{Codage des entiers naturels}
Les entiers naturels peuvent être codés à l'aide de 0,  
du successeur de 0 (qui vaut 1), puis du sucesseur du successeur de 0 
(qui vaut 2) et ainsi de suite\ldots
Le predicat $\textit{entier}$ est alors défini à l'aide de la constante 0
et du symbol fonctionnel $\textit{succ}$ selon les clauses suivantes:

\begin{scriptsize}
\begin{verbatim}
entier(0).
entier(X):- X=succ(Y), entier(Y).
\end{verbatim}
\end{scriptsize}  

\begin{enumerate}
\item Définir le predicat \verb+somme(X,Y,Z)+ qui est vrai si l'entier 
\verb+Z+ est la somme de \verb+X+ et de \verb+Y+, ces trois entiers étant 
codés dans cette logique.
\item Définir le predicat \verb+plus_grand_que(X,Y)+ qui est vrai si l'entier 
\verb+X+ est plus grand que l'entier \verb+Y+, ces deux entiers étant 
codés dans cette logique.
\end{enumerate}




\section{Démonstration syntaxique (45min)}

Dans le système \og PR \fg{} et en se servant éventuellement des théorèmes 
déjà démontrés dans le cours, démontrer syntaxiquement 
les deux formules propositionnelles suivantes:
\begin{enumerate}
\item $(A \Rightarrow (B \Rightarrow C)) \Rightarrow 
  ((A \Rightarrow B) \Rightarrow (A \Rightarrow C))$
\item $(A \lor  (B \land C)) \Rightarrow ((A \lor B) \land (A \lor C))$
\end{enumerate}


\newpage
\noindent Nom:\newline
\noindent Prénom:

\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 & &  &       & &  &  & &  \\ 
\hline
\end{tabular} 
\end{center} 

\end{document}