Chapitre IV - Logique Mathématique

Université Mouloud MAMMERI de Tizi-Ouzou
Faculté de génie électrique et informatique

Département d’informatique
Module : Logique Mathématique – L2 – année : 2022/2023
Chapitre IV
Calcul des Prédicats du 1er ordre
Par : Mr HABET Md-Said

(reprise des notes de cours de Mr KHEMLICHE Salem)
Chapitre IV : Calcul des prédicats du 1er ordre
IV.1/ Introduction :
Il existe des phrases qu’on ne peut pas représenter el logique propositionnelle comme : « Tous les
oiseaux ont des ailes » ou « certains oiseaux ne volent pas ».
Le but du calcul des prédicats du premier ordre est d’exprimer par des formules le plus fidèlement
possible de telles phrases grâce à l’introduction de deux quantificateurs ∀ et ∃ permettant de quantifier
des variables appartenant à un domaine quelconque.
C’est donc une extension du calcul propositionnel.
IV.2/ Le langage du calcul des prédicats du 1er ordre :

IV.2.1/ L’alphabet :
L’alphabet du calcul des prédicats du premier ordre est composé de :
- un ensemble infini dénombrable de variables individuelles : x1, x2, … ;
- un ensemble de constantes : a1, a2, … ;
- un ensemble dénombrable de symboles de prédicats : P1, P2, … ;
- un ensemble dénombrable de symboles de fonctions : f1, f2, … ;
- des connecteurs :  ,  ,  ,  , ↔ ;
- des quantificateurs ∀ et ∃ ;
- des parenthèses : (, ).
IV.2.2/ Les termes :

Les termes du calcul des prédicats du premier ordre sont définis comme suit :
i) Les variables et les constantes sont des termes.
ii) Si f est une fonction n-aire (d’arité n) et t1, …, tn sont des termes alors f(t1, …, tn) est un terme.
iii) Aucune autre formule n’est un terme.
Exemples : x, a, f(x), g(x,f(a)) sont des termes.
Définition IV.2.3 : (Prédicat)

Soit un domaine 𝒟, un prédicat est une fonction définie sur 𝒟 𝑛 dans l’ensemble des valeurs de vérité
{0, 1}.
Exemples : 1) Rond : {ensemble des objets}  {0, 1}

Rond(terre) = 1 : « la terre est ronde »
2) Père : {ensemble des humains}  {0, 1}
Père(x,y) : « x est père de y »
Définition IV.2.4 : (formule atomique)

Si P est un prédicat d’arité n et t1, …, tn sont des termes alors P(t1, …, tn) est une formule atomique.
-2-
Définition IV.2.5 : (formules bien formées)

Les formules bien formées (fbf) ou tout simplement les formules du calcul des prédicats du 1 er ordre
(CP1) sont définies comme suit :
i) Toute formule atomique est une fbf.
ii) Si A et B sont deux fbf et x une variable, alors :
A, (A  B), (A  B), (A  B), (A ↔ B), (∀x) A et (∃x) A sont des fbf.
iii) Toute fbf du CP1 est obtenue par l’application d’un nombre fini de fois des étapes i) et ii).
Exemples : Les formules suivantes sont des fbf :

1. F ≡ ∀x A(x)  (∀y (P(f(y),a)  P(x,g(y))))
2. G ≡ P(f(a),b)  ∀x ∃y (P(x,y)  P(f(x),g(y)))
Remarques :
1) Le calcul des prédicats est dit du 1er ordre car la quantification se fait sur des variables individuelles.
2) ∀x P(x) signifie : Pour tout x du domaine, P(x) est vrai.
∃x Q(x) signifie : Il existe x dans le domaine tel que Q(x) est vrai.
3) Les formules peuvent être allégées par la suppression de certaines parenthèses en tenant compte de
l’ordre de priorité des connecteurs suivant :
( , ) ,  ,  ,  , ∃, ∀,  , ↔
+ -
IV.2.6/ Notion de variables libres et variables liées :

Dans la formule ∀x A(x), le champ du quantificateur ∀ est la formule A. Les positions occupées par la
variable x dans la formule A sont dites occurrences de x.
Définition IV.2.6.1/ : (occurrence libre et occurrence liée)

Une occurrence d’une variable x dans une formule est dite liée si elle figure dans le champ d’un
quantificateur portant sur cette variable. Elle est dite libre sinon.
Exemple :
Dans la formule : F ≡ (∀x A(x))  (∀y (P(f(y),a)  P(x,g(y))))
la 1ère occurrence de x est liée, tandis que la 2ième est libre.
Définition IV.2.6.2/ : (variable libre et variable liée)

Une variable x est dite liée dans une formule F lorsqu’elle possède au moins une occurrence liée dans
F. Elle est dite libre si elle possède une occurrence libre dans F.
Exemple :
F ≡ (∀x P(x))  Q(x,y)
x est libre (dans Q(x,y)) et liée (dans (∀x P(x))).
-3-
Définition IV.2.6.3/ : (terme libre pour une variable)

Soit A une fbf du CP1 ; un terme t est libre pour une variable x dans A si aucune occurrence libre de x
dans n’appartient à un champ de quantificateur (∀y) ou (∃y) où y est une variable de t.
Exemple :
A ≡ ∀x P(x,y)  ∃z P(x,z)
• le terme f(y,u) est libre pour x dans A
• le terme f(y,z) n’est pas libre pour x dans A
IV.3/ Interprétation :
IV.3.1/ Introduction :
On interprète une fbf F quelconque du CP1 en attribuant un sens (signification) aux différents symboles
de prédicats, de fonctions, de constante et de variables utilisés dans F. Pour une fbf donnée, on peut
obtenir plusieurs interprétations.
Exemple :
Soit F ≡ ∀x ∃y P(x,y)
Une 1ère interprétation possible : P(x,y) interprété comme relation « x ≤ y » dans ℕ.
Une 2nde interprétation possible : interpréter P(x,y) comme relation « x est fils de y » dans le domaine
des êtres humains.
Définition IV.3.2/ : (interprétation)

Soit G une fbf du CP1. Une interprétation I de G est un quadruplet <DI, A, F, P> où :
- DI est appelé domaine de l’interprétation I ;
- A est un sous-ensemble de DI appelé ensemble des valeurs constantes de G dans DI ;
- F est l’ensemble des fonctions de G définies dans DI ;
- P est l’ensemble des prédicats de G définis dans DI.
Exemple :
Soit G ≡ ∀x ∀y ∃z P(f(x,y),z)
• Soit I l’interprétation :
DI = ℕ
f:ℕ×ℕℕ
(x,y) ⟼ f(x,y) ≡ x+y
P : ℕ × ℕ  {0, 1}
(u,v) ⟼ P(u,v) ≡ "u = v"
G devient : ∀x ∈ ℕ, ∀y ∈ ℕ, ∃z ∈ ℕ ((x+y)=z) qui est vraie.
• Soit J l’interprétation :
DJ = ℕ
f:ℕ×ℕℕ
(x,y) ⟼ f(x,y) ≡ x+y
-4-
P : ℕ × ℕ  {0, 1}
(u,v) ⟼ P(u,v) ≡ "u > v"
G devient : ∀x ∈ ℕ, ∀y ∈ ℕ, ∃z ∈ ℕ (x+y>z) qui est fausse (pour x=0 et y=0 ∄z tel que x+y>z).
Définition IV.3.3/ :
Une validation (valuation) dans une interprétation I est une fonction v de l’ensemble des termes du CP1
dans l’ensemble DI, définie inductivement comme suit :
1. v(a) = a pour chaque constante a de A
2. v(f(t1, …, tn)) = f(v(t1), …, v(tn))
où la barre signifie valeur.
Remarque :
Pour une interprétation donnée, il existe plusieurs validations différentes ; chaque validation v affecte à
chaque variable propositionnelle un élément de DI. Elle est déterminée par la donnée des v(x1), v(x2), …
puisque les v(ai) et les v(f(t1, …, tn)) sont donnés par les clause 1. Et 2. de la définition IV.3.3.
Dans l’interprétation I de l’exemple précédent pour la formule ∀x ∀y ∃z P(f(x,y),z), les valeurs

possibles pour les variables x, y et z sont 0, 1, …, n, … . Les triplets (x1,x2,x3) avec xi ∈ ℕ déterminent
toutes les validations pour cette formule.
Deux validations v et v’ sont dites x-équivalentes si v(y) = v’(y) pour tout y ≠ x.
IV.4/ Satisfaction, valeurs de vérité d’une formule :

Soit A une fbf du CP1 et soit I une interprétation. Une validation v dans I satisfait A si nous pouvons le
montrer par induction comme suit :
1. v satisfait la formule atomique P(t1, …, tn) si Pv(v(t1), …, v(tn)) est vraie dans DI.
2. v satisfait B si v ne satisfait pas B.
3. v satisfait (B  C) si v ne satisfait pas B ou satisfait C.
4. v satisfait ∀x B si chaque validation v’ x-équivalente à v satisfait B.
Une formule A est vraie dans une interprétation I si chaque validation satisfait A dans I.
A est fausse dans I s’il n’existe aucune validation qui satisfait A.
Notation : I ⊨ A signifie que A est vraie dans I.
Remarque : Une formule A peut être satisfaite par certaines valuations et non satisfaite par d’autres. Une
telle formule n’est ni vraie ni fausse.
-5-
Proposition IV.4.3/ :
Si deux formules A et (A  B) sont vraies dans une interprétation I, alors B est vraie dans I.
Démonstration :
Soit v une valuation de l’interprétation I. v satisfait A et A  B, alors v ne satisfait pas A (ce qui n’est
pas le cas car v satisfait A) ou v satisfait B. Donc le seule cas est v satisfait B i.e B est vraie dans I.
Proposition IV.4.4/ :
Soit A une formule et I une interprétation, alors : I ⊨ A ⇔ I ⊨ ∀x A
Démonstration :
Supposons que nous avons I ⊨ A et soit v une validation dans I. v satisfait A et chaque validation v’
x-équivalente à v satisfait aussi A, car toute validation dans I satisfait A. Donc v satisfait ∀x A.
D’où : I ⊨ ∀x A.
La réciproque : I ⊨ ∀x A ⟹ I ⊨ A est immédiate.
Une formule du calcul des prédicats est dite valide si elle vraie pour toute interprétation possible.
Elle est dite non valide s’il existe au moins une interprétation pour laquelle est fausse.
Une formule du calcul des prédicats est dite insatisfiable si elle fausse pour toute interprétation
possible. Elle est dite satisfiable s’il existe au moins une interprétation pour laquelle la formule est vraie.
• L’interprétation qui donne la valeur vraie pour une formule est appelée modèle pour cette formule.
• L’interprétation qui donne la valeur fausse pour une formule est appelée contre-modèle pour cette
formule.
Lemme IV.4.7/ :
Une formule A est valide si et seulement si A est insatisfiable.
Démonstration : Faire en exercice.
Exemple :
Montrons que la formule : ∀x ∀y ( x ≠ y ∨ P x, y ∨ P y, x ) est valide.
Il y a lieu de distinguer deux cas :
1. (x=y) la formule devient P x, x ∨ P x, x qui est toujours vraie.
2. (x≠y) dans ce cas x ≠ y donne toujours la valeur vraie à la formule considérée.
À compléter …
----------=====---------- Fin du chapitre IV ----------=====----------
-6-

Chapitre IV - Logique Mathématique

Transféré par

Droits d'auteur :

Formats disponibles

Chapitre IV - Logique Mathématique

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

Chapitre IV - Logique Mathématique

Transféré par

Droits d'auteur :

Formats disponibles

Université Mouloud MAMMERI de Tizi-Ouzou

Faculté de génie électrique et informatique

Calcul des Prédicats du 1er ordre

Par : Mr HABET Md-Said

IV.2/ Le langage du calcul des prédicats du 1er ordre :

IV.2.2/ Les termes :

Exemples : x, a, f(x), g(x,f(a)) sont des termes.

Définition IV.2.3 : (Prédicat)

Exemples : 1) Rond : {ensemble des objets}  {0, 1}

Définition IV.2.4 : (formule atomique)

Définition IV.2.5 : (formules bien formées)

Exemples : Les formules suivantes sont des fbf :

IV.2.6/ Notion de variables libres et variables liées :

Définition IV.2.6.1/ : (occurrence libre et occurrence liée)

Définition IV.2.6.2/ : (variable libre et variable liée)

Définition IV.2.6.3/ : (terme libre pour une variable)

Définition IV.3.2/ : (interprétation)

Dans l’interprétation I de l’exemple précédent pour la formule ∀x ∀y ∃z P(f(x,y),z), les valeurs

IV.4/ Satisfaction, valeurs de vérité d’une formule :

----------=====---------- Fin du chapitre IV ----------=====----------

Vous aimerez peut-être aussi