Logique de Premier Ordre

La Logique du premier ordre LPO
La logique des propositions ne prend pas en charge la notion

d’individus, Or la plupart de nos connaissances portent sur
des individus, sur des classes d’individus, sur des relations
entre individus. Il existe un outil plus puissant qui permet
d’exprimer de telles connaissances la logique du premier
ordre : coupable (x) avec x peut être l’individu Sophie ou
Jean ou autre.
L’idée remonte aux grecs anciens, et se formule ainsi : dans
une phrase , le verbe établit une relation entre son sujet et
ses compléments. La proposition jean prend son manteau
s’exprime prend(jean, manteau). Nous allons décrire les
trois volets de la LPO.
1- Langage
 = { ,}  variables{x, y, …}  Symboles de fonction {f, g,

…}  Symboles de prédicats {f, p, q,…}.
A chaque fonction et à chaque prédicat est associé un entier
naturel, son arité ; f est le prédicat d’arité 0.
Formule est l’axiome de ce langage.
Les réécritures sont :
Formule  pred0 / pred1(terme) / pred2(terme, terme) /…/
(formule  formule)/ (var)(formule).
Terme  fonct0 / fonct1(terme) / fonct2(terme, terme) / …/ var
Var  x / y /…
Pour chaque i, predi (respectivement foncti ) correspond au
symbole de prédicat (fonction) d’arité i
1- Langage
{v,  , , , }: mêmes règles données pour la logique
propositionnelle.
V désigne la formule (f  f)
x,  x désigne la formule (x  f)
x,y, x  y ssi ((x  y )  y)
x,y, x  y ssi ((x  (y  f))  f)
x,y, x  y ssi (((x  y)  ((y  x)  f))  f)
Pour  / x et f , (x) (f)  (x) (f)
Notons enfin que les fonctions d’arité 0 sont également appelées
constantes
Parmi les symboles de variables, il importe de faire la distinction
entre ceux qui représentent des variables libres et liées.
2- Système de déduction
• Il y a une infinité d’axiomes dans cette logique. On les
représente par des schémas d’axiomes, i.e., les axiomes sont
obtenus par substitution (la règle R1 de la logique
propositionnelle) à partir des 5 formules ci-dessous :
• (A1), (A2), (A3) : les axiomes correspondants de la logique
propositionnelle
Plus
• (A4) ((  x) ((a  b))  (a  (x) (b)))
• (A5) ((  x) (a)  b) où b est une formule obtenue en
substituant dans a toutes les occurrences de la variable x par
une autre variable y ou par une constante.
Lemme1 : pour toute formule a et toute variable x,

((  x) (a)  a) est un axiome.
Preuve : on obtient la formule cherchée à partir de (A5) :
((  x) (a)  b) ; 
2- Système de déduction
Les règles d’inférence sont :
(R2) [modus ponens] : comme en logique propositionnelle.

(R4) [généralisation] : si a est une formule, R4(a) est l’ensemble
des formules ayant la forme (x) (a) où x est un symbole de
variable.
Lemme 2 : les théorèmes de la logique propositionnelle et les
formules du premier ordre obtenues par R1 appliquées à ces
théorèmes sont des théorèmes de la logique du premier ordre.
3- Règles de valuation
En logique du premier ordre, l’ensemble V des valeurs de vérité
comprend les mêmes symboles vrai et faux. L’évaluation (dans
V) d’une formule du langage s’effectue dans un modèle.
Celui-ci se compose d’un domaine, d’une interprétation, et
d’une assignation
• Un domaine est un ensemble D non vide, absolument
quelconque.
• Une interprétation fait correspondre à chaque symbole de

prédicat predn( respectivement fonction fonctn ) d’arité n une
application pn ( respectivement fn) de Dn dans D(V);
le prédicat f s’interpréte comme la valeur faux.
• Une assignation fait correspondre à chaque symbole de

variable un élément de D
3- Règles de valuation
Comme en logique propositionnelle, les formules dont la valeur
est vrai quel que soit le modèle sont appelées tautologies. Les
règles de valuation étant compatibles, les tautologies du calcul
propositionnel sont des tautologies du premier ordre.
Plus généralement, tout théorème est une tautologie, c’est-à-dire
que le système déductif à la propriété de correction.
La propriété réciproque, la complétude, est beaucoup plus

délicate à démontrer. La preuve a été apportée par K Gödel en
1930.
4- Connaissances du premier ordre
Pour de nombreux auteurs, le langage du premier ordre est le

langage idéal pour la représentation des connaissances : ‘’ si
l’on voit l’univers comme composé d’entité stables, sur
lesquels on dispose d’une connaissance complète, alors la
logique du premier ordre est un excellent système de
représentation.
Mais la notion d’assertion ‘’généralement’’ vraie n’y a toujours
pas sa place.
Exemple sur les nautiles
Les nautiles sont des céphalopodes;
Les céphalopodes sont des mollusques;
Les mollusques ont généralement une coquille;
Les céphalopodes n’en ont généralement pas;
Les nautiles en ont une.
a est un nautile,
b est un céphalopode,
c est un mollusque.
( x) (naut(x)  céph(x));
( x) ((céph(x)  mol(x));
( x)((mol(x) (céph(x) naut(x))  a-coq(x)));
( x) ((céph(x) naut(x)  a-coq(x)));
( x)((naut(x)  a-coq(x))); naut(a); céph(b); mol(c);
Comme précédemment, on peut conclure a-coq(a), mais il existe
des modèles satisfaisant toutes ces formules et a-coq(b)
[il suffit de supposer que b est un naut?]; de même pour a-
coq(c).
Les conséquences attendues ne sont toujours pas dérivables. Le
problème vient de ce que l’on n’a pas de connaissance
complète sur b et c : on ne sait pas, par exemple, si b est ou
non un nautile.
5- Décidabilité
On dit qu’une logique est décidable s’il existe un
procédé de calcul qui pour toute formule, indique en
un temps fini s’il s’agit ou non d’un théorème de cette
logique.
La logique du premier ordre n’est que semi-décidable. Il
existe un algorithme qui, si une formule est
démontrable, le dira en un temps fini, mais qu’on ne
peut borner à priori. Il n’existe en revanche pas
d’algorithme permettant, pour toute formule, de
déterminer en un temps fini qu’elle n’est pas
démontrable.

Logique de Premier Ordre

Transféré par

Droits d'auteur :

Formats disponibles

Logique de Premier Ordre

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Logique de Premier Ordre

Transféré par

Droits d'auteur :

Formats disponibles

La Logique du premier ordre LPO

La logique des propositions ne prend pas en charge la notion

 = { ,}  variables{x, y, …}  Symboles de fonction {f, g,

Lemme1 : pour toute formule a et toute variable x,

(R2) [modus ponens] : comme en logique propositionnelle.

• Une interprétation fait correspondre à chaque symbole de

• Une assignation fait correspondre à chaque symbole de

La propriété réciproque, la complétude, est beaucoup plus

Pour de nombreux auteurs, le langage du premier ordre est le

Vous aimerez peut-être aussi