Définitions
Définition : Prédicats
Un prédicat est une propriété ou relation qui porte sur un ou plusieurs éléments d'un domaine D. C'est une fonction de D dans {T, F}.
Le problème précédent peut être traduit de manière adéquate en logique des prédicats :
Hypothèse 1 : Quelque soit x appartenant au domaine D, si x est un homme, alors x est mortel (∀x (H(x) → M(x))) ;
Hypothèse 2 : Socrate à la propriété d'être un homme (H(Socrate)) ;
Conclusion : Socrate à la propriété d'être mortel (M(Socrate)).
Dans cet exemple, nous avons utilisé deux prédicats (H et M), une constante (Socrate), une variable (x) et le quantificateur universel (∀). Comme nous le plus tard, ce raisonnement, ainsi formalisé en logique des prédicats, sera valide.
Définition : Formule
Avant de définir le langage du calcul des prédicats, l'ensemble des formules bien formées (correctement écrites) nous allons d'abord préciser :
L'alphabet du langage du calcul des prédicats est composé de :
x1, x2 : les variables,
a1, a2 : les constantes,
P1, P2 : les prédicats,
f1, f2 : les fonctions,
￢, → : les connecteurs,
Ɐ, ⱻ les quantificateurs,
Les termes du calcul des prédicats (CP.) sont définis comme suit :
Les variables et les constantes sont des termes.
Si fi est une fonction à n arguments du CP. et t1, t2,... tn sont des termes alors fi (t1, t2,... tn) est un terme du CP.
L'ensemble des termes est engendré par les clauses (a) et (b).
Exemple : xi, f1 (xi), g2(x, f1 (xi)) sont des termes.
Définition : Formule atomique
Une formule atomique du CP. est définie par :
Si Pi est un prédicat, une fonction définie d'un domaine vers l'ensemble
et t1, t2,... tn sont des termes alors Pi (t1, t2,... tn ) est une formule atomique.
Définition : Formule bien formée
Les formules bien formées (ou formule tout simplement) sont définies par :
Chaque formule atomique est une formule bien formée.
Si A, B sont des formules bien formées du CP. alors ﹁A, (A → B), (Ɐx) A, et (ⱻx) A sont des formules bien formées.
L'ensemble de toutes les formules bien formées est engendré par les clauses (1) et (2).
Définition : Variables liées, variables libres
Dans la formule ⱯxA la formule A est dite champ du quantificateur Ɐ. La variable x est dite variable quantifiée par le quantificateur universel Ɐ. Les positions occupées par la variable x dans la formule A sont appelées occurrences de x. Dans la formule précédente F la variable x possède deux occurrences.
Une occurrence d'une variable x dans une formule est dite liée si elle possède une occurrence dans le champ d'un quantificateur Ɐ (ou ⱻ) dans cette formule. Si une occurrence d'une variable n'est pas liée, elle est libre.
