modif algo euclide

[cours-maths-dis.git] / logique / CalculPredicats2.tex

\section{Introduction}



% %\subsection{Insuffisances de la formalisation en calcul
% %  propositionnel} 

% La logique des propositions ne s'occupe que des liens
% entre propositions réalisés à l'aide des connecteurs logiques:
% %Autrement dit, 
% une fois qu'une proposition \og complexe\fg{} a été
% analysée suivant ces connecteurs, il subsiste des \og atomes\fg{} (non
% sécables en calcul propositionnel) et l'analyse ne peut pas être
% poussée plus profondément, alors qu'il existe potentiellement encore des
% \og relations\fg{} entre ces atomes.



 \subsection{Introduction aux \og prédicats\fg{}} 

En logique des propositions,
\og Pierre est le père de Marc\fg{} ne comporte aucun
connecteur logique: elle ne peut se formaliser que par une variable 
propositionnelle: $A$.
La proposition \og Jean est le père de Sylvie\fg{}
qui entretient des rapports évidents avec la précédente, elle ne peut être
formalisée en logique des propositions que par une
variable propositionnelle, $B$. 
Après la formalisation, donc, on se retrouve avec deux variables
propositionnelles $A$ et $B$, sans lien aucun entre elles, alors qu'il
est évident que ces deux propositions évoquent un même lien de parenté
entre des individus différents. 



Il apparaît primordial 
%Ce premier exemple suggère la nécessité, pour poursuivre l'analyse des
% propositions, de la création d'
de créer 
un langage qui permettrait de décrire
des propriétés accordées %(ou non) 
à des individus: c'est ce à quoi s'intéresse la 
\emph{logique des prédicats}. 
%Cette préoccupation est aussi celle des mathématiciens, qui
%s'occupent, par exemple, de décrire les propriétés des entiers
%naturels. 


% Il faudra donc envisager des \og variables\fg{} , dans un certain
% domaine, et, pour certaines \og valeurs\fg{} de ces variables,
% certaines propriétés seront \og vraies\fg{} ou \og fausses\fg{}. 

 \subsection{Introduction à l'\og univers du discours\fg{}}

% Soit la proposition \og 7 n'a pas de racine carrée\fg{}.
% En calcul propositionnel, elle ne peut être formalisée que par une
% variable propositionnelle. 
% De plus, il semble même difficile de lui accorder une \og valeur de
% vérité\fg{} ; en effet, si l'on se place dans l'ensemble des entiers
% naturels, cette proposition est \og vraie\fg{}, alors que si l'on se 
% place dans l'ensemble des nombres réels, elle est évidemment fausse. 

La valeur de l'expression \og $x$ possède une racine carrée \fg{}
dépend de $x$ et de l'\emph{univers} dans lequel on fait évoluer 
$x$.
Cette expression est 
\begin{itemize}
\item toujours vraie si l'univers du discours est l'ensemble des réels
  positifs;
\item toujours fausse si l'univers du discours est l'ensemble des réels
  strictement négatifs;
\item vraie pour certaines valeurs si l'univers du discours est l'ensemble des 
  entiers naturels.
\end{itemize}



% Dans cet exemple, comme dans celui de la section précédente, la
% proposition évoque 
% une propriété, accordée ou refusée, à un objet bien précis (7).
% Bien entendu, la valeur de vérité dépend de la valeur de cet objet,
% mais aussi de l'ensemble dans lequel ces valeurs peuvent être
% choisies. 


% On pourra envisager de formaliser (partiellement) une telle
% proposition par une expression du type \og $x$ a une racine
% carrée\fg{}, et la valeur de vérité de la proposition obtenue en \og
% donnant à $x$ une valeur\fg{} dépend, non seulement de cette valeur,
% mais aussi de l'ensemble dans lequel cette valeur peut être prise. 


% D'une manière générale, et avant de donner une définition précise de
% ces 
% concepts, on dira qu'une \og propriété\fg{} possédée (ou non) par un objet est un prédicat.
% La valeur de vérité de la proposition obtenue en appliquant ce
% prédicat à un (ou plusieurs) objets dépend de l'univers du discours,
% c'est à dire de l'ensemble des valeurs reconnues comme possibles (par
% exemple, dans l'exemple précédent, $\N$ ou $\R$), et aussi, bien
% entendu, de cette valeur elle-même. 


 \subsection{Introduction à la \og quantification\fg{}}

Considérons les propositions \og Tous les étudiants sont sérieux\fg{}
et \og certains étudiants sont sérieux\fg{}. 

La généralisation du calcul propositionnel peut paraître encore
plus grand que dans les exemples précédents, puisque la propriété
évoquée (\og être sérieux\fg{} ) est accordée, par ces propositions,
non pas seulement à un individu bien précis, mais à certains
individus, considérés dans leur ensemble, ou même à toute une
catégorie d'individus, sans qu'aucun ne soit nommément désigné. 
Ce troisième exemple suggère la notion de \emph{quantification} d'une
variable (tous les\ldots, certains\ldots). 


% L'objet du calcul des prédicats est d'étudier et de formaliser les
% notions qui viennent d'être brièvement évoquées, et que le calcul
% propositionnel ne permet pas de faire apparaître.



%\subsection{Sujets et individus}

\section{Définitions}



\subsection{Termes}

Le calcul des prédicats fait intervenir des variables, qui prennent
des valeurs dans un certain ensemble appelé univers du
discours qui par la suite sera souvent noté $U$.

% Les éléments de cet univers sont appelés \emph{sujets}. Un sujet distingué ou
% \emph{individu} est une instance de l'univers du discours qui peut prendre la
% place du sujet.

% \begin{Ex}
%  Le symbole 7 est un individu, ou un sujet distingué, dans l'univers
%  du discours des entiers naturels. 
% \end{Ex}



% Il existe deux manières de distinguer un sujet de l'univers du
% discours. 

% \begin{itemize}

% \item le nommer (donner explicitement son nom, ou le symbole qui le
%   représente), comme dans l'exemple précédent, pour l'entier 7. 

% \item le désigner indirectement par une \og propriété\fg{}
%   caractéristique (qu'il doit donc être le seul à posséder, de manière 
%   à ce qu'il soit identifié sans aucune ambiguïté). 
% Par exemple, si \textit{Pierre} est le père de \textit{Jean}, il est possible de
% distinguer \textit{Pierre} sans le nommer explicitement par la locution \og
% \textit{le père de Jean}\fg{}. 
% \end{itemize}



%De manière tout à fait précise :
\begin{Def}[Symbole fonctionnel]
\index{Symbole fonctionnel}
Soit $f$ une fonction du produit d'univers $U_1\times U_2\times\ldots\times U_n$
dans $U'$. Le symbole fonctionnel $f$ est dit d'\emph{arité} $n$ et on note $f_n$.
\end{Def}

% \begin{Ex}
% Le groupe opératoire à 1 place $\textit{pere}(x)$ désigne sans
% ambiguïté un et un seul individu dans l'univers des êtres humains, dès
% que la variable $x$ a été remplacée par un sujet distingué. 
% Si \textit{Jean} est bien un nom d'individu (c'est à dire, désigne 
% bien un individu unique), s'il en est de même de \textit{Pierre}, et 
% si \textit{Pierre} est le père de \textit{Jean}, alors 
% $\textit{pere}(\textit{Jean})$ distingue l'individu \textit{Pierre}.
% \end{Ex}

Lorsque l'expression $f(x_1, \ldots, x_n)$ ne dépend pas de $x_1,
\ldots, x_n$, on peut la remplacer par une constante $c$ de l'univers.




\begin{Def}[Terme]
\noindent 
Un \emph{terme} est défini de manière récursive par:

\begin{itemize}

\item une variable,

\item une  constante,

\item l'expression $f(t_1,t_2,\ldots,t_n)$ si $t_1,t_2,\ldots,t_n$ sont des
  termes et $f$ un symbole  fonctionnel d'arité $n$  
\end{itemize}
\end{Def}





\subsection{Prédicats et atomes}

On cherche à formaliser les relations qui peuvent lier des
individus de l'univers du discours. 
Par exemple, \og 22 est le double de 11\fg{}, \og 46 est le double de
45\fg{} sont 
des propositions (vraies ou fausses!) qui évoquent la relation \og
être le double de\fg{} . 


\begin{Def}[Symbole prédicatif]
Soit $p$ une fonction du produit d'univers $U_1\times U_2\times\ldots\times U_n$
dans $\{\textit{vrai},\textit{faux}\}$.
Le symbole prédicatif $p$ d'\emph{arité} $n$ (notée $p_n$) est aussi nommé
\emph{prédicat $p$}.
\end{Def}

\begin{Def}[Atome]
Un atome est de la forme $p(t_1, . . . , t_n)$, où $p$ est un
symbole de prédicat d'arité $n$ et $t_1$,\ldots, $t_n$ sont des termes.
\end{Def}


\section{Quantificateurs}

\subsection{Quantificateur universel}

Considérons la proposition \og Tous les étudiants travaillent les
mathématiques\fg{} pour l'analyser du point de vue du calcul 
des prédicats.
%Aucun connecteur logique n'apparaît. 
On peut exprimer ceci à l'aide un prédicat binaire qui peut être formalisé
par $\textit{travaille}(x,y)$, et qui signifie qu'un individu $x$ travaille une
certaine matière $y$. 


% Il faut préciser l'univers du discours, il s'agit ici d'un ensemble
% produit cartésien de deux ensembles : 
% \begin{itemize}
%  \item le premier est l'ensemble des étudiants,
%  \item le second un ensemble de noms de matières (celles qui sont
%    susceptibles d'être enseignées). 
% \end{itemize}
 
% Il est bien clair qu'il s'agit d'une proposition. Or, si la seconde
% variable ($y$) est bien remplacée par un symbole d'individu ($maths$),
% aucun nom, explicite ou implicite, n'est donné pour désigner un
% étudiant particulier : on a \og $\textit{travaille}(x,maths)$\fg{} sans que
% l'on sache \og qui est $x$\fg{} . 

% Il s'agit d'une construction particulière, qui permet d'obtenir des
% propositions à partir de prédicats sans qu'une variable soit
% distinguée, et qui porte le nom de quantification : le sujet $x$ n'est
% pas distingué, il est \emph{quantifié}. 


La notation utilisée pour cette quantification est \og $\qqs$ \fg{} qui
représente un A à l'envers (pour \emph{All}).
Ainsi on représente la proposition ci dessus par 
$$ \qqs x\, . \, \textit{travaille}(x,\textit{maths}).$$



\begin{Def}[Quantificateur universel]
$\qqs$ est un symbole de quantificateur, appelé le
\emph{quantificateur universel}\index{quantificateur!universel}. On
dit alors que $\qqs x$ est le quantificateur universel de la variable
$x$. 
\end{Def}

\begin{Rem} La présence du symbole de quantification est indispensable
  pour donner du sens aux formules avec variables.
\begin{itemize}
\item $\forall x \, . \, \textit{travaille}(x,\textit{maths})$ est une
  proposition. La variable $x$ est dite \emph{liée} au quatificateur $\forall$;
 \item $\textit{travaille}(x,\textit{maths})$ n'est pas une
proposition: on ne peut pas lui attribuer une valeur de
vérité. Il est nécessaire de substituer $x$ par un terme distinguant
un individu pour que cela le devienne 
(i.e. 
$\textit{travaille}(Jean,\textit{maths})$ ou bien  
$\textit{travaille}(\textit{fils}(\textit{Pierre}),\textit{maths})$).
Dans cette expression, la
variable $x$ est dite \emph{libre}. 
\end{itemize}
\end{Rem}

\begin{Exo}
  Pour chacune des formules $A$ suivantes, 
  préciser 
  l'ensemble $\textit{Var}(A)$ des variables de A, 
  l'ensemble $\textit{Varliees}(A)$ des occurences liées de $\textit{Var}(A)$, 
  l'ensemble $\textit{Varlibres}(A)$ des occurences libres de $\textit{Var}(A)$.
\begin{enumerate}
\item  $ A \equiv P (f (x, y)) \lor \forall z\, .\, Q(a, z)$
\item  $A \equiv (\forall x \,.\,  P(x, y, z)) \lor (\forall z\,.\, Q(z)
  \imp R(z))$
\item  
  $A \equiv \forall x\,.\, (\forall y\,.\, P (x, y) \imp \forall z\,.\, 
  Q(x, y, z))$
\end{enumerate}
\end{Exo}


\subsection{Quantificateur existentiel}


Dans la proposition \og Tous les étudiants travaillent au moins une 
matière\fg{}, intervient le même prédicat binaire 
$\textit{travaille}(x,y)$; on remarque qu'aucun étudiant n'est 
explicitement nommé, pas plus que la matière qu'il travaille. Si le 
\og Tous \fg{} induit une quantification universelle, le \og au moins 
une matière \fg{} signifie qu'il existe une matière travaillée par 
cet étudiant. Il suffit alors d'introduire le quantificateur 
existentiel, représenté par un E (première lettre de \emph{Exists}) retourné
($\exi$).


Cet exemple se traduit alors par  
$$\qqs x\, . \, \exi y\, . \, \ \textit{travaille}(x,y)$$
où la variable
$x$ est liée par le quantificateur universel $\qqs x$ et la variable
$y$ est liée par le quantificateur existentiel $\exi y$. 

% AG : ce ne sont pas des quantificateurs, mais des modalités.
% \begin{Rem}
% Dans d'autres logiques (modales, temporelles\ldots), on fait
% intervenir d'autres symboles de quantificateurs. 
% Ces autres logiques se situent en dehors du cadre de notre étude.
% \end{Rem}

\begin{Exo}
Formalisez les affirmations suivantes, en utilisant uniquement les
prédicats indiqués, les connecteurs logiques et les quantificateurs.
 \begin{enumerate}
\item  Personne n'est parfait ($p(x)$ représente que $x$
  est parfait)  
\item   0 est multiple de chaque nombre entier 
($e(x)$ et $m(x,y)$ signifient respectivement que $x$ est un entier
et que $x$ est un multiple de $y$).
\item  les absents n'ont pas tous tort 
($a(x)$ et $t(x)$  signifient respectivement que $x$ est absent 
et que $x$ a tort)
\end{enumerate}
% Réponses :
% \opt{prof}{
%  \begin{enumerate}
% \item  $\forall x \,. \, \non p(x)$
% \item  $ \forall x \,.\, e(x) \imp m(0,x)$
% \item  $\exists x \, . \, a(x) \et \non t(x)$
%  \end{enumerate}
% }
% \opt{etud}{
% \vspace{10cm}
% } 
\end{Exo}

\begin{Exo}
Soit les prédicats 
$\textit{curé}(x)$ ($x$ est un curé),
$\textit{vélo}(y)$ ($y$ est un vélo) et 
$\textit{possède}(x,y)$ ($x$ possède $y$).

Traduisez en langage courant les formules quantifiées suivantes :
\begin{enumerate}
\item $\forall x\, . \textit{vélo}(x) \imp 
(\exists z \, . \, \textit{curé}(z) \land \textit{possède}(z,x))$.
\item $\forall x\, . \textit{curé}(x) \imp 
(\forall y,z \, . \, (\textit{velo}(y) \land \textit{velo}(z) \land y
\neq z ) \imp 
(\neg \textit{possède}(x,y) \lor \neg \textit{possède}(x,z)))$
\item $\exists x \, . \, \textit{curé}(x) \land 
(\forall y \, . \, \textit{vélo}(y) \imp \neg
\textit{possède}(x,y))$. 
\end{enumerate}
\end{Exo}




\subsection{Alternance de quantificateurs}

Attention : \emph{Il est interdit d'intervertir des quantificateurs 
de symboles différents} (si l'on désire que la formule conserve le 
même sens, bien entendu).

\begin{Ex} $ $

\begin{itemize}
\item $\qqs x\, . \, \exi  y \, .\, \textit{travaille}(x,y)$ signifie que
tout étudiant travaille une matière (au moins).
Autrement dit, la matière travaillée  dépend de cet étudiant, elle
n'est éventuellement pas la même pour tous les étudiants. 

\item La formule $\exi y\, . \, \qqs x\, .\, \ 
\textit{travaille}(x,y)$ signifie qu'il y a une matière que tous les 
étudiants travaillent. La différence fondamentale avec le cas 
précédent est que, dans cette dernière affirmation, on affirme que 
tous les étudiants travaillent la même matière.
\end{itemize}
\end{Ex}

% AG : cet exemple n'est pas très satisfaisant, car donne vrai dans
% les deux cas.
% \begin{Ex}
% Un autre exemple, plus mathématique :
% \begin{itemize}
% \item $\qqs x\exi y\,(x+y=x)$, soit: \og pour tout $x$, on peut
%   trouver un $y$, tel que $x+y=x$\fg{} . Si l'univers du discours est
%   une algèbre de Boole, il est clair que la formule est vraie : il
%   suffit pour s'en convaincre de choisir $y=x$, et on a bien, en
%   algèbre de Boole, $x+x=x$: la valeur de $y$ dépend bien de celle de
%   $x$ (c'est la même). 

% \item $\exi y \qqs x\,(x+y=x)$, soit: \og il existe une valeur de $y$
%   telle que, pour tout $x$, $x+y=x$\fg{} . Si l'univers du discours
%   est une algèbre de Boole, il est clair que la formule est vraie :
%   la valeur 0 pour $y$ convient, et, si $y=0$, on a bien, quelle que
%   soit la valeur de $x$, $x+0=x$. 
% \end{itemize}
% \end{Ex}




% \begin{Ex}
% En supposant que $(a,b,c)$ prenne ses valeurs dans un univers du
% discours qui est une partie de $\R^3$ telle que $b^2-4ac>0$, la
% formule : 

% \begin{itemize}

% \item $\qqs a\,.\, \qqs b \, . \,   \qqs c \, .\,   \exi x\, .\, \
%   ax^2+bx+c=0$ est une formule vraie (une équation du second
%   degré dont le discriminant est positif admet des racines réelles, et
%   tout le monde sait que les valeurs de ces racines dépendent de
%   celles de $a$, de $b$ et de $c$). 

% \item $\exists x\,.\,\qqs a\,.\,\qqs b\,.\,\qqs c\,.\, ax^2+bx+c=0$ est
%   une formule fausse : il n'y a pas de réel qui soit solution de
%   n'importe quelle équation du second degré ! 
% \end{itemize}
% \end{Ex}

\begin{Exo}
Dans cet exercice, nous considérons qu'aimer est une relation binaire 
(non nécessairement symétrique). On note $\textit{aime}(x, y)$ 
si la personne $x$ aime la personne $y$.

\begin{enumerate}
\item Représentez, à l'aide de propositions logiques, les phrases suivantes :
\begin{enumerate}
\item  Quelqu'un aime Valentine.
\item Personne n'aime Quentin.
\item Toute personne aime quelqu'un.
\item Quelqu'un est aimé de tous.
\item Toute personne s'aime.
\item  Il n'y a personne qui ne s'aime pas lui-même.
\end{enumerate}
\item Les deux propositions suivantes sont-elles \'equivalentes ?
$$(\exists x\, .\, \textit{aime}(x,\textit{caroline}) )\land  
(\exists x\, .\, \textit{aime}(\textit{caroline}, x) )$$ 
et 
$$\exists x \, . \,  \textit{aime}(x,\textit{caroline}) 
\land  \textit{aime}(\textit{caroline}, x)$$
\end{enumerate}
\end{Exo}

\begin{Exo}
Formaliser les propositions suivantes dans le calcul des prédicats.
\begin{enumerate}
\item \og Il existe une planète plus petite que toutes les autres;\fg{}
\item \og Il y a une planète plus grande que tout objet du système solaire;\fg{}
\item \og Toute planète a une planète plus proche du soleil qu'elle;\fg{}
\item \og Certaines planètes sont plus petites que Neptune, d'autres pas;\fg{}
\item \og Il n'y a pas de planète qui soit plus grande qu'une autre tout en 
  étant plus proche du soleil qu'elle;\fg{}
\item \og Tout ce qui tourne autours de la Terre est plus petit que toutes 
  les planètes;\fg{}
\item \og Certaines planètes sont plus grosses que Neptune, mais aucune n'est 
  plus éloignée du soleil qu'elle;\fg{}
\item \og Certaines planètes sont plus grosses que Neptune tout en étant  
  plus éloignées du soleil qu'elle.\fg{}
\end{enumerate}
\end{Exo}

% \begin{Exo}
% Traduire les affirmations suivantes en formules au moyen de prédicats
% et de quantificateurs.
% \begin{enumerate}
% \item \og la somme des angles d'un triangle vaut 180 degrés \fg{}
% \item \og deux droites perpendiculaires a une même troisième sont
%   parallèles entre elles\fg{}
% \item \og un nombre complexe égal à son conjugué est un nombre réel
%   \fg{}
% \item \og après 4, tout entier pair est la somme de deux nombres
%   premiers\fg{} 
% \item \og un polynome de degré $n$ ne peut pas s'annuler plus de $n$
%   fois \fg{}
% \end{enumerate} 
% \end{Exo}

% \begin{Exo}
% Imaginer une façon d'exprimer l'affirmation suivante 
% \og
% $\epsilon + \epsilon + \epsilon + \ldots +\epsilon$ finit toujours par
% faire beaucoup, même si $\epsilon$ est très petit \fg{} au moyen d'un
% prédicat d'arité 3 et de trois quantificateurs.
% \end{Exo}

\subsection{Portée d'un quantificateur}

\begin{Def}[Portée d'un quantificateur] La \emph{portée d'un 
quantificateur}\index{portée d'un 
quantificateur}\index{quantificateur!portée} dans une formule du 
calcul des prédicats est la partie de cette formule couverte par ce 
quantificateur.
\end{Def}


Par convention, dans l'écriture d'une formule, un quantificateur est
prioritaire sur tout connecteur logique. Sa portée est donc
généralement clairement délimitée par une paire de parenthèses, avant
le quantificateur jusqu'après la formule elle-même. 


\begin{Exo}
Dans cet exercice $f_n$ signifie que le symbole $f$ (propositionnel ou
prédicatif)  est d'arité $n$.
On considère un langage 
$\mathcal{L}=\{f_1, g_1, h_2, R_1,S_2,T_2,=_2\}$ et les expressions
suivantes:
\begin{itemize}
\item 
$ \varphi_1  : 
\exists x \,. \, 
(
(\forall y \, . \, 
(\exists z \,.\,
R(x)))) \lor
(\exists y \, .\, 
(\neg 
(\forall z \, . \, 
(S(h(x,z),x)))))
$

\item 
$ \varphi_2  : 
(\forall x \, .\, 
(T(f(x),y)) 
\imp
(\neg 
(\exists x \, .\, (f(x,y)))))$

\item 
$ \varphi_3  :
(\forall z \, .\,
T(x,y) \imp
(\exists y \,.\,
((\forall x' \, . \,\neg (f(x) = y))) \lor T(y,z)))$

\item 
$ \varphi_4  : 
(\forall x \,.\,
(\exists y  \,.\,
(( g(y) = x) \lor 
(\neg T(y,y)))))
\imp 
(\exists y \,.\,
(\forall x \,.\,
(T(y,g(x)))))$
\end{itemize}

\begin{enumerate}
\item Parmi ces expressions, lesquelles sont des formules de
$\mathcal{L}$ ?
\item Pour celles qui sont des formules, supprimer les parenthèses
  inutiles.
\item Déterminer les occurrences liées des variables dans les formules.
\end{enumerate}
\end{Exo}


\begin{Exo}
Classer les huit propositions suivantes dans les deux premières
colonnes libres du tableau ci-dessous de 
manière à ce que les relations annoncées soient vérifiées.

Compléter le tableau avec les formules correspondantes.

\begin{enumerate}
\item Dans cette assemblée, tout le monde parle l'anglais et le français.
\item Dans cette assemblée, tout le monde parle l'anglais ou le français.
\item Dans cette assemblée, tout le monde parle l'anglais et tout le monde 
  parle le français.
\item Dans cette assemblée, tout le monde parle l'anglais ou tout le monde 
  parle le français.
\item Un accompagnateur au moins parlera le russe et un accompagnateur  
  au moins parlera le chinois.
\item Un accompagnateur au moins parlera le russe ou un accompagnateur  
  au moins parlera le chinois.
\item Un accompagnateur au moins parlera le russe et le chinois.
\item Un accompagnateur au moins parlera le russe ou le chinois.
\end{enumerate}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
  \hline
  \multirow{2}{0.5cm}{\ldots} & $\Rightarrow$ & 
  \multirow{2}{0.5cm}{\ldots} &
  \multirow{2}{3.5cm}{$\forall x\,. \, P(x) \ldots Q(x)$} & 
  \multirow{2}{0.5cm}{$\approx$} & 
  \multirow{2}{3.5cm}{$\forall x\,. \, P(x) \ldots \forall y\,. \, Q(y)$}\\
  \cline{2-2}
  & $\Leftarrow$ & & & & \\
  \hline
  \multirow{2}{0.5cm}{\ldots} & $\Rightarrow$ & 
  \multirow{2}{0.5cm}{\ldots} &
  \multirow{2}{3.5cm}{\ldots} & 
  \multirow{2}{0.5cm}{$\not \approx$} & 
  \multirow{2}{3.5cm}{\ldots}\\
  \cline{2-2}
  & $\not \Leftarrow$ & & & & \\
  \hline
  \multirow{2}{0.5cm}{\ldots} & $\Rightarrow$ & 
  \multirow{2}{0.5cm}{\ldots} &
  \multirow{2}{3.5cm}{\ldots} & 
  \multirow{2}{0.5cm}{$ \approx$} & 
  \multirow{2}{3.5cm}{\ldots}\\
  \cline{2-2}
  & $ \Leftarrow$ & & & & \\
  \hline
  \multirow{2}{0.5cm}{\ldots} & $\Rightarrow$ & 
  \multirow{2}{0.5cm}{\ldots} &
  \multirow{2}{3.5cm}{\ldots} & 
  \multirow{2}{0.5cm}{$\not \approx$} & 
  \multirow{2}{3.5cm}{\ldots}\\
  \cline{2-2}
  & $\not \Leftarrow$ & & & & \\
  \hline
\end{tabular}
\end{center}
\end{Exo}






\subsection{Formules du calcul des prédicats}
% AG : Cette introduction ne convient pas : on utilise aussi des
% connecteurs logiques entre formules avec variables libres !
% JFC : un atome peut contenir des variables. Cela permet de définir 
% des formules avec variables libres
% Comme les prédicats produisent des propositions
% \begin{itemize}
%  \item soit quand les variables sont remplacées par des individus,
%  \item soit quand elles sont liées par quantification,
% \end{itemize}
%  il est possible de relier ces propositions par les connecteurs 
%  logiques habituels, comme en calcul propositionnel. On obtient ainsi 
%  une formule du calcul des prédicats\ldots


\begin{Def}[Formule]
La définition d'une \emph{formule}\index{formule} est:

\begin{itemize}

\item un atome est une formule,

\item si $P$ est une formule, si $Q$ est un symbole de quantificateur
  et si $x$ est un symbole de variable, alors $Qx\,.\, P $ est une
  formule, 

\item si $P$ est une formule, alors $\non(P)$ est une formule,

\item si $P$ et $Q$ sont des formules, alors 
  $(P \ou Q)$, 
  $(P \et Q)$,
  $(P \imp Q)$, 
  $(P \eqv Q)$ sont des formules,

\item il n'existe pas d'autres manières de construire une formule
qu'en appliquant les règles précédentes un nombre fini de fois.
\end{itemize}
\end{Def}

\begin{Exo}
On considère un ensemble d'objets de différentes couleurs.
Chacun de ces objet porte un numéro et possède une forme géométrique
particulière (cube, sphère prisme).
En utilisant les prédicats 
$\textit{pair}(x)$, $\textit{cube}(x)$,
$\textit{vert}(x)$\ldots, formalisez les phrase suivantes en logique 
des prédicats
\begin{enumerate}
\item Si un objet est sphérique, alors cet objet n'est pas vert ou
  porte un numéro impair.
\item S'il existe un objet vert sphérique, alors il existe un objet
  vert portant un numéro impair.
\item Si tout objet vert porte un numéro impair, alors aucun objet
  sphérique n'est vert.
\end{enumerate}
\end{Exo}



\section{Sémantique}




\subsection{Valeurs de vérité}


Le calcul des prédicats utilise, comme le calcul propositionnel, les
connecteurs logiques, et produit des propositions.
Il est possible d'étendre la notion de \og valeur de vérité\fg{} au
calcul des prédicats. 
Mais l'étude de la valeur de vérité d'une formule du calcul des
prédicats est beaucoup plus compliquée.

\begin{enumerate}
 \item Une expression typique (une forme propositionnelle) du calcul
   propositionnel est $P\imp Q$. 
Les \og atomes\fg{} sont ici des variables propositionnelles qui
peuvent être remplacées par n'importe quelle proposition. Quelle que
soit cette proposition, sa valeur de vérité ne peut être que \og
\vrai \fg{} ou \og \faux\fg{}. 
Cela permet de lui associer une simple variable booléenne, sa valeur
de vérité, pour obtenir simplement la fonction de vérité $\sur p+q$. 

\item Une expression analogue (une formule) du calcul des prédicats
  pourrait être $\forall x\, .\, p(x,y)\imp q(x,z)$. 
  Les atomes sont ici des prédicats binaires qui, eux aussi, ne
  peuvent prendre que les valeurs \og \vrai\fg{} ou \og \faux\fg{}, mais
  pas indépendamment des individus considérés.
\end{enumerate}



Il n'est donc pas possible de remplacer un atome par une simple
variable booléenne. Seule une fonction booléenne (de variables non
booléennes) peut convenir, pour faire intervenir les valeurs des
variables qui sont les arguments du prédicat. 
\begin{itemize}
 \item si $f_p(x,y)$ est la fonction booléenne associée au prédicat
   $p(x,y)$ 
\item si $f_q(x,z)$ est celle qui est associée à $q(x,z)$, 
\end{itemize}
alors la fonction de vérité de la formule est: $\sur{f_p(x,y)}+f_q(x,z)$.

Attention, $x$, $y$ et $z$ ne sont pas ici des variables booléennes,
mais elles prennent leurs valeurs dans l'univers du discours. Il n'est
donc pas question de \og calculer avec $x$, $y$ et $z$ comme en
algèbre de Boole\fg{}. 

Le seul moyen, en général, pour étudier une telle fonction de vérité
est de construire le tableau de ses valeurs, en donnant à $x$, $y$ et
$z$ successivement toutes les valeurs possibles dans l'univers du
discours (si celui-ci est infini, on imagine aisément les problèmes
qui vont se poser\ldots). 


Les définitions de tautologie et de conséquence logique s'adaptent
comme suit.

\begin{Def}[Tautologie, conséquence logique, équivalence]
si $P$ et $Q$ sont des formules du calcul des prédicats

\begin{itemize}

\item $\tauto P$ [$P$ est une tautologie] si et seulement si, pour
  tous les univers du discours possibles, pour tous les prédicats qui
  interviennent dans $P$, et pour toutes les valeurs des
  variables dans chacun des univers, la valeur de vérité de $P$ est
  \og \vrai\fg{}. 

\item $\{P\}\tauto Q$ [$Q$ est conséquence logique de $P$] si et seulement
  si, dans les mêmes conditions que ci-dessus, chaque fois que $P$ est
  vraie, $Q$ l'est aussi. 

\item $P\approx Q$ [les formules $P$ et $Q$ sont équivalentes] si et
  seulement si $\{P\}\tauto Q$ et $\{Q\} \tauto P$. 

\end{itemize}
\end{Def}


Il reste à  donner la définition de la fonction de vérité pour les
nouveaux symboles introduits (les quantificateurs)\ldots 


\begin{itemize}
\item la valeur de vérité de $\qqs x\,. \, p(x)$ est obtenue en faisant la
  liste des valeurs de vérité de $p(x)$ pour toutes les valeurs
  possibles de $x$ dans l'univers du discours: 
  % (liste effective lorsque  c'est possible, ou démonstration).
  si, pour toute valeur de $x$, la
  valeur de vérité de $p(x)$ est $\vrai$, alors la valeur de vérité de
  $\qqs x\, . \, p(x)$ est $\vrai$. S'il y a une seule valeur de $x$ pour
  laquelle la valeur de vérité de $p(x)$ est $\faux$, alors la valeur
  de vérité de $\qqs x\, . \, p(x)$ est $\faux$. 

\item la valeur de vérité de $\exi x\, . \, p(x)$ est obtenue en faisant la
  liste des valeurs de vérité de $p(x)$ jusqu'à ce qu'on trouve
  $\vrai$. Si on trouve $\vrai$, la valeur de vérité de 
  $\exi x\, . \, p(x)$
  est $\vrai$. Si, pour tout élément $x$ de l'univers du discours, la
  valeur de vérité de $p(x)$ est $\faux$,
  % (liste effective ou  démonstration),
 alors celle de $\exi x\, . \, p(x)$ est $\faux$. 

\end{itemize}


Bien entendu, dans certains cas, il n'est pas nécessaire d'établir
effectivement la table de vérité d'une formule du calcul des prédicats
pour prouver qu'il s'agit d'une tautologie. Par exemple, il est bien
clair que, pour un atome $p(x,y,z)$, on a: 
$\tauto  (\forall x, y, z \, . \,  p(x,y,z)) \imp 
(\forall x, y, z \, . \,  p(x,y,z)) $.  

% Soit $p$ est un prédicat unaire.
% Pour donner un exemple de la complexité introduite en théorie
% des valeurs de vérité par le calcul des prédicats, étudions la formule
% $\forall x,y \, . \, p(x) \imp p(y)$ 
% pour savoir s'il s'agit d'une
% tautologie. Pour prouver qu'il s'agit d'une tautologie, il faut prouver
% que:  

% \begin{itemize}

% %\item 
% \item pour tout univers du discours ${\cal U}$,

% \item pour toutes valeurs des variables $x$ et $y$ dans ${\cal U}$,

% \end{itemize}
% la valeur de vérité de la formule est $\vrai$. \og Pour tout univers du
% discours\fg{} : il faut envisager des univers à 1, puis 2,\ldots
% éléments et essayer d'en déduire un résultat général, si c'est
% possible. 

% \begin{itemize}
 
% \item Dans un univers à un seul élément, $x$, comme $y$, ne peut
%   prendre qu'une seule valeur; on a donc $x=y$, et donc la valeurs de
%   vérité de $p(x)$ est la même que celle de $p(y)$, et donc $p(x)\imp
%   p(y)$ est $\vraie$ [table de l'implication]. 

% \item Dans un univers à deux éléments, pour que la valeur de vérité de
%   $p(x)$ soit définie, il faut se la donner pour chacune des deux
%   valeurs de $x$; or, il faut le faire \og pour tout prédicat unaire
%   $p$\fg{} , donc envisager toutes les fonctions booléennes de deux
%   variables: il y en a quatre, que nous noterons $z$, $i$, $n$, et
%   $r$. Désignons les deux éléments de ${\cal U}$ par 1 et 2 (pour ne
%   pas les confondre avec des variables booléennes):\saut 
% \centerline{\begin{tabular}{|c|c|c|c|c|} \hline
% $x$ & $z(x)$ & $i(x)$ & $n(x)$ & $r(x)$ \\ \hline
% $1$ & $\faux$ & $\faux$ & $\vrai$ & $\vrai$ \\ \hline
% $2$ & $\faux$ & $\vrai$ & $\faux$ & $\vrai$ \\ \hline
% \end{tabular}}\par
% \noindent Puis il faut faire le tableau des valeurs de vérité de
% $p(x)$, $p(y)$ et de $p(x)\imp p(y)$ en fonction des valeurs de $x$ et
% de $y$ et de la fonction booléenne associée à $p$ ($z$, $i$, $n$, ou
% $r$)\saut\centerline{ 
% \begin{tabular}{|c|c|c|c|c|c|}\hline
% fonction booléenne de $p$ & $x$ & $y$ & $p(x)$ & $p(y)$ & $p(x)\imp p(y)$
% \\ \hline $z$ & 1 & 1 & $\faux$ & $\faux$ & $\vrai$ \\ \hline 
% & 1 & 2 & $\faux$ & $\faux$ & $\vrai$ \\ \hline
% & 2 & 1 & $\faux$ & $\faux$ & $\vrai$ \\ \hline
% & 2 & 2 & $\faux$ & $\faux$ & $\vrai$ \\ \hline
% $i$ & 1 & 1 & $\faux$ & $\faux$ & $\vrai$ \\ \hline
% & 1 & 2 & $\faux$ & $\vrai$ & $\vrai$ \\ \hline
% & 2 & 1 & $\vrai$ & $\faux$ & $\faux$ \\ \hline
% & 2 & 2 & \dotfill & \dotfill & \dotfill \\ \hline
% $n$ & \dotfill & \dotfill & \dotfill & \dotfill & \dotfill \\ \hline
% \end{tabular}}\par 
% \noindent Inutile de construire le reste du tableau: on a trouvé $\faux$ dans une ligne, donc $p(x)\imp p(y)$ n'est pas une tautologie [en effet, il existe un prédicat unaire, un univers à deux éléments, et, dans cet univers, une valeur de $x$ et une valeur de $y$ pour lesquels la formule est fausse\ldots].

% \end{itemize}


Donnons enfin deux exemples pour lesquels la construction d'une table
de vérité n'est pas nécessaire : 

\begin{Exo}
Montrer que 
$\tauto (\qqs x\, . \, p(x,x))\imp (\qqs x \, . \, (\exi
y\, . \, p(x,y)))$.

% Soit ${\cal U}$ un univers du discours, $p$ une relation binaire
% sur ${\cal U}$.

% \begin{itemize}
 
% \item Premier cas : dans ${\cal U}$, $\qqs x\, . \, p(x,x)$ est
%   $\faux$; alors 
%   l'implication est vraie. 

% \item Deuxième cas : dans ${\cal U}$, $\qqs x\,. \, p(x,x)$ est 
% $\vrai$; donc, pour chaque valeur de $x$ dans ${\cal U}$, $p(x,x)$ 
% est vrai. Alors  $\forall x \, . \, \exi y\,.\, p(x,y)$ est $\vrai$ 
% car, pour toute valeur de $x$, il suffit de prendre pour $y$ la même 
% valeur que celle de $x$ pour que $p(x,y)$ soit $\vrai$.

% \end{itemize}
\end{Exo}


% \begin{Ex}
% Montrer que 
% $(\qqs x\, . \, (r(x)\imp s(x)))\et (\exi x\,.\, (\non r(x)\et s(x))$
%  n'est ni une antilogie, ni une tautologie.

% Pour montrer que cette formule n'est pas une antilogie, il suffit
% d'exhiber un exemple dans lequel elle est vraie; pour montrer qu'elle
% n'est pas une tautologie, il suffit d'exhiber un exemple dans lequel
% elle est fausse. 

% \begin{itemize}

% \item ${\cal U}$ est l'ensemble des habitants de la France; $r(x)$ est
%   le prédicat \og $x$ habite Belfort\fg{} et $s(x)$ est le prédicat \og
%   $x$ habite la France\fg{} . Puisque Belfort est en France, tout
%   habitant de Belfort habite la France, donc 
%   $\qqs x\, . \, r(x)\imp s(x)$
%   est $\vrai$. Mais tous les habitants de la France ne sont pas
%   concentrés à Belfort, autrement dit: il existe des habitants de la
%   France qui n'habitent pas Belfort, 
% donc: $\exi x\, . \, \non r(x) \et s(x)$ est $\vrai$; enfin, d'après
% la table de vérité de la conjonction logique, la formule est vraie. 

% \item ${\cal U}$ est un ensemble $E$, dans lequel on a défini deux
%   parties $R$ et $S$, telles que $S\sse R$; $r(x)$ est le prédicat \og
%   $x\in R$\fg{} et $s(x)$ est le prédicat \og $x\in S$\fg{} . Comme
%   $S\sse R$, tout élément extérieur à $R$ ne peut pas être dans $S$,
%   donc $\exi x\,.\, \non r(x) \et s(x)$ est $\faux$, et donc la formule
%   est fausse. 

% \end{itemize}

% \end{Ex}



\subsection{Simplification de formules quantifiées}
De la définition de la valeur de vérité d'une formule quantifiée, on 
peut déduire:

\begin{eqnarray*}
  \non (\exi x\, . \, p(x)) & \approx & (\qqs x \,.\, \non p(x))  \\
  \non (\qqs x \,.\, p(x)) &\approx & (\exi x\, . \, \non p(x))  
\end{eqnarray*}

% \begin{Ex}
% considérons la proposition (fausse): 
% \og l'ensemble des entiers naturels admet un élément maximum\fg{}. 
% Pour formaliser cette proposition en calcul des prédicats,
% il faut introduire le prédicat classique d'inégalité qu'il faudrait,
% en toute rigueur, noter $\le (x,y)$, qui signifie que $x$ est
% inférieur ou égal à $y$, mais 
% pour lequel nous conserverons la notation usuelle $x \leqslant
% y$. L'univers du discours est évidemment $\N$, et, pour exprimer que
% $\N$ admet un élément maximum, on exprime que tout élément de $\N$ est
% inférieur ou égal à cet élément maximum, 
% soit: 
% $$\exi M \,.\, \qqs n\,.\, n\leqslant M.$$

% % (en calcul des prédicats, on ne précise jamais
% % l'univers du discours dans la formule, comme on le fait habituellement
% % en mathématiques: $\exi M\in\N,\ \qqs n\in\N,\ n\leqslant M$)
% Pour montrer que cette proposition est fausse, 
% on intuite qu'il suffit de démontrer que 
% sa négation est vraie, soit 
% $$
% \non (\exi M \,.\, \qqs n\,.\, n\leqslant M).$$

% D'après ce que nous venons de voir, cette
% négation a même valeur de vérité que
% $\qqs M \, .\, \exi n\,.\, \non (n\leqslant M)$, ou encore 
% $\qqs M \, .\, \exi n\,.\, M<n$.
% Ceci signifie que, pour tout entier
% $M$, on peut trouver un entier $n$ qui est plus grand (il suffit de
% prendre $n$ égal à $M+1$).
% \end{Ex}

\begin{Exo}
\'Ecrire la négation des formules suivantes
\begin{enumerate}
\item  $\forall x \, .\, p(x) \imp q(x)$
\item  $\exists x \, .\, p(x) \land q(x)$
\item  $\forall x \, . \, p(x) \Ssi q(x)$
\item  $\exists x\, .\, (\forall y \,.\,
  q(x,y) \imp (p(x,y) \lor r(x,y)))$ 
\end{enumerate}

% Réponses:
% \opt{prof}{
% \begin{enumerate}
% \item $\exists x \, .\, p(x) \land \neg q(x)$
% \item $\forall x \, .\, p(x) \imp \neg q(x)$
% \item $\exists x \, . \, (p(x) \land  \neg q(x)) \lor (\neg p(x) \land q(x))$
% \item 
% $\forall x\, .\, (\exists y \,.\,
%   q(x,y) \land \neg p(x,y) \land \neg r(x,y))$ 
% \end{enumerate}
% }
% \opt{etud}{
% \vspace{10cm}
% } 
\end{Exo}

\begin{Exo}
\'Ecrire la négation des formules suivantes
\begin{enumerate}
\item  $\forall x \, .\, (\exists y \,.\, p(x,y) \land q(x,y))$
\item  $\forall x \, .\, (\exists y \,.\, p(x,y) ) \imp q(x)$
\item  $\forall x \, .\, (\exists y \,.\, p(x,y) ) \imp
  (\forall z\, .\, q(z))$
\item $ \forall x \,.\, r(x) \imp (\exists y \,.\, p(x,y))$
\end{enumerate}
\end{Exo}

\noindent Voici d'autres résultats d'équivalences entre formules
permettant de réduire la portée de quantificateurs.


\begin{Th}[Réduction de portée de quantificateurs]
Soit $p$ et $q$ des prédicats unaires. Alors on a les deux
équivalences suivantes :

\begin{eqnarray}
  (\qqs x\, . \, p(x) \et q(x)) 
  &\approx& 
  (\qqs x\, . \, p(x)) 
  \et
  (\qqs y\, . \, q(y)) \label{eq:reduction:forall}\\
  (\exi x\,.\, p(x) \ou q(x)) 
  &\approx&
  (\exi x\,.\, p(x))
  \ou
  (\exi y\,.\, q(y))
   \label{eq:reduction:exists}
\end{eqnarray}
\end{Th}

\begin{Proof}$ $ 

\paragraph{Preuve  de (\ref{eq:reduction:forall}).}
Si, pour toute valeur de $x$, $p(x)$ et $q(x)$ sont
simultanément vrais, alors, pour toute valeur de $x$, $p(x)$ est vrai,
et, 
pour toute valeur de $y$, $q(y)$ est vrai. 
Réciproquement, si, pour toute
valeur de $x$, $p(x)$ est vrai, et, si, pour toute valeur de $y$,
$q(y)$ 
est aussi vrai, il est bien évident que, pour toute valeur de $x$,
$p(x)$ 
et $q(x)$ sont simultanément vrais. 

\paragraph{Preuve  de (\ref{eq:reduction:exists}).}
S'il existe une valeur de $x$ pour laquelle l'une au moins des deux 
propriétés $p(x)$ ou $q(x)$ est vraie, il est bien clair qu'il existe 
une valeur de $x$ pour laquelle $p(x)$ est vraie ou qu'il en existe 
une pour laquelle $q(y)$ est vraie; la réciproque est aussi évidente.
\end{Proof}

\begin{Exo}
Trouver 
\begin{enumerate}
\item un exemple où $\forall x \, .\, p(x) \lor q(x)$ est vraie  
  sans que $(\forall x \, .\, p(x)) \lor (\forall x \, .\, q(x))$ ne le
  soit;
\item un exemple où 
$(\exists x \, .\, p(x)) \land (\exists x \, .\,  q(x))$ est vraie 
  sans que 
  $\exists x \, .\, p(x) \land q(x)$ ne le
  soit.
\end{enumerate}
\end{Exo}

\begin{Exo}
Pour chacune des formules suivantes,  
\begin{itemize}
\item dire si c'est une négation, une conjonction, une disjonction, 
une implication, une quantification (universelle ou existentielle);
\item donner la portée des quatificateurs;
\item donner les occurences libres des variables.
\end{itemize}

\begin{enumerate}
\item  $\exists x \, . \, A(x,y) \land B(x)$
\item  $\exists x \, . \, (\exists y \, . \, A(x,y) \Rightarrow B(x))$
\item  $\neg (\exists x \, . \, \exists y \, . \, A(x,y) \Rightarrow B(x))$
\item  $\forall x \, . \, \neg (\exists y \, . \, A(x,y))$
\item  $\exists x \, . \, A(x,y) \land B(x)$
\item  $\exists x \, . \, A(x,x) \land \exists y \, . \,B(y)$
\end{enumerate}
\end{Exo}

\subsection{Substitutions}

Si $t$ est  un terme et $\varphi$ est une formule pouvant contenir la
variable $x$, alors  $\varphi(t/x)$ est le résultat du remplacement de
toutes les occurrences libres de $x$ par $t$ dans $\varphi$. 


Le résultat du remplacement $\varphi(t/x)$ est une formule qui est 
une conséquence logique de la formule originale $\varphi$ si aucune 
des  variables libre de $t$ ne devient liée suite à ce remplacement. 
Pour éviter que de telles variables libres deviennent liées il suffit 
de changer le nom des variables liées de $\varphi$ en des noms frais 
(qui n'apparaissent pas dans les variables libres de $t$). L'oubli de 
cette condition est une cause fréquente d'erreurs de raisonnement.


A titre d'exemple, on considère la formule $\varphi$ définie par 
$\forall y \, .\, y \le x $ sur l'univers $\mathcal{U}$.
\begin{itemize}
\item Si $t$ est un terme sans la variable libre $y$, 
alors  $\varphi(t/x)$ signifie juste que $t$ est l'élément maximal.
\item A l'opposé, si $t$ est $y$, la formule $\varphi(y/x)$ est
  $\forall y\,.\, y \le y$ qui ne dit plus que $y$ est maximal. 
\end{itemize}

\begin{Exo}
Soit le langage $\mathcal=\{a, f_2, R_2, S_1\}$, les termes 
$t_i$ et les formules $\varphi_j$ suivantes.
\begin{itemize}
\item $t_1 = f(x,y)$
\item $t_2 = f(a,y)$
\item $t_3 = a$
\item $t_4 = f(x,f(x,x))$
\item $\varphi_1 : R(x,y) \imp \forall y \,. \, S(y)$
\item $\varphi_2 : 
  (\forall y \, .\, R(y,a) ) \imp 
  (\exists y \, .\, R(x,y))$
\item $\varphi_3 : 
  (\forall x \,.\,  \exists z \,.\, R(x,z))
  \land 
  (\exists x \,.\,  \forall y \,.\, R(y,x))$
\end{itemize}
Déterminer si $t_i$ est substituable à $x$ dans $\varphi_j$ et
calculer,  le cas échéant, $\varphi_j (t_i/x)$ pour $1 \le i \le 4$ et 
$1 \le j \le 3$. Dans le cas où $t_i$ n'est pas substituable, renommer
les variables qui le composent ou les variables de la formule afin
qu'il le soit.
\end{Exo}

\begin{Exo}
Quelle est la valeur de vérité des formules 
\begin{itemize}
\item $\varphi_1 = \exists x,y,z \, . \, 
  x \neq y \land 
  y \neq z \land 
  z \neq x $
\item $\varphi_1 = \forall x,y,z,t \, . \, 
  x \neq y \lor
  x \neq z \lor
  x \neq t \lor
  y \neq z \lor
  y \neq t \lor
  z \neq t$
\end{itemize}
 pour les univers suivants
\begin{itemize}
\item $\mathcal{U}_1 = \{0\}$;
\item $\mathcal{U}_2 = \{0,1\}$;
\item $\mathcal{U}_2 = \{0,1,3\}$.
\end{itemize}

% Réponse: 
% \begin{itemize}
% \item la formule $\varphi_1$ est fausse sur $\mathcal{U}_1$ et $\mathcal{U}_2$
% mais vraie sur $\mathcal{U}_3$;
% \item la formule $\varphi_2$ est vraie sur $\mathcal{U}_1$ et fausse ailleurs.
% \end{itemize}
\end{Exo}

\begin{Exo}
Dans le langage $\mathcal{L}=\{R_2, =_2\}$, on considère 
les formules
suivantes:
\begin{eqnarray*}
 \Gamma_1 &=&\forall x \,.\, \exists y\, .\, R(x,y) \\
 \Gamma_2 &=&\forall x \,.\, (\forall y\, .\, 
 (\exists z \, .\, R(x,z) \land R(z,y)) \imp R(x,y)) \\
 \Gamma_3 &=&\forall x,y \,.\, (R(x,y) \land R(y,x)) \Ssi
 y=x \\
 \Gamma_4 &=&\forall x,y \,.\, 
 (\exists z \, .\, \neg R(z,x) \land \neg R(z,y)) \lor x =y
\end{eqnarray*}
Déterminer la valeur de vérité de ces formules dans les
interprétations suivantes :
\begin{itemize}
\item $\mathcal{U}_1= \N$ et 
$R(x,y)$ est vraie si et seulement si  $x\le y$. 
Le prédicat $=$ a l'interprétation standard.

\item $\mathcal{U}_2= \N\setminus \{0\}$ et 
$R(x,y)$ est vraie si et seulement si  $x \neq y$ et $x$ divise $y$. 
Le prédicat $=$ a l'interprétation standard.
\end{itemize}
\end{Exo}

% On notera par $A(x)$ une formule du calcul des prédicats (éventuellement
% compliquée!) dans laquelle la variable $x$ présente des occurrences; ces
% occurrences peuvent être libres ou liées, et $A$ peut présenter des
% occurrences libres et des occurrences liées de $x$; bien entendu, il peut
% aussi n'y avoir aucune occurrence libre, ou aucune occurrence liée; enfin,
% d'autres variables peuvent aussi présenter des occurrences dans $A$. Soit
% ensuite $t$ un terme du calcul des prédicats, qui présente des
% occurrences de diverses variables (toutes libres, dans un terme,
% évidemment; un terme ne comporte pas de quantificateurs).

% On dit que ce terme $t$ est libre pour $x$ dans $A$ lorsque les
% occurrences libres de $x$ dans $A$ ne rentrent dans la portée d'aucun
% quantificateur portant sur une variable de $t$.
% \par\noindent
% Exemple: Soit la formule $A(x)=\exi x\,r(x,y)\imp\qqs y\,s(x,y,z)$
% [Cette formule présente une occurrence liée et une occurrence libre de
% $x$].

% \begin{itemize}

% \item Examinons le terme $y$ (une variable est un terme) par rapport à la
% variable $x$ dans $A$. Comme l'occurrence libre de $x$ dans $A$ (la
% seconde) entre dans la portée du quantificateur $\qqs y$, et que $y$ est
% une variable (et même la seule\ldots) du terme $y$, le terme $y$ n'est pas
% libre pour $x$ dans $A$.

% \item Examinons le terme $t=f(x,z)$ [où $f$ est un symbole opératoire,
% $t$ est bien un terme] par rapport à la variable $x$ dans $A$. Comme
% l'occurrence libre de $x$ dans $A$ n'entre pas dans la portée d'un
% quantificateur portant sur $x$ (et pour cause\ldots), ni dans celui d'un
% quantificateur portant sur $z$ (il n'y en a pas\ldots), ce terme $t$ est
% libre pour $x$ dans $A$.

% \end{itemize}
% On appelle substitution libre de la variable $x$ par le terme $t$ dans la
% formule $A$ le remplacement de $x$, dans toutes ses occurrences libres
% dans $A$ (et uniquement celles-ci\ldots) par le terme $t$, à condition que ce
% terme soit libre pour $x$ dans $A$. La nouvelle formule obtenue est notée
% $(x\mid t)A$.

% \begin{itemize}

% \item il est impossible d'effectuer la substitution libre de $x$ par $y$
% dans la formule de l'exemple ci-dessus ($y$ n'est pas libre pour $x$ dans
% $A$).

% \item il est possible d'effectuer la substitution libre de $x$ par
% $t=f(x,z)$ dans $A$, car ce terme est libre pour $x$ dans $A$. Le résultat
% est $(x\mid f(x,z))A=\exi x\,r(x,y)\imp\qqs y\,s(f(x,z),y,z)$.

% \end{itemize}
% Par convention, si $x$ ne présente pas d'occurrences libres dans $A$, la
% substitution libre de $x$ par n'importe quoi est toujours possible, et
% elle laisse la formule $A$ inchangée.

% %________________ 24.

% \subsection{Tautologies quantifiées}

% Soit $A(x)$ la formule $A$ où $x$ est une variable libre et $A(r)$ le
% résultat de  $A[r/x]$. Alors:

% \begin{itemize}

% \item Tautologie 1: $\tauto (\qqs x\,.\, A(x))\imp A(r)$
% \item Tautologie 2: $\tauto A(r)\imp (\exi x \, .\, A(x))$

% \end{itemize} 
% La première est le \og principe de particularisation\fg{} : si, pour
% toute valeur 
% de $x$, $A(x)$ est vrai, alors $A(r)$ est vrai, $r$ étant une \og
% valeur 
% particulière\fg{} de $x$. La seconde est le principe d'\og exhibition
% d'une 
% valeur particulière\fg{} : si on peut trouver une valeur $r$ pour
% laquelle 
% $A(r)$ est vraie alors on peut affirmer qu'il existe une valeur de $x$ 
% pour laquelle $A(x)$ est vraie (c'est $r$!).

% \noindent Exemples (mathématiques):

% \begin{itemize}

% \item Si tout nombre premier n'est divisible que par 1 et par lui-même,
% alors 17 (qui est un nombre premier) n'est divisible que par 1 et par 17.

% \item Puisque 2 divise 6, il existe des nombres qui sont divisibles par 2.

% \end{itemize}
% L'extrême simplicité de ces exemples ne doit pas faire oublier que le
% terme $r$ peut être bien autre chose qu'une constante, en fait, tout terme
% libre pour $x$ dans $A$.

% Soit $A(x)$ une formule répondant à la définition du paragraphe précédent
% et $B$ une formule ne contenant pas d'occurrences libres de $x$. Alors:

% \begin{itemize}

% \item Si $\tauto B\imp A(x)$, alors: $\tauto B\imp (\qqs x\,.\, A(x))$

% \item Si $\tauto A(x)\imp B$, alors: $\tauto(\exi x\,.\, A(x))\imp B$.

% \end{itemize}
% Le premier résultat est le \og principe de
% généralisation\fg{} ; il est très souvent utilisé en
% mathématiques: Si on conduit une démonstration qui a pour conclusion
% un résultat dont l'expression fait intervenir une variable $x$, et si cette
% démonstration n'a fait intervenir aucune hypothèse sur cette variable,
% alors le résultat est vrai pour toute valeur de $x$. On appelle aussi
% cette règle (il s'agira ultérieurement, en théorie de la
% démonstration, d'une règle d'inférence) la règle d'introduction du
% quantificateur universel.

% Le second est l'introduction du quantificateur existentiel. Autant le
% premier est facilement utilisé (souvent abusivement\ldots) autant le
% second 
% est malaisé à saisir. 
% %__________ 3.

% \section{Théorie de la démonstration en calcul des prédicats}

% %________________ 31.

% \subsection{Axiomes et règles d'inférence}
% Pour élaborer la théorie de la démonstration en calcul des prédicats,
% on reprend celle qui a été donnée en calcul propositionnel en ajoutant
% les axiomes et les règles d'inférence qui permettent de traiter les
% nouveaux symboles introduits (les quantificateurs).

% \begin{itemize}

% \item Nouveaux axiomes :

% \begin{itemize}

% \item Axiome 14: $(\qqs x\,  . \, A(x))\imp A(r)$

% \item Axiome 15: $A(r)\imp (\exi x\, . \, A(x))$

% \end{itemize}
% [Dans les conditions indiquées au paragraphe précédent: substitution libre
% de $x$ par $r$ dans $A$, $r$ étant libre pour $x$ dans $A$].

% \item Nouvelles règles d'inférence, avec $C$ sans occurrences libres
%   de $x$:

% \begin{itemize}

% \item $\{C\imp A(x)\}\theor C\imp\qqs x\, . \, A(x)$ [règle d'introduction de
% $\qqs$ ou règle-$\qqs$]

% \item $\{A(x)\imp C\}\theor\exi x\, . \, A(x)\imp C$ [règle d'introduction de
% $\exi$ ou règle-$\exi$].

% \end{itemize}
% \end{itemize}



% \subsection{Validité des résultats établis en calcul
% propositionnel}
% Le calcul propositionnel étant un sous-ensemble du calcul des
% prédicats, tous les théorèmes établis en calcul propositionnel demeurent
% établis en calcul des prédicats. 
% Bref, tant que l'on n'utilise pas les symboles (quantificateurs), pas les axiomes
% (14 et 15) ni les règles d'inférence (introductions de quantificateurs)
% propres au calcul des prédicats, les démonstrations et déductions du
% calcul des propositions s'étendent sans difficultés au calcul des
% prédicats.

% Il ne faudrait pas en conclure hâtivement que les règles d'inférence vraies en
% calcul propositionnel s'appliquent aussi en calcul des prédicats. 
% A titre d'exemple, on va étudier le cas du méta-théorème de la déduction.

% %________________ 33.

% \begin{Th}[méta-théorème de la déduction]
% En calcul des prédicats, on a:
% $$
% \textrm{Si } 
% (B_1,B_2,\ldots,B_{n-1}) \theor B_n\imp C
% \textrm{, alors }
% (B_1,B_2,\ldots,B_n)\theor C
% $$
% \end{Th}
% \begin{Proof}
% De 
% $(B_1,B_2,\ldots,B_{n-1}) \theor B_n\imp C$ et 
% $(B_1,B_2,\ldots,B_{n-1},B_n)$ par modus ponens on en déduit
% $C$.
% \end{Proof}

% En général, la réciproque n'est  pas vraie. 
% Cependant elle reste établie dans les cas suivants:

% \begin{itemize}

% \item 
% lorsque la déduction de $C$ est faite \og à variables
% constantes\fg{} (cette expression 
% %malheureuse, mais consacrée, 
% signifie %simplement
% que la déduction
% n'utilise aucune des 
% règles d'introduction des quantificateurs, donc est faite comme en
% calcul propositionnel).
% \item 
% lorsque les hypothèses de la déduction sont toutes des formules closes
% (c'est à dire sans variables libres).
% \end{itemize}



% \section{Le système formel \og \textit{PR}\fg{} }

% Il s'agit du système formel construit pour la formalisation  
% du calcul des prédicats. Comme pour \og \textit{LP}\fg{} , le nombre de
% symboles est 
% réduit par rapport à celui du calcul des prédicats tel qu'il a été
% décrit 
% ci-dessus, dans le but d'obtenir plus d'efficacité en \og
% démonstration automatique\fg{} .



% \subsection{Définition}

% \begin{itemize}

% \item L'alphabet $\Sigma_{\textit{PR}}$ est celui de \og
%   \textit{LP}\fg{} , auquel on adjoint: 

% \begin{itemize}

% \item le symbole de quantificateur universel
% \item des symboles de variables et d'individus (les \og constantes\fg{} )
% \item des symboles opératoires et fonctionnels

% \end{itemize}

% \item Les formules sont celles du calcul des prédicat (limitées au
% vocabulaire de \og \textit{PR}\fg{} )
% \item Les (schémas d') axiomes sont au nombre de 5:

% \begin{itemize}

% \item Axiome 1: $A\imp(B\imp A)$
% \item Axiome 2: $(A\imp(B\imp C))\imp((A\imp B)\imp(A\imp C))$
% \item Axiome 3: $(\non B\imp\non A)\imp(A\imp B)$
% \item Axiome 4: $(\qqs x\, . \, A(x)) \imp A(t)$
% \item Axiome 5: $(C\imp B(x)) \imp (C\imp \qqs x\, . \, B(x))$ [$x$ n'étant pas
% variable libre de $C$].

% \end{itemize}

% \item Il y a 2 règles d'inférence:

% \begin{itemize}

% \item Le \og modus ponens\fg{} $(A,A\imp B)\theor\ B$
% \item La généralisation $A\theor\ \qqs x\, . \, A$.

% \end{itemize}

% \end{itemize}

% %________________ 42.

% % \subsection{Calcul des prédicats égalitaire}

% % Dans de nombreuses applications, notamment mathématiques, on a besoin de
% %  l'égalité. La \og vraie\fg{} égalité, c'est à dire la capacité de
% % reconnaissance de l'identité de deux objets, n'est pas une notion de
% % logique du premier ordre (celle dont nous nous occupons ici). En effet,
% % deux objets sont identiques lorsque toute propriété qui est vraie pour
% % l'un est aussi vraie pour l'autre, et que toute propriété fausse pour
% % l'un est aussi fausse pour l'autre. Autrement dit, pour définir
% % l'égalité, il faudrait quantifier universellement un symbole de prédicat,
% % écrire une formule qui pourrait ressembler à :\par
% % \centerline{$(x=y)$ si et seulement si $\qqs p\,.\,(p(x)\eqv
% %   p(y))$.}\par\noindent 
% % Or, quantifier un symbole de prédicat n'est pas possible en calcul des
% % prédicats du premier ordre. Donc, lorsqu'on a besoin d'une égalité, on se
% % contente d'une égalité \og affaiblie\fg{} comme simple relation d'équivalence
% % (réflexive, symétrique, transitive), donc comme un prédicat
% % binaire, qu'il faudrait noter $\equiv(x,y)$ mais que l'on note $(x\equiv
% % y)$. Bien entendu, il faut ajouter les axiomes qui fixent les propriétés
% % de cette égalité, pour obtenir un calcul des prédicats égalitaire.

% % %________________ 43.

% %\subsection{Interprétations de \og \textit{PR}\fg{} }


% %________________ 44.

% \subsection{Théorème de complétude de Gödel}
% La démonstration est longue et repose sur un raisonnement par récurrence
% sur la complexité de la formule (en gros, le nombre de connecteurs ou
% quantificateurs qui interviennent dans celle-ci), après avoir démontré la
% propriété individuellement pour chaque formule de complexité 1 (un seul
% connecteur ou quantificateur). Toute la difficulté provient de la
% cardinalité (du \og nombre d'éléments\fg{} ) de l'interprétation. Le
% résultat est connu sous le nom de théorème de complétude de Gödel (1930).
% \begin{Th}[Théorèmes de complétude de Gödel] $ $
% \begin{itemize}
% \item le système formel \og \textit{PR}\fg{} est complet:
%   $$
%   \tauto B  \textrm{ si et seulement si } \theor B 
%   $$
% \item sa généralisation aussi:
%   $$
%   F\tauto B \textrm{ si et seulement si } F\theor B$$
% \end{itemize}

% \end{Th}

% \subsection{Satisfaisabilité et insatisfaisabilité}

% Soit $E$ l'interprétation de \og \textit{PR}\fg{} .

% \begin{itemize}

% \item une formule de \og \textit{PR}\fg{} est dite \emph{satisfaite} dans $E$
%   chaque fois qu'il 
% existe un ensemble de valeurs, choisies dans $E$, pour les variables libres
% qui interviennent dans cette formule tel que la proposition qui en résulte
% est \og vraie\fg{} .

% \item une formule de \og \textit{PR}\fg{} est dite \emph{valide} dans
%   $E$ si, pour tout ensemble 
% de valeurs, choisies dans $E$, pour les variables libres qui interviennent
% dans $E$, la proposition qui en résulte est vraie.

% % \item une formule de \og \textit{PR}\fg{} est \emph{universellement valide ou est une thèse
% % lorsqu'elle est valide dans toute interprétation. L'usage veut cependant
% % que l'on conserve terme de tautologie (qui devrait être réservé au calcul
% % propositionnel).

% \end{itemize}



% Soit $F$ un ensemble de formules de \og \textit{PR}\fg{} ; $F$ est dit
% \emph{satisfaisable} s'il 
% est possible de trouver une interprétation dans laquelle les formules de
% $F$ sont simultanément satisfaites. Une telle interprétation
% est appelée modèle de $F$. S'il n'est pas possible de
% trouver un modèle pour l'ensemble de formules $F$, celui-ci est dit
% \emph{insatisfaisable}, \emph{incohérent}, \emph{contradictoire}.

%  Ce sont ces notions d'insatisfaisabilité qui sont à
% l'origine des méthodes de démonstration dites de réfutation.
% Elles sont basées sur le théorème suivant.
% \begin{Th}[Théorème de contradiction]
% Soit $F$ un ensemble de formules closes et $B$ une formule close de 
% \og \textit{PR}\fg{}. Alors, $F\theor B$ si et
% seulement si $F\union\{\non B\}$ est insatisfaisable 
% \end{Th}

% Ce théorème peut être démontré à l'aide du théorème de complétude.


 \gsaut

\centerline{\x{Fin du Chapitre}}