partiels/090525/partiel.tex

   1
   2 \subsection{Calcul des prédicats}
   3 Dans la série suivante, chaque formule est logiquement équivalente à une et
   4 une seule autre. Retrouver les paires équivalentes et justifier.
   5 \begin{eqnarray}
   6 & \forall x\, . \, \neg p(x) \land q(x) &  \\
   7 & \neg (\forall x\, . \, p(x) \Rightarrow q(x) ) &  \\
   8 & \exists x\, . \, \neg p(x) \lor \neg  q(x)  &  \\
   9 & \exists x\, . \, \neg p(x) \lor  q(x)  &  \\
  10 & (\exists x\, . \, \neg p(x)) \lor (\exists x\, . \,  q(x))  &  \\
  11 & (\exists x\, . \, \neg p(x)) \lor \neg (\exists x\, . \,\neg  q(x))  &  \\
  12 & \neg (\exists x\, . \, p(x)) \land (\forall x\, . \,  q(x))  &  \\
  13 & \exists x\, . \, p(x) \Rightarrow \neg q(x)  &  \\
  14 & \neg (\forall x\, . \, p(x)) \lor (\forall x\, . \,  q(x))  &  \\
  15 & \exists x\, . \, p(x) \land \neg  q(x)  &
  16 \end{eqnarray}
  17
  18
  19 % initiation à la logique formelle, lucas, berlanger...
  20
  21 \subsection{Prolog}
  22 \subsubsection{Graphe}
  23 \begin{figure}
  24 \includegraphics{graph.eps}
  25 \caption{Graphe à modéliser en Prolog \label{Fog:graph}}
  26 \end{figure}
  27
  28 On considère le graphe donné à la figure~\ref{Fig:graph}.
  29 \begin{enumerate}
  30 \item Modéliser ce graphe à l'aide du prédicat $\textit{arc}(X,Y)$ qui est
  31   vrai s'il existe un arc depuis le noeud $X$ vers le noeud $Y$.
  32 \item Construire le prédicat $\textit{chemin}(X,Y)$ qui est vrai
  33 s'il existe un chemin, c'est à dire une suite continue et éventuellement vide
  34 d'arcs entre les noeuds $X$ et $Y$ du graphe.
  35 \item Quelle requête Prolog effectueriez-vous pour obtenir tous les noeuds
  36   accessibles à partir du noeud a.
  37 \end{enumerate}
  38
  39 \subsubsection{Liste d'entiers naturels}
  40 \begin{enumerate}
  41 \item Définir un prédicat $\textit{pair}(X)$ qui est vrai si $X$ est un
  42   nombre pair.
  43
  44 \item Définir un prédicat $\textit{membres\_impairs}(L,Lp)$ qui est vrai
  45   si $Lp$ est composé des éléments pairs de $L$ et dans le même ordre.
  46
  47 \item On considère le prédicat Prolog $\textit{append}(L1,L2,L3)$ qui est
  48 est vrai si $L3$ est la concaténation des listes $L1$ et $L2$.
  49 Définir le prédicat $\textit{inverse}(L,Lp)$ qui est vrai sir $Lp$ est la liste
  50 $L$ retournée.
  51 \end{enumerate}
  52
  53 \subsection{Déduction syntaxique}
  54
  55 \begin{enumerate}
  56 \item Démontrer le théorème suivant par déduction syntaxique.
  57 $$
  58 (
  59 p_1 \Rightarrow ( p_2 \land p_3)
  60 )
  61 \Rightarrow
  62 (p_1 \Rightarrow p_2) \land
  63 (p_1 \Rightarrow p_3)
  64 $$
  65 On pourra utiliser le théorème de transitivité de l'implication.
  66
  67 \item Effectuer la démonstration sous hypothèse suivante:
  68 $$
  69 \{
  70 C \Rightarrow \neg B ,
  71 C \lor D,
  72 D \Rightarrow \neg B,
  73 A \Rightarrow B
  74 \}
  75 \models \neg A
  76 $$
  77 On pourra utiliser le théorème de la contraposée et la règle de disjonction
  78 des cas.
  79
  80