
\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}
\includegraphics{graph.eps}
\caption{Graphe à modéliser en Prolog \label{Fog: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\_impairs}(L,Lp)$ qui est vrai 
  si $Lp$ est composé des éléments pairs de $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 sir $Lp$ est la liste 
$L$ retournée.
\end{enumerate}  

\subsection{Déduction syntaxique}

\begin{enumerate}
\item Démontrer le théorème suivant par déduction syntaxique.
$$
(
p_1 \Rightarrow ( p_2 \land p_3)
)
\Rightarrow
(p_1 \Rightarrow p_2) \land 
(p_1 \Rightarrow p_3)
$$
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
\}
\models \neg A
$$
On pourra utiliser le théorème de la contraposée et la règle de disjonction 
des cas.

 
