La logique avec

prédicats du première ordre

1
Introduction
◼ La logique avec prédicats du premier ordre a été
développée pour exprimer des raisonnements sur
des objets complexes ou classes d'objets et sur les
relations qui existent entre eux
◼ Cette généralisation est effectuée par l'introduction
de prédicats au lieu de propositions, à l'aide des
fonctions, des variables et des quantificateurs

2
 La syntaxe de la logique avec
prédicats du premier ordre
◼ L'alphabet de la logique avec prédicats du premier
ordre contient des symboles pour représenter des
constantes (a, b, c,…), des variables (x, y, z,…), des
fonctions (f, g, h,…), des prédicats (P, Q, R,…), des
connecteurs logiques (~,  , , →, ) et des
quantificateurs logiques (, )
◼ Les prédicats sont des fonctions logiques avec des
nombreux arguments. Les arguments des prédicats
sont appelés termes

3
Définition
◼ Soit D un domaine. Un terme est défini
par:
◼ 1. Une constante est un terme ayant une
valeur dans le domaine D
◼ 2. Une variable est un terme qui peut
recevoir des valeurs différentes du
domaine D

4
Définition
◼ 3. Si f est une fonction avec n arguments
(f:Dn→D) et t1,…,tn sont des termes, alors
f(t1,…,tn) est un terme
◼ 4. Tous les termes sont générés par
l'application des règles 1, 2 et 3

5
Définitions
◼ Un prédicat d'arité n est une fonction P
avec n arguments, ayant les valeurs vraie
ou faux P:Dn→{ v, f }
◼ Un prédicat d'arité 0 est une proposition,
aussi appelé prédicat constante

6
Définitions
◼ Si P est un prédicat d'arité n et t1,…,tn sont
des termes, alors P(t1,…,tn) est appelé
atome ou formule atomique
◼ Un littéral est un atome ou un atome nié

7
 Définition
◼ Une formule bien formée est définie par:
◼ 1. Un atome est une formule bien formée
◼ 2. Si P est une formule bien formée, alors ~P,
(x)P(x), (x)P(x) sont des formules bien
formées
◼ 3. Si P et Q sont des formules bien formées,
alors PQ, PQ, P→Q et PQ sont des
formules bien formés
◼ 4. Une formule bien formée est générée par
l'application d'un nombre fini les règles 8
9
Exemple
◼ (x)(y)(z)(Pere(x,y)  Pere(y,z) →
Grandpere(x,z))
◼ Formule bien formée
◼ Pere(x,y), Pere(y,z) et Grandpere(x,z) sont
des littéraux
◼ x, y et z sont des variables

10
Exemple
◼ (x)(y)(Egal(y,f(x))  (z)(Egal(z,f(x)) →
Egal(y,z)))
◼ Formule bien formée
◼ Egal(y,f(x)) est un littéral
◼ f(x) est une fonction
◼ x, y et z sont des variables

11
Exemple
◼ (P)(P(x) → Q(x))
◼ PAS une formule bien formée
◼ Les quantificateurs NE peuvent pas être
appliqués aux prédicats
◼ Ceci n'est possible que dans la logique de
prédicats du second ordre

12
Exemple
◼ (x)(y)Marriage(Homme(x),Femme(y))
◼ PAS une formule bien formée
◼ Les arguments des prédicats NE peuvent
pas être, à leur tour, des prédicats

13
 Définition
◼ Une formule bien formée est dans la forme
normale conjonctive si la formule est de la
forme
◼ F1F2 … Fn
◼ où Fi i=1, n est une formule composée d'une
disjonction de littéraux

14
Exemple
◼ (~P  Q  R)  (~P  ~Q)
◼ Formule dans la forme normale
conjonctive

15
Définition
◼ Une formule bien formée est dans la
forme normale disjonctive si la formule
est de la forme
◼ F1F2  …  Fn
◼ où Fi i=1, n est une formule composée
d'une conjonction de littéraux

16
Exemple
◼ (P  Q  R)  (~P  ~Q)
◼ Formule dans la forme normale disjonctive

17
La sémantique de la logique avec
prédicats du premier ordre
◼ La sémantique peut être établie en fonction du
domaine de l'interprétation de la formule
◼ Le domaine d'interprétation est l'ensemble de
tous les objets à partir de laquelle sont
sélectionnés les constantes, les variables et
qui établit le domaine de définition et le
domaine des valeurs pour les fonctions des
formules

18
Définition
◼ L'interprétation d'une formule F consiste à
établir un domaine des valeurs non-vide et
une affectation des valeurs pour chaque
constante, fonction et prédicat de F:
◼ 1. Pour chaque constante il est associé un
élément de D

19
Définition
◼ 2. Pour chaque fonction f, d'arité n, est
associée une correspondance Dn→D où
Dn={(x1,…,xn) | x1D,…,xnD}
◼ 3. A chaque prédicat d'arité n est associé une
correspondance P:Dn→{v, f}

20
Exemple
◼ Considérez la formule bien formée
suivante:
◼ (x)(((A(a,x)  B(f(x)))  C(x)) → D(x))
◼ Domaine d'interprétation D = {1,2}
◼ Interprétation I

21
Exemple
◼ Pour établir la valeur de vérité de la
formule, nous considérons:
◼x=1 ((v  f)  v) → f faux
◼x=2 ((f  v)  f) → v vrai
◼ Parce que la formule n'est pas vraie pour
chaque x du domaine d'interprétation D,
l'expression a la valeur de vérité faux

22
Exemple
◼ Considérez les axiomes des nombres
naturels
◼ 1) Pour chaque nombre naturel, il existe
un successeur immédiat unique
◼ 2) Il n'y a pas de nombre naturel dont 0 est
son successeur immédiat
◼ 3) Pour tout nombre naturel différent de 0,
il existe un prédécesseur immédiat unique
23
Exemple
◼ s(x) successeur immédiat de x
◼ p(x) prédécesseur immédiat de x
◼ Egal(x,y) x est égal à y

24
Traduction dans la logique des
prédicats du premier ordre
◼ (A1) (x)(y)(Egal(y,s(x)) 
(z)(Egal(z,s(x)) → Egal(y,z)))
◼ (A2) ~((x)(Egal(0,s(x))))
◼ (A3) (x)(~Egal(x,0)  ((y)(Egal(y,p(x)) 
(z)(Egal(z,p(x)) → Egal(y,z)))))

25
26
27
Règles d'inférence
◼ Les règles d'inférence sintactiques de la
logique propositionnelle peut être
généralisée dans le cas de la logique avec
prédicats du premier ordre
◼ Modus Ponens
P(a)
(x) (P(x) → Q(x))
_____
Q(a)
28
Observations
◼ Il est possible de remplacer x par a, car
P(x)→Q(x) est vrai dans toutes les
interprétations
◼ La règle de la substitution est plus
complexe dans la logique avec prédicats
du premier ordre
◼ Les règles d'inférence précédentes sont
toujours valides

29
Observations
◼ Aussi, on utilise des règles d'inférence
non-déductive - les résultats obtenus ne
sont pas toujours vrai
◼ Ces règles peuvent être utilisés dans de
nombreux cas, mais ils ne garantir pas
l'exactitude du résultat

30
L'inférence abductive
◼ Basé sur les connaissances causales
utilisées pour expliquer ou justifier une
conclusion, qui peut-être non valide
Q(a)
(x) (P(x) → Q(x))
_____
P(a)

31
L'inférence inductive
◼ Basé sur l'idée qu'une proprieté qui est
vraie pour un sous-ensemble d'objets d'un
ensemble est vraie pour tous les exemples
de cette classe
P(a1), P(a2),…,P(an)
________________
(x) P(x)

32
L'inférence analogique
◼ C'est une forme d'inférence fondée sur
l'expérience et est basé sur l'idée que des
situations ou des entités qui ont la tendance
d’être similaires sur certains aspects sont
similaires en général

33
Observations
◼ Les dernière trois règles d'inférence
représentent des manières de simuler le
raisonnement de sens commun
◼ Ces règles d'inférence sont utilisées dans
les programmes d'apprentissage
automatique

34
Observations
◼ Dans la logique propositionnelle il y a
toujours des procédures efficaces qui
permet d'établir si une formule est
théorème ou pas
◼ Ainsi, la demonstration des théorèmes
dans la logique propositionnelle est
décidable

35
Observations
◼ Dans le cas de la logique avec prédicats
du premier ordre, il est garanti l'existence
d'une procédure pour demontrer qu'une
formule est un théorème si cette formule
est effectivement un théorème
◼ Cette procédure n'est pas garantie de
s'arrêter si la formule à demontrer n'est
pas un théorème
◼ Ainsi, la démonstration des théorèmes
dans la logique avec prédicats du premier
ordre est semi-décidable 36
La démonstration des théorèmes en
utilisant le principe de la résolution
◼ Le principe de la résolution est un moyen
efficace pour démontrer les théorèmes
◼ La résolution est une méthode d'inférence
sintactique qui, appliquée à plusieurs
reprises à un ensemble de formules dans
la forme standard, détermine si l'ensemble
des formules est inconsistant

37
 Observations
◼ Pour démontrer que la formule C est une
conséquence logique des formules P1, P2,…,
Pn il est démontré que P1  P2  …  Pn  ~C
est une formule inconsistante
◼ Le principe de la résolution est appliqué sur une
forme standard des formules, appelé la forme
clausale

38
Définitions
◼ Une clause est une disjonction de littéraux
◼ Une clause de base est une clause sans
variables
◼ Une clause de Horn est une clause qui
contient au plus un littéral positif
◼ Une clause vide est une clause sans
aucun littéral; une clause vide est notée 

39
Exemples
◼ P(x,y)  ~Q(x,f(y))  R(z) est une clause
◼ Dans une clause, toutes les variables sont
implicitement quantifiées universellement
◼ ~P(a,y)  ~Q(x,z)  P(x,y) est une clause
de Horn
◼ P(a,b)  Q(c,d)  R(a) est une clause de
base

40
La transformation d'une formule bien
formée dans la forme clausale
◼ Étape 1 – Tous les connecteurs d'implication
et d'équivalence sont éliminés
◼ Étape 2 - Toutes les négations de la formule
sont déplacés, tels qu'ils apparaissent avant
les atomes

41
Exemple
◼ La formule:
◼ ~((x)P(x) → (y)Q(y))
◼ se transforme successivement en:
◼ ~(~((x)P(x))  (y)Q(y))
◼ (x)P(x)  ~((y)Q(y))
◼ (x)P(x)  (y)~Q(y)

42
La transformation d'une formule
bien formée dans la forme clausale
◼ Étape 3 - Les variables sont renommés,
s'il est nécessaire, telle que tous les
quantificateurs se référrent à des variables
différentes

43
Exemple
◼ Dans la formule:
◼ (x)(P(x) → (x)Q(x))
◼ la deuxième variable x est renommée,
référencée par le quantificateur existentiel
(x) et la formule est obtenue:
◼ (x)(P(x) → (y)Q(y))

44
 La transformation d'une formule bien
formée dans la forme clausale
◼ Étape 4 - Tous les quantificateurs existentiels
sont éliminés de la formule par un processus de
substitution
 Étape 4.1 - Si le quantificateur plus à gauche est un
quantificateur existentiel, toutes les occurrences de
la variable sont remplacées par une constante
arbitraire qui n'apparaît pas dans l'expression et le
quantificateur est éliminé. Ce processus est
appliqué pour tous les quantificateurs existentiels
qui ne sont pas précédées par des quantificateurs
universels, à l'aide des constantes différentes 45
 La transformation d'une formule
bien formée dans la forme clausale
 Étape 4.2 - Pour chaque quantificateur existentiel, qui
est précédé d'un ou plusieurs quantificateurs
universels, toutes les occurrences de la variable sont
remplacées par une fonction qui n'apparaît pas dans la
formule et qui a comme arguments toutes les variables
quantifiées universels qui précèdent le quantificateur
existentiel. Le quantificateur existentiel est éliminé. Le
processus est répété pour chaque quantificateur
existentiel, à l'aide d'un autre symbole de fonction et en
choisissant comme variables de fonction les arguments
qui correspondent à toutes les variables quantifiées
universels qui précèdent le quantificateur existentiel
46
Exemple
◼ L’expression:
◼ (u)(v)(x)(y)(P(f(u),v,x,y)  Q(u,v,y))
◼ se transforme en:
◼ (v)(x)(P(f(a),v,x,g(v,x))  Q(a,v,g(v,x))

47
La transformation d'une formule
bien formée dans la forme clausale
◼ Étape 5 - Tous les quantificateurs universels
sont déplacés vers la gauche de l'expression
et l'expression est transformée dans la forme
normale conjonctive
◼ Étape 6 - Tous les quantificateurs universels
sont éliminés, parce qu'ils sont implicitement
retenus dans la forme clausale et les
conjonctions sont éliminées de la forme
normale conjonctive
48
Observations
◼ Par ce processus est obtenu un ensemble
de formules, appelées clauses
◼ L'ensemble des clauses obtenu n'est pas
équivalent à la formule originale, mais la
réalisation de la formule est maintenue
◼ L'ensemble des clauses est réalisable ou
inconsistente, respectivement, si et
seulement si la formule originale est
réalisable ou inconsistente,
respectivement
49