CHAP3- LOGIQUE DES PRÉDICATS
INTRODUCTION
Activité: Déterminez si chacune des phrases suivantes est une proposition ou
non. Si oui, précisez s’il s’agit d’une proposition vraie ou d’une proposition
fausse.
(a) 7 est un nombre pair.
(b) x est un nombre pair.
Réponse
- (a) Est une proposition fausse
- (b) n’est pas une proposition, tant que la valeur de x n’est pas
connue, on ne peut pas dire si elle est vrai ou fausse.
- « x est un nombre pair » est un Prédicat
- Un Prédicat est un énoncé général qui dépend d’une ou plusieurs variables.
INTRODUCTION (PRÉDICATS)
+ En fait, un prédicat est une expression qui associe une propriété à un ou
plusieurs objets. Par exemple, le prédicat P(x) signifie que l'objet x possède la
propriété P.
+ Exemples de prédicats en logique de prédicats :
- P(x) : l'objet x est un chien
- Q(x, y) : x est supérieur à y
- R(x, y, z) : x est plus grand que y et plus petit que z
+ Les prédicats sont utilisés dans les formules de logique de prédicats pour
exprimer des propositions.
INTRODUCTION
+ La logique des prédicats a pour objectif de généraliser la logique des
prédicat, des quantificateurs ∀ et ∃, des variables de quantification.
propositions tout en introduisant des nouvelles notions: La notion de
Exemple: Traduisons la phrase suivante en logique de prédicat:
« Tout homme est mortel »
Réponse:
quantificateur prédicats Variable de quantification
∀x:[homme(x) → mortel(x)]
INTRODUCTION (LES QUANTIFICATEURS)
∀ :quantificateur universel ; ∃:quantificateur existentiel
+ ∀xP(x) se lit "pour tout x, P(x)" et signifie
- « P(x) est vraie pour chaque valeur de x dans l’univers du discours ».
- Ou encore «Quelque soit la valeur de x (dans l’univers du discours), P(x) est
vraie. »
- Exemple : ∀x (x > 0) signifie "pour tout x, x est plus grand que 0".
+ ∃xP(x) signifie
- « Il existe au moins un élément x de l’univers du discours tel que P(x) est
vraie ».
- Exemple : ∃x (x > 0) signifie "il existe un x tel que x est plus grand que 0".
+ NB: L’ensemble des valeurs possibles pour la variable x est appelé univers
du discours, ou domaine de la fonction P(x).
+ Combinaison de Quantificateurs :
- ∀x ∀y (P(x, y)) : "Pour tout x et tout y, P(x, y) est vrai."
- ∃x ∀y (P(x, y)) : "Il existe un x tel que, pour tout y, P(x, y) est vrai."
+ Négation de Quantificateurs :
- ¬∀x P(x) : "Il n'est pas vrai que, pour tout x, P(x) est vrai." Cela
Equivaut à ∃x ¬P(x).
- ¬∃x P(x) : "Il n'est pas vrai qu'il existe un x tel que P(x) est vrai."
Cela équivaut à ∀x ¬P(x).
Application:
Trouvez la négation des propositions suivantes:
¬(∃x(x>0)) = ...
¬(∀y(y2≥0)) = ...
¬(∃z(z=2 ∧ z2=4)) ...
Interprétation de Quantificateurs:
comme une conjonction : ∀x:[étudiant(x) → intelligent(x)] et est interprété
+ L’interprétation de la quantification universelle est souvent comprise
par intelligent(et 1) ∧ intelligent(et 2) ∧ ... ∧ intelligent(et n).
comme une disjonction : ∃x:[étudiant(x) → intelligent(x)] est interprété par
+ L’interprétation de la quantification existentielle est souvent comprise
intelligent(et1) ∨ intelligent(et 2) ∨ ... ∨ intelligent(et n).
I-SYNTAXE
1- Alphabet
+ L’alphabet du calcul des prédicats (CP) est composé de :
1. Un ensemble fini de symboles de constantes: a, b, c, ...
2. Un ensemble fini de symboles de variables : x, y, z, ...
3. Un ensemble fini de symboles de fonctions: f, g, h, ...
4. Un ensemble fini de symboles de prédicats (relations): P, Q, R, ...
5. Des connecteurs logiques : ¬, ∧, ∨ ,→, ↔
6. Deux quantificateurs: universel (∀) et existentiel (∃)
7. Des parenthèses ( et ) et des crochets [ et ].
2- Les expressions du langage
a- Terme:
1- Tout symbole de constante ou de variable est un terme. Ex. Julie,
Sociologie, x.
2- Si f est un symbole de fonction à n arguments et t1, ...,tn sont des termes,
alors f(t1,...,tn) est un terme. Ex. père(Julie), père(père(Julie)), père(x),
cours(logique).
3- Un terme sans variables est un terme clos
4- Rien d’autres n’est un terme, s’il n’est pas obtenu en vertus des règles 1, 2
et 3.
b- Formule atomique:
+ Une formule atomique est une formule de la forme P(t1,...,tn) où P est un
symbole de prédicat et t1,...,tn sont des termes. Ex. père(Ali,Fatma).
+ t1=t2 est une formule atomique.
c- Formule :
une formule de la logique de prédicats est définie récursivement comme suit:
- Toute formule atomique est une formule,
- Si A est une formule alors : ¬A est une formule,
- Si A est une formule alors (A) est une formule.
- Si A et B sont des formules, alors A∧B ; A∨B ; A→B ; A↔B, sont aussi des
formules ;
- Si A est une formule et si x est une variable quelconque alors ∀x A et ∃x A
sont des formules.
3- Priorité des connecteurs et des quantificateurs
+ Les connecteurs et les quantificateurs sont appliqués dans l’ordre suivant :
∀, ∃, ¬, ∧, ∨ , →, ↔
+ Les parenthèses peuvent être utilisées pour changer l'ordre d'évaluation et
pour clarifier l'expression.(Les opérations à l'intérieur des parenthèses sont
évaluées en premier).
* Exemple
∀ x P(x) ∨ ∃y Q(y) ∧ P(x)
se lit
∀ x (P(x) ∨ ∃y (Q(y) ∧ P(x)))