La Logique des Prédicats

A chaque symbole de pr dicat et de fonction est associ un nombre darguments (arit ).

Variables et quantificateurs:

Lintroduction de variables permet de formuler deux types d noncer:

1. Des nonc s universels dans lesquels les variables repr sentent tous les objets

dun domaine. Exemples: tous les humains sont mortels :

x(hum ain(x) m or tel(x))

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 lexistence 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 rie

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 nis 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 nies 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 quanticateurs: loi de Morgan:

" "

" "

" "

" "

x( f ) a x( f )

x( f ) a x( f )

x( f ) a x( f )

x( f ) a 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 naime pas les brocolis : "

x( f ) a x( f )

x( Aim e(x, brocolis))

alors cette formule est quivalente il ny a personne

3. Certains tudiants assistent tous les cours

x(Et u dia nt (x) ' ( yAssist (x, y))

4. Aucun tudiant nassiste 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 quelquun et personne naime tout le monde, ou bien

quelquun aime tout le monde et quelquun naime 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 lon 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 nest 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 linterpr tation D, qui est un ensemble non vide

" Une fonction dinterpr 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 nie une fonction dinterpr 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 dinterpr tation D= {0, 1, 2, 3}

Et soit la fonction dinterpr 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 dinterpr tation I: une fonction dinterpr 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 d2 D Ix=d,y=d2P(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)}

{

do

x y(P(x, y) = vrai

7

"

"

"