La Logique des Prédicats

exprime le fait que si x est un être humain alors

• tous les humains sont mortels: " hum ain(x) → m or tel(x) x est mortel; x < x + 1 alors x est strictement inférieur à x+1: "

• "

pour les nombre entiers exprime le fait que x est un nombre

∀x, x < x + 1

2. Des énoncés exprimant l’existence de quelque chose, sans la connaitre précisément ;

exemple:

• Père (Mohamed, x), x représente la personne qui est le père de Mohamed • 3x-8= 22; x représente un nombre encore inconnu, qui existe et qui vérifie

l’équation. "

∃x,3x − 8 = 22

A partir du vocabulaire W, on construit les termes, les atomes et les formules, tels que:

• Les termes sont définis récursivement sur W par:

• toutes variables et toutes constantes est un termes • Si f est une fonction et "

sont ses termes, alors "

t1, t2, t3, . . . tn

f (t1, t2, t3, . . . tn)

est un

terme

• Si P est un prédicat et et "

t1, t2, t3, . . . tk un atome ou encore une proposition

sont ses termes, alors "

P(t1, t2, t3, . . . tk)

est

• Les formules bien formée sont définies récursivement par:

• Les atomes sont des formules • Si f est une formule et x est une variable, alors "

∀x( f ) et ∃x( f )

sont des

formules

• Si f et g sont deux formules alors: "

¬f, f ∧ g, f ∨ g, f ↔ g, et f → g

sont des

formules.

Propriétés

• Règles de priorités: pour éviter toute ambiguïté on adopte la règle de priorité

suivant :

1) ∀, ∃ 2) ¬, 3) ∧ , ∨ , 4) → , ↔

• Liens entre quantificateurs: loi de Morgan:

• " • " • " • "

¬ ∀x( f ) ≡ ∃x( ¬f ) ¬ ∃x( f ) ≡ ∀x( f ) ∀x( f ) ≡ ¬ ∃x( ¬f ) ∃x( f ) ≡ ¬ ∀x( ¬f )

3

" " Exemples

1. 2+2=4 (ou encore deux plus deux égale à quatre): Egale (Plus (2,2), 4)

tel que:

Prédicat: Egale, dont les termes sont Plus(2,2) et 4 termes: 4 est une constante

Plus (2,2) est une fonction dont les termes sont 2 et 2

2. Tout le monde aime les brocolis: "

∀x Aim e(x, brocolis) Aime: Prédicat; les termes sont x: variable et Brocolis : constante

:

Or on sait que " qui n’aime pas les brocolis »: "

∀x( f ) ≡ ¬ ∃x( ¬f )

¬ ∃x( ¬Aim e(x, brocolis))

alors cette formule est équivalente à « il n’y a personne

3. Certains étudiants assistent à tous les cours

∃x(Et u dia nt (x) ∧ ( ∀yAssist (x, y))

4. Aucun étudiant n’assiste à un cours inintéressant ¬ ∃x(Et u dia nt (x) → (Assist (x, y) ∧ ¬Interessa nt (y)))

5. Tous les hommes sont méchants

∀x(Hom m e(x) → Mech a nt (x))

6. Seulement les hommes sont méchants

∀x(Mech a nt (x) → Hom m e(x))

7. Il existes des hommes méchants

∃x(Hom m e(x) ∧ Mech a nt (x))

8. Il existe un homme qui aime toutes les femmes.

∃x(Hom m e(x) ∧ ∀yFem m e(y) → aim e(x, y))

9. Chaque chat connait un chien qui le déteste

∀x(Ch at (x) → ∃y(Chien(y) ∧ conn ait (x, y) ∧ detest (y, x)))

10. Chaque personne aime quelqu’un et personne n’aime tout le monde, ou bien

quelqu’un aime tout le monde et quelqu’un n’aime personne. ( ∀x ∃y aim e(x, y) ∧ ¬( ∃x ∀y aim e(x, y))) ∨ ( ∃x ∀y aim e(x, y) ∧ ∃x ∀y ¬aim e(x, y))

11. Il y a des gens que l’on peut rouler tout le temps et quelque fois on peut rouler

tout le monde, mais on ne peut pas rouler tout le monde à chaque fois. ∃x ∀t rouler (x, t) ∧ ∃t ∀xrouler (x, t) ∧ ∀t ∀x ¬rouler (x, t)

Remarque: On traduit couramment certaines expressions en logique du prédicats:

• « Tous les A sont B »: " • « Seuls les A sont B »: " • « Aucun A n’est B »: "

∀x(A(x) → B(x)) ∀x(B(x) → A(x)) ∀x(A(x) → ¬B(x))

4

" " " " " " " " " • « Quelques A sont B »: "

∃x(A(x) ∧ B(x))

Sémantique

Une interprétation I du vocabulaire W est la donnée de:

• Le domaine de l’interprétation D, qui est un ensemble non vide • Une fonction d’interprétation I, qui associe à chaque:

• Variable un valeur dans D • Constante une valeur dans D • Fonction à n termes une fonction totale de " • Prédicat à k termes une relation k-aire dans D;

Dn → D

Interprétation des termes On définie une fonction d’interprétation I par:

Terme

Constante c

Variable x

I(Terme)

I(c)

I(x

Fonction "f (t1, t2, . . . , tn)

"I( f )(I(t1), I(t2), . . . , I(tn))

Exemple: Soient:

Le vocabulaire W { a, b, c, d : constantes; x, y: variables et f: une fonction} Le domaine d’interprétation D= {0, 1, 2, 3} Et soit la fonction d’interprétation I telle que:

• I(a) 0, I(b)= 1, I(c)= 2 et I(d)=3 • I(x)= 1 et I(y) =0 • "

I( f ) = ((0,0) → 0, (0,1) → 0, (1,0) → 2, (2,3) → 2, (3,3) → 3, . . . → 3 pour le reste)

les interprétation des termes suivant selon I:

• " • " • "

I(a) = 0 I( f (a, x)) = I( f )(I(a), I(x)) = I( f )(0,1) = 0 I( f (x, f (y, b)) = I( f )(I(x), I( f (y, b)) = I( f )(1,I( f )(I(y), I(b)) = I( f )(1,I( f )(0,1)) = I( f )(1,0) = 2

Interprétation des atomes

I(P(t1, t2, . . . , tn)) = v ssi (I(t1), I(t2), . . . I(tn)) ∈ I(P)

Interprétation de formules avec quantificateurs

• "

I( ∀xϕ) = vrai ssi pour tout d ∈ D on a Ix=d(ϕ) = vrai

5

! • "

I( ∃xϕ) = vrai ssi il existe d ∈ D on a Ix=d(ϕ) = vrai

Exemple Soit le vocabulaire W { a, b: constantes, f: fonction, P: prédicat}

Et soit D= {1,2} le domaine d’interprétation I: une fonction d’interprétation telle que:

• I(a) =1, I(b)= 2 • I(f(1))=2, I(f(2))= 1 • I(P(2,1) = faux; I(P(2,2))= faux; I(P(1,2))=vrai; I(P(1,1)) = vrai.

Donner les interprétation des formules suivantes: • I(P(b, f(b)) I(P(b, f (b)) = vrai ssi (I(b), I( f (b))) ∈ I(P) or (I(b), I( f (b)) = (2,I( f )(I(b)) = (2,I( f )(2)) = (2,1) or I(P(2,1)) = fau x donc I(P(b, f (b)) = fau x

• I(P(a, f(a)) I(P(a, f (a)) = vrai ssi (I(a), I( f (a))) ∈ I(P) or (I(a), I( f (a)) = (1,I( f )(I(a)) = (1,I( f )(1)) = (1,2) or I(P(1,2)) = vrai donc I(P(a, f (a)) = vrai

• "

I( ∀x P(b, x))

I( ∀x P(b, x)) = vrai ssi ∀d ∈ D, Ix=dP(b, x) = vrai

Ix=1(P(b, x)) = vrai ssi (I(b),1) ∈ I(P) Ix=2(P(b, x)) = vrai ssi (I(b),2) ∈ I(P)}

{

(2,1) ∉ I(P) (2,2) ∉ I(P)}

{

Donc "

I( ∀x P(b, x)) = fau x

• "

∃x ∀y(P(x, y)

∃x ∀y(P(x, y) = vrai ssi il existe d ∈ D tel que Ix=d( ∀yP(x, y)) = vrai

or Ix=d( ∀yP(x, y)) = vrai ssi pour tout d′ ∈ D Ix=d,y=d′P(x, y) = vrai

or pour x = 1 on a

:

6

" " " " " " " " " " " " Ix=1,y=1(P(1,y)) = vrai ssi (1,1) ∈ I(P) Ix=1,y=2(P(1,y)) = vrai ssi (1,2) ∈ I(P)}

donc

{

(1,1) ∈ I(P) (2,2) ∈ I(P)}

{

d’où

∃x ∀y(P(x, y) = vrai

7

" " "