14/11/2022
Cours: Logique Formelle
Chapitre 3: Logique des prédicats
Partie 1/3:
Réalisé par:
Dr. Sakka Rouis Taoufik
Chapitre 3: Logique des prédicats
I. Introduction
La logique propositionnelle qui nous a permis de mettre au point une
première théorie de raisonnement mais elle ne permet pas de formuler
tous les raisonnements .
Il faut aller alors plus loin que le simple calcul des propositions.
Nous n’allons plus contenter de simples propositions, mais nous allons
introduire un nouveau type de formules logique: appelé le prédicat.
Exemples :
- {n est un entier naturel pair} n’est pas une proposition
- par contre {5 est un entier naturel pair} est une proposition fausse.
À Chaque fois qu’on remplace n par un entier particulier
on obtient une proposition
- {n est un entier naturel pair} est un prédicat.
2
1
14/11/2022
Chapitre 3: Logique des prédicats
I. Introduction
Définitions :
un prédicat est une formule logique qui dépend d’une variable libre.
un prédicat c’est une affirmation qui porte sur des symboles
représentant des éléments variables d’un ensemble fixe.
- Puisqu’un prédicat dépend d’une variable x, nous les noterons souvent
P(x);
- C’est une application qui associe une proposition P(x) à chaque élément
d’un ensemble E, cette ensemble s’appelle l’univers du prédicat
- Dans le cas de l’exemple précédent E = N
Chapitre 3: Logique des prédicats
I. Introduction
Objectif:
La logique des prédicats a pour but de généraliser la logique des
propositions. On peut considérer un prédicat comme un énoncé général
où apparaissent des variables. Par exemple:
(1) « X est la sœur de Y »
(2) « si X est le père de Y et Y le père de Z alors X est le grand père de Z »
Si l’on remplace toutes les variables d’un prédicat par des valeurs définies
on obtient une proposition à la quelle on pourra associer une interprétation
(vrais, faux), Par exemple
X= Rim et Y = Ali dans (1) donne « Rim est la sœur de Ali »
Un prédicat représente donc potentiellement une classe de propositions.
2
14/11/2022
Chapitre 3: Logique des prédicats
I. Introduction
Le nombre des variables d’un prédicat s’appelle poids du prédicat.
Exemple : p (a,b) = { le couple d’entiers naturels (a,b) tel que a+b=10}
- si l’univers du prédicat est N2 alors son poids est égal à 2
- si l’univers du prédicat est N alors son poids est égal à 1
Dans un prédicat de poids n, si l’on affecte une valeur à l’une des
variables, on obtient un prédicat de poids n-1.
Par conséquent, un prédicat de poids 0 est une proposition.
Les prédicats qui portent sur le même univers peuvent être combinés
entre eux à l’aide des connecteurs , , , , pour former de
5
nouveau prédicat.
Chapitre 3: Logique des prédicats
I. Introduction
Définitions :
Le prédicat p (x) associe à x la négation du prédicat p(x)
Le prédicat pq (x) associe à x la conjonction des prédicats p(x) et q(x)
on notera aussi (p q) (x)
Le prédicat pq (x) associe à x la disjonction des prédicats p(x) et q(x)
on notera aussi (p q) (x)
• Exemple : même univers N
p(n) = {l’entier naturel n est pair}; q(m) = {l’entier naturel m est divisible pas 5}
- p(n) = {l’entier naturel n est impair}
- pq (n) = {l’entier naturel n est pair, et il est divisible par 5} (poids 1)
- pq (n) = {l’entier naturel n est pair, ou il est divisible par 5} (poids 1)
Attention : si l’univers est N2 (poids 2), il ne faut pas confondre pq (n) avec
S (n,m) = {l’entier naturel n est pair et l’entier naturel m est divisible par 5}
6
3
14/11/2022
Chapitre 3: Logique des prédicats
II. Formalisation du langage naturel
Soit P un prédicat de poids 1 sur l’univers E. Comme ce prédicat associe
une proposition P(x) à tout élément x de E, on peut trier les élément de E
en deux sous ensembles, ceux pour lesquelles P(x) est vraie et ceux pour
qui elle est fausse.
E
V F
Donc soit l’application v : E {V , F }
x P(x)
Ce tri revient à regrouper les éléments de E pour qui v (x) est V et ceux
pour qui v (x) = F
7
Chapitre 3: Logique des prédicats
II. Formalisation du langage naturel
Les quantificateurs :
L’affirmation « l’ensemble des x pour lesquels P(x) est vraie est E tout
entier » est une proposition ; on la note x P(x)
on lit : quelque soit x la proposition P(x) est vrai
: quantificateur universel
L’affirmation « l’ensemble des x pour lesquels P(x) est vraie n’est pas
vide » est une proposition ; on la note x P(x)
on lit : il existe x tel que P(x) est vraie
: quantificateur existentiel
4
14/11/2022
Chapitre 3: Logique des prédicats
II. Formalisation du langage naturel
Exemples :
Soit le prédicat P(n) = { l’entier naturel n est pair }
- n P(n) est une proposition fausse car on lit : « tout entier naturel est pair »
- n P(n) est une proposition vraie car on lit : « il existe un entier naturel pair »
Exercice d’application:
Soit les prédicats : H(x) = { x est un homme }
M(x) = { x est méchant }
Formuler les affirmation suivantes:
- «C’est faux que tout les hommes sont méchants »: (x (H(x) M(x)))
- «Seulement les hommes sont méchants » : x (M(x) H(x))
- « Il existe un homme méchant » : x (H(x) M(x))
- « Il n’existe pas d’homme méchant » : (x (H(x) M(x)))
9
Chapitre 3: Logique des prédicats
II. Formalisation du langage naturel
Remarques :
Soit P un prédicat dont l’univers est E = { e1, e2, e3,….., en}
- La proposition x P(x) est vraie quand les propositions P(e1) ,
P(e2),……, P(en) sont toutes vraies.
x P(x) se confond avec la proposition P(e1) P(e2) …… P(en)
- La proposition x P(x) est vraie si l’une au moins des propositions P(e1)
, P(e2),……, P(en) est vraie.
x P(x) se confond avec la proposition P(e1) P(e2) …… P(en)
Soit P(x,y,z) un prédicat de poids 3
- Q(x,z) = y P(x,y,z) est un prédicat de poids 2
- R(z) = x Q(x,z) = x y P(x,y,z) est prédicat de poids 1 10
5
14/11/2022
Chapitre 3: Logique des prédicats
III. Syntaxe du calcul des prédicats
Alphabet du langage du premier ordre (prédicat)
Le langage du calcul des prédicats est formé de :
--Les connecteurs , , , et
- Les quantificateurs
: quantificateur existentiel (« il existe » : x P(x) )
: quantificateur universel (« pour tout ») : x P(x) )
- Des constantes logiques : V et F
11
Chapitre 3: Logique des prédicats
III. Syntaxe du calcul des prédicats
Formules du langage :
- A est une formule atomique ssi A s’écrit sous la forme P(t1, t2,t3 …. tn)
avec: P est un symbole de prédicat de poids n ( P P n )
t1, t2,t3 …. tn sont des termes
- Une formule atomique (formule de poid 0) est une formule
- Si A est une formule, alors ( A) est une formule.
– Si A et B sont deux formules, A B, A B, A B et A B sont des
formules.
– Si A est une formule et x est une variable, alors x. A et x. A sont des
formules.
12
6
14/11/2022
Chapitre 3: Logique des prédicats
III. Syntaxe du calcul des prédicats
Termes du langage :
• Les termes sont construits à partir de l’ensemble des variables et des
symboles de fonctions F .
• Tout terme est engendré par l’application des lois suivantes:
Une constante est un terme (qui sera interprétée par un individus fixé)
Les symboles de fonctions ayant chacun un poids 1 sont des termes.
(un nombre d’arguments fixé)
Une variable est un terme (qui varie dans l’ensemble des individus de
l’interprétation)
Si f est un symbole fonctionnel d’arité (de poids) n et si t1, t2,t3 …. tn
sont n termes, alors f (t1, t2,t3 …. tn) est un terme.
Un terme est dit clos s’il ne contient aucune variable
13
Chapitre 3: Logique des prédicats
III. Syntaxe du calcul des prédicats
Termes du langage : Exemples
f (x, g (y , z) ) est un terme si f et g sont des symboles de fonction de poids 2.
Arbre de décomposition :
f
x g
y z
- f ( 5, 3 ) est un terme clos
- f (x, g (y1, y2) ) est un terme
14
7
14/11/2022
Chapitre 3: Logique des prédicats
III. Syntaxe du calcul des prédicats
Utilisation des quantificateurs :
Revenons au deux quantificateurs (existentiel et universel) développer
précédemment. Nous rappelons les définitions de chacun:
- : « existe au moins un sel »
- ! : « existe un et un seul »
- : « quelque soit, ou pour tout »
- Quantificateurs imbriqués:
Notons que l’ordre des quantificateurs est important. En effet, « tout le monde
aime quelqu’un » s’écrirait x.(y. Aime(x,y)), qui n’a pas exactement le
même sens que « il y a quelqu‘un qui est aimé par tout le monde » qui
15
s’écrirait y.(x. Aime(x,y)).
Chapitre 3: Logique des prédicats
III. Syntaxe du calcul des prédicats
Utilisation des quantificateurs :
Loi de Morgan entre les quantificateurs:
x.Fx.F
x.Fx.F
x.Fx.F
x.Fx.F
16
8
14/11/2022
Chapitre 3: Logique des prédicats
III. Syntaxe du calcul des prédicats
Formules du langage :
Illustration: soit le prédicat Aime (A, B) : « A aime B »
- « Tout le monde déteste les brocolis » revient au même que « Il n’existe
personne qui aime les brocolis »:
x. Aime(x,brocolis) x. Aime(x,bricolis)
-« Tout le monde aime les glaces » et « il n’y a personne qui n’aime pas les
glaces » sont équivalentes:
x. Aime(x,glaces ) x. Aime(x,glaces)
17
Chapitre 3: Logique des prédicats
III. Syntaxe du calcul des prédicats
Utilisation des quantificateurs :
Exercice 1: Formuler en calcul des prédicats les phrases suivantes:
1. les baleines sont des mammifères.
2. les entiers sont pairs ou impairs
3. Il existe un entier pair
Correction: E(x) : « x est un entier»
B (x) : « x est un baleine » P(x) : « x est pair»
M (x) : « x est un mammifère » I(x) : « x est impair»
Traduction : x. (B(x) M(x)) Traduction : x (E(x) (P(x) v I (x)) )
18
9
14/11/2022
Chapitre 3: Logique des prédicats
III. Syntaxe du calcul des prédicats
Utilisation des quantificateurs :
Exercice 2: Exprimer les énoncés suivants en logique du premier ordre
1. « Tous les lions sont féroces. »
2. « Quelques femmes ne boivent pas du café »
Correction:
Lion (x) : « x est un lion» Femme (x) : « x est une femme»
Feroce(x) : « x est un féroce» Cafe(x) : « x boit du café»
Traduction : x.(Lion(x) Feroce(x)) Traduction : x.(Femme(x)Cafe(x))
19
Chapitre 3: Logique des prédicats
III. Syntaxe du calcul des prédicats
Utilisation des quantificateurs :
Exercice 3: Utiliser les 3 prédicats suivants pour exprimer les énoncés
suivants en logique du premier ordre
Etudiant (x) : « x est un étudiant »; Assiste (x, y) : « x assiste au cours y »
Interessant(y) : « y est intéressant »
1. « Certains étudiants assistent à tous les cours »:
x.(Etudiant(x)(y . Assiste(x,y)))
2. « Aucun étudiant n’assiste à un cours intéressant »:
x.(Etudiant(x) (Assiste(x,y) Interessant(y)))
Dans la seconde formule, on constate que la variable y n’est pas quantifiée:
une telle variable est dite libre. Une variable quantifiée est dite liée. 20
10
14/11/2022
Chapitre 3: Logique des prédicats
III. Syntaxe du calcul des prédicats
Variables libres:
Soit A une formule. L’ensemble des variables libres de A, noté
Var(A), est définie comme suit :
Si A est un atome, de forme P(t1, t2,t3 …. tn) alors :
Var(A) = Var(P(t1, t2,t3 …. tn)) = Var(t1) U Var(t2) U…….U Var(tn)
Si A= B alors Var(A) = Var(B) = Var(B)
Si A=B # C avec # { , , , } alors :
Var(A) = Var(B # C) = Var(B) U Var(C)
Si A = x B ou A = x B alors :
Var(A) = Var( x B) = Var( x B) = Var(B) \ {x} 21
Chapitre 3: Logique des prédicats
III. Syntaxe du calcul des prédicats
Variables libres:
- Chacune des fois où une variable x apparaît dans une
formule A est appelée une occurrence de x dans A.
- Toutes les occurrences des variables d’un terme sont des
variables libres de t. c.a.d :
1/ Var(x) = {x}
2/ Var(c) = { } ( c : constante)
3/ Var(f (t1, t2,t3 …. tn)) = Var(t1) U Var(t2) U…….U Var(tn)
- Une formule de A est dite close si Var(A) = (A n’a pas
de variable libre) 22
11
14/11/2022
Chapitre 3: Logique des prédicats
III. Syntaxe du calcul des prédicats
Variables libres: Exemples :
- A : x y P(f (x,y),z)
Var(A) = Var(y P(f (x,y),z)) \{x}
= Var(P(f (x,y),z) \{y} ) \{x}
= Var( (Var(f (x,y)) U Var(z)) \{y} ) \{x}
= (({x,y} U {z}) \{y} ) \{x}
= ({x,y,z}\{y}) \{x}
= ({x,z}) \{x}
={z} Donc A n’est pas close
- B : x P(x)
Var(B) = Var(x P(x))= Var(P(x)) \{x} = {x} \{x} =
23
Donc B est close
Chapitre 3: Logique des prédicats
III. Syntaxe du calcul des prédicats
Variables libres : Exemple :
- A : (x (P(x,y) Q(x))) ( y ( P(x,y) (z Q(z)) ) )
Var(B) = Var(P(x,y) Q(x)) \ {x} = { x,y,x }\ {x} = {y}
Var(C) = Var( P(x,y) (z Q(z))) \ { y }
Var(C) = (Var( P(x,y)) U Var(Q(z) \ { z } )) \ { y }
Var(C) = ({ x,y } U ({ z } \ { z } )) \ {y}
Var(C) = { x,y } \ {y} = { x }
Var(A) = Var(B) U Var(C) = { x, y }
24
12
14/11/2022
Chapitre 3: Logique des prédicats
III. Syntaxe du calcul des prédicats
Variables liées :
- Soit A une formule. L’ensemble des variables liées de A, noté
BVar(A) (B pour bound), est définie comme suit :
Si A est un atome, BVar(A) =
Si A= C alors BVar(A) = BVar(C) = BVar(C)
Si A=B # C avec # { , , , } alors :
BVar(A) = BVar(B # C) = BVar(B) U BVar(C)
Si A = x B ou A = x B alors :
BVar(A) = BVar( x B) = BVar( x B) = BVar(B) U {x}
25
Chapitre 3: Logique des prédicats
III. Syntaxe du calcul des prédicats
Variables liées : Exemple :
- A : (x (P(x,y) Q(x))) ( y ( P(x,y) (z Q(z)) ) )
BVar(B) = BVar(P(x,y) Q(x)) U {x}
= (BVar(P(x,y)) U BVar(Q(x))) U { x }
=(U)U{x}={x}
BVar(C) = BVar( P(x,y) (z Q(z))) U { y }
BVar(C) = (BVar( P(x,y)) U ( BVar(Q(z)) U { z } ) ) U { y }
BVar(C) = ( U ( U { z } ) ) U {y} = { z } U {y} = { z,y }
BVar(A) = BVar(B) U BVar(C) = { x, y ,z} 26
13
14/11/2022
Chapitre 3: Logique des prédicats
III. Syntaxe du calcul des prédicats
Variables liées : Exemple :
- A : (x (P(x,y) Q(x))) ( y ( P(x,y) (z Q(z)) ) )
BVar(B) = BVar(P(x,y) Q(x)) U {x}
= (BVar(P(x,y)) U BVar(Q(x))) U { x }
=(U)U{x}={x}
BVar(C) = BVar( P(x,y) (z Q(z))) U { y }
BVar(C) = (BVar( P(x,y)) U ( BVar(Q(z)) U { z } ) ) U { y }
BVar(C) = ( U ( U { z } ) ) U {y} = { z } U {y} = { z,y }
BVar(A) = BVar(B) U BVar(C) = { x, y ,z} 27
Chapitre 3: Logique des prédicats
III. Syntaxe du calcul des prédicats
Exercice d’application :
Donner les variables libres et liées pour chacune des formules
suivantes:
1/ x (P(x) y Q(x,y))
2/ ( y Q(x,y)) x P(x)
3/ x ((y P(x,y)) (z Q(z) R(x)))
4) (x ((y P(x,y)) ) (z Q(z) R(x))
5/ ((x P(x) y Q(y)) z R(z)) u S(u)
28
14
