\documentclass[11pt]{article}
\usepackage{alltt}
\usepackage{verbatim}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{pifont}
\usepackage[dvips]{graphics}
\usepackage[dvips]{graphicx}
\usepackage[latin1]{inputenc} %% entr\'ee 8 bits iso-latin1
\usepackage[T1]{fontenc}      %% encodage 8 bits des fontes utilis\'ees
\usepackage{verbatim}

\parindent=0cm
\oddsidemargin 0.2cm
\evensidemargin 0.2 cm


\textheight 25cm
\textwidth 17.0cm

\begin{document}

\vspace{-2cm}
{ \bf ESSI 2\`eme Ann\'ee} \hfill {\bf Ann\'ee 2002-2003}\\
\centerline{\Large \bf Examen de logique et Prolog}\vspace{1.0cm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{\Large \bf A) LOGIQUE}

\section{Formalisation (3 points)}

Soit le langage du premier ordre form\'e de l'ensemble de variables {\em V = \{x,y\}}, des symboles fonctionnels 0-aire {\em H} et {\em L}, des symboles de pr\'edicat 1-aire {\em homme},{\em vtt}, {\em yeuxVerts} et des symboles de pr\'edicats 2-aire 
{\em \'egal} et {\em estMari\'eAvec}.

Dans ce langage, exprimer les \'enonc\'es suivants:
\begin{enumerate}
\item Les hommes qui font du VTT ont les yeux verts.
\item Les hommes aux yeux verts sont mari\'es.
\item H\'el\`ene ne peut \'epouser qu'un homme qui fait du VTT.
\item Il existe un unique homme aux yeux verts qui est mari\'e avec H\'el\`ene.
\end{enumerate}

\section{Validit\'e (2 points)}
\begin{enumerate}
\item Soit la formule $\Phi =  \exists~ x~ \forall~ y~ p(x,y,y)$. Donner une interpr\'etation $I1$ qui est un mod\`ele de $\Phi$ et une interpr\'etation $I2$ qui n'est pas un mod\`ele de $\Phi$.
\item Montrer par 0-r\'esolution que $A \Rightarrow (B \Rightarrow A)$ est universellement valide.
\end{enumerate}

\section{Preuve dans tous les mod\`eles (5 points)}
Soit les axiomes :
\begin{itemize}
\item A1 : \(  \forall x_1 \:\forall y_1 \: \forall z_1 \:  
          \forall x_2 \:\forall y_2 \: \forall z_2 \:  
           (p(x_1,y_1,x_2) \:\wedge\: p(y_1,z_1,y_2)) \Rightarrow
           (p(x_1,y_2,z_2) \Leftrightarrow  p(x_2,z_1,z_2)) \) 

\item A2:  \( \exists x \:[\forall y \:\: p(x,y,y) \:\:\wedge \:\: 
        \forall z \:\exists u \:\: p(u,z,x)]\)
\end{itemize}
Montrer que :
\begin{center}  
\( \Phi=\exists x[\forall y \:  p(x,y,y) \: \wedge \: 
\forall z\: \exists u \: p(z,u,x)] \)
\end{center}
 est valide dans tous les mod\`eles de \{A1, A2\}.
Prenez soin de d\'etailler les \'etapes de mise sous forme de clauses ainsi que de noter les substitutions lors de la r\'esolution.\\


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{\Large \bf B) PROLOG}



\section{La classique ``famille'' (3 points)}
Soit le programme :
{\small 
\begin{verbatim}
descendant(Descendant,Ascendant) :- 
  parent(Ascendant,Descendant).
descendant(Descendant,Ascendant) :- 
  descendant(Descendant,Enfant),
  parent(Ascendant,Enfant).
\end{verbatim}}
\pagebreak
\begin{verbatim}
parent(mathilde,francois).  parent(pierre,francois).    parent(pierre,jean).
parent(mathilde,rose).      parent(jean,bastien).       parent(jean,rudolph).
parent(rose,bastien).       parent(rose,rudolph).       parent(rudolph,gwendoline.

\end{verbatim}}
\begin{enumerate}
\item  Donner l'ensemble de solutions de la requ\^ete 
       {\tt descendant(D,A)}
\item  Dessiner l'arbre de recherche  pour la requ\^ete 
       {\tt descendant(D,A)}
\end{enumerate}

\section{La classique ``send+more'' (2 points)}
Donner la taille de l'espace de recherche pour la  requ\^ete 
t {\tt mm2([S,E,N,D,M,O,R,Y])}
{\small 
\begin{verbatim}
mm2([S,E,N,D,M,O,R,Y]) :-
     generate([S,E,N,D,M,O,R,Y],[0,1,2,3,4,5,6,7,8,9]),     
     S>0, M >0, 
     test_sum(S,E,N,D,M,O,R,Y).         

generate([],_).
generate([X|Xs],Vs):-                     
     select(X,Vs,Vr), generate(Xs,Vr).
select(J,[J|L],L).
select(J,[K|L],[K|M]):- select(J,L,M).
test_sum(S, E, N, D, M, O, R, Y) :-
     V1 is             1000*S + 100*E + 10*N + D 
          +            1000*M + 100*O + 10*R + E,
     V2 is 10000*M + 1000*O + 100*N + 10*E + Y,  V1 = V2.
    
\end{verbatim}}

\section{Un programme de coloriage (3 points)}
Ecrire un   prédicat {\tt color(Lr,Lc)} qui permet de colorier une carte planaire avec 4 couleurs 
tel que les couleurs de deux régions adjacentes soient différentes. {\tt Lr} est la liste des 
régions à colorier et {\tt Lc} la liste des couleurs associées.  Les relations d'adjacence sont 
définies à l'aide du prédicat {\tt adj(Région1,Région2)}.\\
Exemple:\\
{\small   
Soient
{\small \begin{verbatim}
adj(france,allemagne).    adj(france,italie).  adj(france,suisse).    adj(allemagne,suisse). 
adj(allemagne,autriche).  adj(suisse,italie).  adj(suisse,autriche).  adj(autriche,italie).
\end{verbatim}}
alors
{\small \begin{verbatim}
?- color([france,allemagne,autriche,suisse,italie],Lc).
Lc=[rouge,vert,rouge,jaune,vert] ; Lc=[rouge,vert,rouge,jaune,bleu] ; ... 
\end{verbatim}}

\section{Un petit parser (3 points)}
Ecrire la DCG qui permet de parser des expressions booléennes. 
Une expression booléenne est constituée de variables 
(notées $x_1$ à $x_{99}$) et de connectives 
(notées {\tt and, or, not}) avec les arités usuelles. Il n'y pas de parenthèses et vous pouvez définir les règles de priorités que vous souhaitez.

\end{document}
