Logique des prédicats

Damien Nouvel

Damien Nouvel (INaLCO) Logique des prédicats 1

 Histoire et définitions

Plan

1. Histoire et définitions

2. Manipulation de formules

Damien Nouvel (INaLCO) Logique des prédicats 2

 Histoire et définitions

Propositions vs prédicats

§ Avantages et inconvénients la logique des propositions

Damien Nouvel (INaLCO) Logique des prédicats 3

 Histoire et définitions

Propositions vs prédicats

§ Avantages et inconvénients la logique des propositions

+ Formalisation logique solide
+ Possibilité de démonstrations
+ Monde clos

Damien Nouvel (INaLCO) Logique des prédicats 3

 Histoire et définitions

Propositions vs prédicats

§ Avantages et inconvénients la logique des propositions

+ Formalisation logique solide
+ Possibilité de démonstrations
+ Monde clos
- Pas de fonctions
- Pas de catégories
- Pas de formules génériques

Damien Nouvel (INaLCO) Logique des prédicats 3

 Histoire et définitions

Propositions vs prédicats

§ Avantages et inconvénients la logique des propositions

+ Formalisation logique solide
+ Possibilité de démonstrations
+ Monde clos
- Pas de fonctions
- Pas de catégories
- Pas de formules génériques
§ Exemple
• Jean est le père de Jacques et Alain, et Roger et le père de Tom.
• On sait que le père d’un père s’appelle un grand-père.
• Qui est le grand-père de Tom ?

Damien Nouvel (INaLCO) Logique des prédicats 3

 Histoire et définitions

Propositions vs prédicats

§ Avantages et inconvénients la logique des propositions

+ Formalisation logique solide
+ Possibilité de démonstrations
+ Monde clos
- Pas de fonctions
- Pas de catégories
- Pas de formules génériques
§ Exemple
• Jean est le père de Jacques et Alain, et Roger et le père de Tom.
• On sait que le père d’un père s’appelle un grand-père.
• Qui est le grand-père de Tom ?
ñ Raisonnement logique, évident pour un humain
ñ Impossible à formuler correctement en logique des propositions

Damien Nouvel (INaLCO) Logique des prédicats 3

 Histoire et définitions

Propositions vs prédicats

§ Avantages et inconvénients la logique des propositions

+ Formalisation logique solide
+ Possibilité de démonstrations
+ Monde clos
- Pas de fonctions
- Pas de catégories
- Pas de formules génériques
§ Exemple
• Jean est le père de Jacques et Alain, et Roger et le père de Tom.
• On sait que le père d’un père s’appelle un grand-père.
• Qui est le grand-père de Tom ?
ñ Raisonnement logique, évident pour un humain
ñ Impossible à formuler correctement en logique des propositions
ñ Logique des prédicats étend la logique des propositions
Damien Nouvel (INaLCO) Logique des prédicats 3
 Histoire et définitions

Quantité et qualité des formules

§ On peut qualifier les propositions selon

Damien Nouvel (INaLCO) Logique des prédicats 4

 Histoire et définitions

Quantité et qualité des formules

§ On peut qualifier les propositions selon
• Leur quantité : universelle vs particulière

Damien Nouvel (INaLCO) Logique des prédicats 4

 Histoire et définitions

Quantité et qualité des formules

§ On peut qualifier les propositions selon
• Leur quantité : universelle vs particulière
• Extension (ou dénotation)
ñ Ensemble d’individus dans le dans le domaine du discours
ñ Par ex. : Homme Ñ Damien _ Pierre _ Paul _ Jacques . . .

Damien Nouvel (INaLCO) Logique des prédicats 4

 Histoire et définitions

Quantité et qualité des formules

§ On peut qualifier les propositions selon
• Leur quantité : universelle vs particulière
• Extension (ou dénotation)
ñ Ensemble d’individus dans le dans le domaine du discours
ñ Par ex. : Homme Ñ Damien _ Pierre _ Paul _ Jacques . . .
• Compréhension (ou intention)
ñ Ensemble de caractères
ñ Par ex. : Hommepx q Ñ Humainpx q ^ Malepx q

Damien Nouvel (INaLCO) Logique des prédicats 4

 Histoire et définitions

Quantité et qualité des formules

§ On peut qualifier les propositions selon
• Leur quantité : universelle vs particulière
• Extension (ou dénotation)
ñ Ensemble d’individus dans le dans le domaine du discours
ñ Par ex. : Homme Ñ Damien _ Pierre _ Paul _ Jacques . . .
• Compréhension (ou intention)
ñ Ensemble de caractères
ñ Par ex. : Hommepx q Ñ Humainpx q ^ Malepx q
• Leur qualité : affirmative ou négative

Carré logique (Aristote)

Damien Nouvel (INaLCO) Logique des prédicats 4
 Histoire et définitions

Alphabet

§ Élements pour la logique des prédicats :

Damien Nouvel (INaLCO) Logique des prédicats 5

 Histoire et définitions

Alphabet

§ Élements pour la logique des prédicats :

• Variables et constantes
• V “ x , y , z et C “ a, b, c , Pierre, Paul , Jacques . . .

Damien Nouvel (INaLCO) Logique des prédicats 5

 Histoire et définitions

Alphabet

§ Élements pour la logique des prédicats :

• Variables et constantes
• V “ x , y , z et C “ a, b, c , Pierre, Paul , Jacques . . .
• Négation et connecteurs logiques
• , ^, _, Ñ, Ø

Damien Nouvel (INaLCO) Logique des prédicats 5

 Histoire et définitions

Alphabet

§ Élements pour la logique des prédicats :

• Variables et constantes
• V “ x , y , z et C “ a, b, c , Pierre, Paul , Jacques . . .
• Négation et connecteurs logiques
• , ^, _, Ñ, Ø
• Prédicats
• P px q, Q px , z q, mariespx , y q, perepx , y q, cousinpx , y q
• Application dans les valeurs de vérités

Damien Nouvel (INaLCO) Logique des prédicats 5

 Histoire et définitions

Alphabet

§ Élements pour la logique des prédicats :

• Variables et constantes
• V “ x , y , z et C “ a, b, c , Pierre, Paul , Jacques . . .
• Négation et connecteurs logiques
• , ^, _, Ñ, Ø
• Prédicats
• P px q, Q px , z q, mariespx , y q, perepx , y q, cousinpx , y q
• Application dans les valeurs de vérités
• Fonctions
• f px q, g px , y q, mari px q, perepx q
• Application dans le domaine

Damien Nouvel (INaLCO) Logique des prédicats 5

 Histoire et définitions

Alphabet

§ Élements pour la logique des prédicats :

• Variables et constantes
• V “ x , y , z et C “ a, b, c , Pierre, Paul , Jacques . . .
• Négation et connecteurs logiques
• , ^, _, Ñ, Ø
• Prédicats
• P px q, Q px , z q, mariespx , y q, perepx , y q, cousinpx , y q
• Application dans les valeurs de vérités
• Fonctions
• f px q, g px , y q, mari px q, perepx q
• Application dans le domaine
• Quantificateurs
• @ (universel) et D (existentiel)
• Opérateurs unaires sur les variables, ayant une portée

Damien Nouvel (INaLCO) Logique des prédicats 5

 Histoire et définitions

Alphabet

§ Élements pour la logique des prédicats :

• Variables et constantes
• V “ x , y , z et C “ a, b, c , Pierre, Paul , Jacques . . .
• Négation et connecteurs logiques
• , ^, _, Ñ, Ø
• Prédicats
• P px q, Q px , z q, mariespx , y q, perepx , y q, cousinpx , y q
• Application dans les valeurs de vérités
• Fonctions
• f px q, g px , y q, mari px q, perepx q
• Application dans le domaine
• Quantificateurs
• @ (universel) et D (existentiel)
• Opérateurs unaires sur les variables, ayant une portée
ñ Exemple de formule : @x , Dy , y ă x
Damien Nouvel (INaLCO) Logique des prédicats 5
 Histoire et définitions

Définitions
§ Termes
• Toute variable
• Toute fonction f px , y , z q si x, y et z sont des termes

Damien Nouvel (INaLCO) Logique des prédicats 6

 Histoire et définitions

Définitions
§ Termes
• Toute variable
• Toute fonction f px , y , z q si x, y et z sont des termes
§ Formule atomique
• Si P est un prédicat à n arguments et x1 , x2 , . . . xn sont des termes,
alors P px1 , x2 , . . . xn q est une formule atomatique

Damien Nouvel (INaLCO) Logique des prédicats 6

 Histoire et définitions

Définitions
§ Termes
• Toute variable
• Toute fonction f px , y , z q si x, y et z sont des termes
§ Formule atomique
• Si P est un prédicat à n arguments et x1 , x2 , . . . xn sont des termes,
alors P px1 , x2 , . . . xn q est une formule atomatique
§ Formule bien formée
• Comme pour les propositions pour , ^, _, Ñ, Ø, pq
• Si une formule est atomique elle est bien formée
• Si Q est un quantificateur, x une variable et F une formule bien
formée, alors QxF est également bien formée

Damien Nouvel (INaLCO) Logique des prédicats 6

 Histoire et définitions

Définitions
§ Termes
• Toute variable
• Toute fonction f px , y , z q si x, y et z sont des termes
§ Formule atomique
• Si P est un prédicat à n arguments et x1 , x2 , . . . xn sont des termes,
alors P px1 , x2 , . . . xn q est une formule atomatique
§ Formule bien formée
• Comme pour les propositions pour , ^, _, Ñ, Ø, pq
• Si une formule est atomique elle est bien formée
• Si Q est un quantificateur, x une variable et F une formule bien
formée, alors QxF est également bien formée
§ Portée des quantificateurs
• Si Q est un quantificateur, x une variable et F une formule bien
formée, alors la portée de Qx est F
ñ Exemple : P px q ^ Dx pP px , y q ^ @y Q px , y q _ R px , y qq
Damien Nouvel (INaLCO) Logique des prédicats 6
 Histoire et définitions

Liaison de variables

§ Dans une formule, selon la portée des quantificateurs

Damien Nouvel (INaLCO) Logique des prédicats 7

 Histoire et définitions

Liaison de variables

§ Dans une formule, selon la portée des quantificateurs

• Variable liée : si elle est dans la portée d’un quantificateur
ñ Exemple : @xP px q, @xP px q ^ pDyQ px , y qq

Damien Nouvel (INaLCO) Logique des prédicats 7

 Histoire et définitions

Liaison de variables

§ Dans une formule, selon la portée des quantificateurs

• Variable liée : si elle est dans la portée d’un quantificateur
ñ Exemple : @xP px q, @xP px q ^ pDyQ px , y qq
• Variable libre : si elle n’est pas liée
ñ Exemple : P px q, @x pP px q ^ Q px , y qq

Damien Nouvel (INaLCO) Logique des prédicats 7

 Histoire et définitions

Liaison de variables

§ Dans une formule, selon la portée des quantificateurs

• Variable liée : si elle est dans la portée d’un quantificateur
ñ Exemple : @xP px q, @xP px q ^ pDyQ px , y qq
• Variable libre : si elle n’est pas liée
ñ Exemple : P px q, @x pP px q ^ Q px , y qq
§ Une formule peut être
• Close : toutes les variables sont liées
• Ouverte : il existe au moins une variable libre
ñ Nous travaillons sur les formules closes

Damien Nouvel (INaLCO) Logique des prédicats 7

 Histoire et définitions

Sémantique, domaine et interprétation

§ Une interprétation I est constituée des éléments suivants

Damien Nouvel (INaLCO) Logique des prédicats 8

 Histoire et définitions

Sémantique, domaine et interprétation

§ Une interprétation I est constituée des éléments suivants

• Domaine D : valeurs que peuvent prendre les constantes
• Constantes : élément de D
• Prédicats : application de D n dans tV , F u
• Fonctions : application de D n dans D
ñ Une interprétation est un modèle pour une formule si elle la rend
toujours vraie dans le domaine
§ Exemple

Damien Nouvel (INaLCO) Logique des prédicats 8

 Histoire et définitions

Sémantique, domaine et interprétation

§ Une interprétation I est constituée des éléments suivants

• Domaine D : valeurs que peuvent prendre les constantes
• Constantes : élément de D
• Prédicats : application de D n dans tV , F u
• Fonctions : application de D n dans D
ñ Une interprétation est un modèle pour une formule si elle la rend
toujours vraie dans le domaine
§ Exemple
• Formule : @x pppx q Ñ q px , f px qq
• Domaine : D “ r0, `8s
• Prédicats : ppx q est vrai si x ă 1, q px , y q est vrai si x ą y
• Fonctions : f px q “ x 2

Damien Nouvel (INaLCO) Logique des prédicats 8

 Histoire et définitions

Sémantique, domaine et interprétation

§ Une interprétation I est constituée des éléments suivants

• Domaine D : valeurs que peuvent prendre les constantes
• Constantes : élément de D
• Prédicats : application de D n dans tV , F u
• Fonctions : application de D n dans D
ñ Une interprétation est un modèle pour une formule si elle la rend
toujours vraie dans le domaine
§ Exemple
• Formule : @x pppx q Ñ q px , f px qq
• Domaine : D “ r0, `8s
• Prédicats : ppx q est vrai si x ă 1, q px , y q est vrai si x ą y
• Fonctions : f px q “ x 2
ñ Cette interprétation est un modèle pour la formule

Damien Nouvel (INaLCO) Logique des prédicats 8

 Histoire et définitions

Sémantique, domaine et interprétation

§ Une interprétation I est constituée des éléments suivants

• Domaine D : valeurs que peuvent prendre les constantes
• Constantes : élément de D
• Prédicats : application de D n dans tV , F u
• Fonctions : application de D n dans D
ñ Une interprétation est un modèle pour une formule si elle la rend
toujours vraie dans le domaine
§ Exemple
• Formule : @x pppx q Ñ q px , f px qq
• Domaine : D “ r0, `8s
• Prédicats : ppx q est vrai si x ă 1, q px , y q est vrai si x ą y
• Fonctions : f px q “ x 2
ñ Cette interprétation est un modèle pour la formule
ñ Si l’on change le domaine, ça n’est plus un modèle
Damien Nouvel (INaLCO) Logique des prédicats 8
 Histoire et définitions

Exercices

§ Modélisez selon la logique des prédicats

• Jacques est le fils de Marie
• Tout le monde a un père
• Jean aime tout le monde
• Jacques n’aime pas tout le monde
• Personne n’aime Jacques
• Jean aime Marie mais Marie aime quelqu’un d’autre
• Jean aime une personne qui ne l’aime pas
• L’ami de mon ami est mon ami

Damien Nouvel (INaLCO) Logique des prédicats 9

 Manipulation de formules

Plan

1. Histoire et définitions

2. Manipulation de formules

Damien Nouvel (INaLCO) Logique des prédicats 10

 Manipulation de formules

Substitution

§ Substitution de variables
• Remplacement d’une variable par une expression
• Notation : pour une proposition A remplacer x par B se note Arx {B s
ñ Exemple : @x DyP px , y qrx {z s@z DyP pz , y q
ñ Utile pour la mise sous forme prénexe et skolémisation, lorsque
deux sous fomules ont les mêmes variables
§ Ordre des quantificateurs peut être modifié
• @x @y ” @y @x
• Dx Dy ” D y Dx
• Attention : @x Dy ı Dy @x

Damien Nouvel (INaLCO) Logique des prédicats 11

 Manipulation de formules

Mise sous forme normale prénexe

§ Une formule est sous forme prénexe si elle s’écrit Q1 Q2 . . . Qn F

• Q1 . . . Qn sont des quantificateurs
• F est sans quantificateurs
ñ On amène tous les quantificateurs en début de formule
§ Si F et G sont des formules
• Suppression des négations
• DxF ” @x F
• @xF ” Dx F
• Si G est libre de x
• @xF _ G ” @x pF _ Gq
• @xF ^ G ” @x pF ^ Gq
• DxF _ G ” Dx pF _ Gq
• DxF ^ G ” Dx pF ^ Gq
§ Exercice
• Avec G est libre de x, mettre sous forme prénexe p@xF q Ñ G
Damien Nouvel (INaLCO) Logique des prédicats 12
 Manipulation de formules

Forme normale de Skolem

§ Quantificateur existentiel : une constante satisfait la formule

• Il existe un homme qui a été président des États-Unis
” DxHommepx q ^ President px , USAq
” HommepBillClintonq ^ President pBillClinton, USAq
§ Sous quantification universelle l’individu dépend d’une fonction
• Chaque président des États-Unis est assisté par un vice président
” @xPresident px , USAq Ñ DyVicePresident px , y q
” @x DyPresident px , USAq Ñ VicePresident px , y q
” @xPresident px , USAq Ñ VicePresident px , NominationVP px qq
§ La skolémisation consiste à remplacer tous les D par
• Des constantes s’il n’y a pas de quantification existentielle avant
• Sinon des fonctions des variables quantifiées existentiellement

Damien Nouvel (INaLCO) Logique des prédicats 13

 Manipulation de formules

Forme normale clausale

§ Forme normale clausale

• Forme normale de Skolem
• Forme normale conjonctive
§ Résolvant de Robinson
• Si deux clauses sont sous la forme
• F “ F1 _ F2 . . . Fi . . . Fn
• G “ G1 _ G2 . . . Gj . . . Gn
• Et si Fi ” Gj alors la clause H résultant de la disjonction de F et
G après suppression de Fi et Gj est appelée clause résolvante de
F et G
• H “ F1 _ F2 . . . Fi ´1 _ Fi `1 . . . Fn _ G1 _ G2 . . . Gj ´1 _ Gj `1 . . . Fn

Damien Nouvel (INaLCO) Logique des prédicats 14

 Manipulation de formules

Exercices

§ Modélisez, mettez sous forme clausale

• Il existe une capitale où se trouve la Tour Eiffel
• Chaque capitale a un monument
• Si tous les hommes sont mortels, alors le père Noël n’existe pas
• S’il existe un homme naïf alors le père Noël existe

Damien Nouvel (INaLCO) Logique des prédicats 15