Calcul des prédicats

Motivations

Nous allons maintenant généraliser les langages propositionels et définir ainsi des langages prédicatifs. Ceci nous permettra d'exprimer des formules correspondants à des énoncés utilisant des expressions comme «pour tout» et «il existe». Le but final est d'écrire en langage formel des raisonnements comme:

1. Tout les hommes sont mortels,
2. Socrate est un homme,
3. donc, Socrate est mortel.

Nous allons donc introduire des formules où apparaissent une ou plusieurs variables. Ceci nous permettra d'exprimer formellement des choses comme: «$x$ est un nombre entier». Dans cette expression, $x$ est une variable, et l'expression peut être vrai ou fausse suivant la valeur de $x$. On va aussi introduire des symboles, que l'on va appeler des constantes, qui seront analogues aux variables si ce n'est qu'ils ont une «valeur» fixée. Les variables et les constantes seront aussi appelés des termes.

Comme on généralise les langages propositionnels, on retrouve les symboles propositionels dans les langages prédicatifs. On voudrait ensuite ajouter des analogues aux propositions, mais qui puisse dépendre d'un certain nombre $n$ de termes, les symboles correspondants seront appelés symboles prédicatifs d'arité $n$. Puisqu'une proposition ne dépend d'aucun terme, un symbole propositionnel peut être vu comme un symbole prédicatif d'arité zéro.

On peut aussi imaginer qu'un terme puisse dépendre d'un certain nombre $n$ d'autre terme. Pour cela, on va introduire des symboles appelés symboles fonctionnels d'arité $n$.

Quantificateurs existentiels et universels

Les différents connecteurs vu en logique propositionnelle restent tout à fait d'actualité. Mais pour le calcul des prédicats, nous devons introduire deux nouveaux symboles logiques: ce sont des quantificateurs.

Le quantificateur existentiel

Ce quantificateur signifie: «il existe» ou plus précisément: «il existe au moins un» et est noté $\exists$. On peut écrire:

Et on doit comprendre: «il existe au moins un $x$ tel que $A$ soit vrai».

On rencontre parfois en mathématique des expressions du type:

Et on doit comprendre: «il existe un et un seul $x$ tel que $A$ soit vrai». On ne va cependant pas utiliser cette écriture en logique.

Le quantificateur universel

Ce quantificateur signifie «quelque soit» et est noté $\forall$. On peut écrire:

Et on doit comprendre: «quelque soit $x$, $A$ est vrai».

Alphabet et syntaxe

Le langage de la logique du premier ordre est constitué des ensembles suivants:

1. un ensemble éventuellement infini de symboles propositionnels: $p,q,r,s,...$,
2. un ensemble éventuellement infini de symboles prédicatifs d'arité $n$ ($n$ est entier strictement positif): $p^1,q^1,r^1,...,p^2,q^2,r^2,...$,
3. un ensemble éventuellement infini de symboles fonctionnels d'arité $n$ ($n$ est entier strictement positif): $f^1,g^1,h^1,...,f^2,g^2,h^2,...$,
4. un ensemble infini de symboles appelés variables: $x,y,z,...$,
5. un ensemble infini de symboles appelés constantes: $a,b,c,...$,
6. l'ensemble des symboles logiques: $\neg ,\vee ,\wedge ,\Rightarrow ,\iff ,\forall ,\exists$
7. et les parenthèse: $(,)$.

Il reste à définir la syntaxe. Il faut rappeler que si pour le cas la logique des propositions on avait uniquement des formules, on a deux notions distinctes en logique des prédicats: les formules et les termes.

L'ensemble des termes est le plus petit ensemble de mots construits sur l'alphabet de la logique des prédicats tel que:

1. toute variable est un terme,
2. toute constante est un terme,
3. si $T_1,T_2,...,T_n$ sont des termes, alors si $F$ est un symbole fonctionnel d'arité $n$, $F{T}_1{T}_2...T_n$ est un terme.

L'ensemble des formules est le plus petit ensemble de mots construits sur l'alphabet de la logique des prédicats tel que:

1. toute proposition est une formule,
2. si $T_1,T_2,...,T_n$ sont des termes, alors si $P^n$ est un prédicat d'arité $n$, $P^n{T}_1{T}_2...T_n$ est une formule,
3. si $A$ est une formule, alors $\neg A$ est une formule,
4. si $A$ et $B$ sont des formules, alors $(A\vee B)$ est une formule,
5. si $A$ et $B$ sont des formules, alors $(A\wedge B)$ est une formule,
6. si $A$ et $B$ sont des formules, alors $(A\Rightarrow B)$ est une formule,
7. si $A$ et $B$ sont des formules, alors $(A\iff B)$ est une formule,
8. Si A est une formule et $X$ est une variable, $\forall XA$ est une formule,
9. Si A est une formule et $X$ est une variable, $\exists XA$ est une formule.

Énoncés des langages prédicatifs

Dans les langages propositionnels, nous n'avons pas fait de distinctions entre les formules et les énoncés. Nous allons maintenant en faire une, il existera donc des formules qui ne sont pas des énoncés. On commence par définir la notion de sous-formules:

L'interêt de cette définition est que la valeur de vérité d'un énoncé est ainsi indépendante de toute variable. Si on remplace donc, dans un énoncé, une variable par une constante, cela n'a de sens que si il y a une occurrence libre de cette variable dans l'énoncé. On peut exprimer cette idée de façon plus générale, en remplaçant une variable par un terme dans lequel ne figure aucune variable, un tel terme sera appelé terme clos. Intuitivement, un terme clos est un «terme constant». On va écrire, si $A$ est une formule (pas forcément un énoncé) et $T$ un terme clos:

la formule obtenue en remplaçant $X$ par $T$ dans $A$, si $X$ est une constante, et la formule obtenue en remplaçant les occurrences libre de $X$ par $T$ dans $A$, si $X$ est une variable.