Logique des prédicats - Résolution des exercices

(iii) Aucun animal rationnel nest un philosophe : x((Ax ' Rx) P x)

(iv) Quelque philosophe rationnel na rien ecrit : x(P x ' Rx ' yExy)

(v) Tout philosophe rationnel a ecrit quelque chose : x((P x ' Rx) yExy)

(vi) Aucun philosophe rationnel nest cit e par tout le monde :

x((P x ' Rx) yCyx)

3

(vii) Quelquun cite tous les philosophes : xy(P y Cxy)

(viii) Personne ne cite tous les philosophes : xy(P y Cxy)

(ix) Quelquun qui se cite ne cite pas tous les philosophes :

x(Cxx ' y(P y Cxy))

(x) Tout philosophe cite quelque philosophe qui ne cite personne :

x(P x y(P y ' Cxy ' zCyz))

(xi) Tout philosophe cite quelque philosophe qui na rien ecrit.

x(P x y(P y ' Cxy ' zEyz))

Exercice 28 Si le vocabulaire consid er e contient une seule constante c, une seule pr edicat

unaire P , et une seule pr edicat binaire R, et si on a disponible une seule variable x, quelles

sont les formules atomiques qui peuvent etre form ees dans le langage correspondant de la

logique des pr edicats ? P c, P x, Rcc, Rxx, Rcx, Rxc.

Exercice 29 Pour chacune des expressions suivantes, d eterminez si elle est une formule de

la logique des pr edicats.1 On suppose que larit e du pr edicat P est 1 et larit e du pr edicat

R est 2 ; x, y, z sont des variables et c est une constante.

(i) R : Non. Des justications possibles de la r eponse : Un quanticateur est toujours

imm ediatement suivi dune variable dans une formule (ce qui nest pas le cas ici pour

aucun des deux quanticateurs) / un pr edicat binaire est toujours suivi dune suite

de deux termes dans une formule (ce qui nest pas le cas ici non plus).

(ii) x(yRxy zRzx) : Oui. Pour justier la r eponse, vous pouvez construire un

arbre syntaxique.

(iii) P c ( Rxc ' P y : Non. Les connecteurs binaires (', ( et ) sont selon la syntaxe

toujours introduits avec des paranth`eses : si et sont des formules et est un tel

connecteur, alors ( ) et non pas est une formule. Dailleurs, ici on

note que lexpression P c ( Rxc ' P y nest pas seulement syntaxiquement mal form ee

mais aussi s emantiquement ambigu e. Il y aurait deux mani`eres de la d esambigu 1ser :

1Pour justier votre r eponse, vous pouvez utiliser les arbres syntaxiques ou directement les conditions

qui sp ecient la syntaxe. Quand une expression nest pas bien form ee (nest pas une formule), il faut

en particulier expliquer pourquoi elle ne peut pas etre construite en utilisant les r`egles syntaxiques ou

pourquoi un essai de dessiner un arbre syntaxique qui respecte ces r`egles va echouer.

4

((P c ( Rxc) ' P y) et (P c ( (Rxc ' P y)).2

(iv) P xy : Non, car P est un pr edicate unaire.

(v) x(P x ' y(Rxy (zRzy ( P c))) : Oui. Pour justier la r eponse, vous

pouvez construire un arbre syntaxique.

Exercice 32 Dans chacun des cas suivants, d eterminez quelles occurrences des variables

sont li ees et quelles occurrences des variables sont libres dans la formule en question ;

d eterminez aussi si la formule est un enonc e.

(i) x(P xy ' Qx) :3 Toutes les deux occurrences de x dans des formules atomiques

sont li ees par lunique occurrence du quanticateur x ; loccurrence de y est libre.

La formule nest pas un enonc e (une formule close) parce que cette formule a des

occurrences des variables libres.

(ii) (xP xy ' Qx) : Loccurrence de x dans P xy est li ee par lunique occurrence de

x, loccurrence de y libre comme aussi loccurrence de x dans Qx. La formule

nest pas un enonc e.

(iii) (xyP xy Rxy) : Loccurrence de x dans P xy est est li ee par lunique

occurrence de x, loccurrence de y dans P xy etant li ee par lunique occurrence

de y. Les occurrences de x et de y dans Rxy sont libres. La formule nest pas un

enonc e.

(iv) x(yP xy Rxy) : Toutes les deux occurrences de x dans des formules ato-

miques sont li ees par lunique occurrence de x ; loccurrence de y dans P xy est

li ee par lunique occurrence de y ; loccurrence de y dans Rxy est libre. La formule

nest pas un enonc e.

(v) xy(P xy Rxy) : Toutes les deux occurrences de x dans des formules atomiques

sont li ees par lunique occurrence de x ; toutes les deux occurrences de y dans des

formules atomiques sont li ees par lunique occurrence de y. La formule est bien un

enonc e car toutes les occurrences des variables dans cette formule sont li ees.

2Pour une discussion de telles ambigu 1t es, cf les notes de cours de L1 (non pas L2), d ebut du Ch 4.

3Dans cette exercice Q est un pr edicat unaire. Parfois pendant le cours jai utilis e Qx pour d esigner

un quanticateur de fa con g en erique (donc dans ce cas Qx est une variable dont la valeur est soit x

soit x). Pour eviter ambigu 1t e il serait mieux utiliser dans le second cas une autre police, par ex. Qx

ou Qx.

5

(vi) (ySx ' x(Qy yRxy)) : Loccurrence de x dans Sx est libre, comme aussi

loccurrence de y dans Qy. Loccurrence de x dans Rxy est li ee par lunique

occurrence du quanticateur x, tandis que loccurrence de y dans Rxy est li ee par

la deuxi`eme occurrence du quanticateur y. La formule nest pas un enonc e.

(vii) y(Sx ' (xQy yRxy)) : Toutes les deux occurrences de x dans des formules

atomiques sont libres ; loccurrence de y dans Qy est li ee par la premi`ere occur-

rence du quanticateur y ; et loccurrence de y dans Rxy est li ee par la deuxi`eme

occurrence de y. La formule nest pas un enonc e.

Exercice 33 Quels aspects du contexte d evaluation faut-il conna 1tre pour pouvoir d e-

terminer la valeur de v erit e de l enonc e de la forme suivante :

(i) P c : ici il sut de conna 1tre linterpr etation I(P ) du pr edicat P et linterpr etation

I(c) de la constante c. Si I(c) I(P ) l enonc e est vrai, autrement non.

(ii) xP x : Eectivement ici il est susant de conna 1tre linterpr etation I(P ) du

pr edicat P : Si lensemble I(P ) est non vide, l enonc e est vrai, autrement non.

Encore un troisi`eme exemple : l enonc e x P x. Dans ce cas il est n ecessaire mais

non pas susant de conna 1tre linterpr etation I(P ) du pr edicat P ; il faut aussi

conna 1tre le domaine (lunivers du discours) D du mod`ele. Si lensemble D \ I(P )

est non vide, alors l enonc e est vrai, autrement non.4

Un mod`ele consiste en une sp ecication dun domaine et des interpr etations des

constantes et des pr edicats consid er es. Dans certains cas on na pas besoin de toute

cette information pour evaluer une formule dans un mod`ele. Lid ee de lexercice etait

didentier quelle information il est n ecessaire de conna 1tre pour pouvoir evaluer une

formule donn ee.

Exercice 36 Soit D lunivers du discours qui consiste en trois individus : Ber-

trand Russell, Virginia Woolf et Pablo Picasso. On consid`ere deux pr edicats P et

C avec la cl e de traduction

4Souvent on suppose que le domaine dun modele est non vide. Si on fait cette hypothese, alors dans

le cas particuliere ou I(P ) = la connaissance de I(P ) sut pour inf erer que l enonc e x P x est vrai ;

car dans ce cas il existe forc ement au moins un individu dans D dehors de I(P ).

6

" P x : x est un po`ete

" Cxy : x cite y.

Soit I une fonction dinterpr etation selon laquelle Russell et Picasso (mais non pas Woolf)

appartiennent `a lextension I(P ) de P tandis que linterpr etation I(C) de C est

speci ee comme suit : Russell est reli e a Woolf selon la relation I(C), Woolf est reli ee a

Picasso selon cette relation et enn Picasso est reli e `a Russell selon cette relation (mais

il ny pas des autres individus reli es selon la relation en question). On note M le mod`ele

(D, I).

Pour chacun des enonc es suivants, sp eciez quel enonc e fran cais est repr esent e par

l enonc e logique en question ; ensuite d eterminez la valeur de v erit e de l enonc e logique

dans le mod`ele M selon la s emantique objectuelle. Expliquez de fa con d etaill ee pourquoi

l enonc e en question a cette valeur de v erit e.

Solution : Pour commencer, on note que le domaine D = {Russell, Woolf, Picasso} et

linterpr etation I est d enie comme suit :

" I(P ) = {Russell, Picasso}

" I(C) = {(Russell, Woolf), (Woolf, Picasso), (Picasso, Russell)}.

(i) x P x :

Quelquun nest pas un poete (ou : Pas tout le monde est un poete).

On a M |= x P x. En eet Woolf exemplie la formule P x dans le mod`ele

M (symboliquement M, x 7 Woolf |= P x), car Woolf / I(P ).

(ii) xCxx :

Quelquun se cite lui-m eme.

M 6|= xCxx, car pour aucun Z D, on na (Z, Z) I(C). Eectivement

(Russell, Russell) / I(C) et (Woolf, Woolf) / I(C) et (Picasso, Picasso) /

I(C).

(iii) xyCxy :

Quelquun cite quelquun.

On a M |= xyCxy. Par exemple le couple (Russell, Woolf) exemplie la

formule Cxy dans M, symboliquement M, x 7 Russell, y 7 Woolf |= Cxy,

7

parce que (Russell, Woolf) I(C).

(iv) xyCxy :

Tout le monde cite quelquun.

On a M |= xyCxy. Pourquoi ? Parce que pour tout Z D on a

M, x 7 Z |= yCxy.

Si Z = Russell, on peut assigner Woolf `a la variable y ; si Z = Woolf, on

peut assigner Picasso a y ; et si Z = Picasso, on peut assigner Russell a y.

Eectivement on a :

" M, x 7 Russell, y 7 Woolf |= Cxy

" M, x 7 Woolf, y 7 Picasso |= Cxy

" M, x 7 Picasso, y 7 Russell |= Cxy

(v) x(P x ' y(P y ' Cxy)) :

Quelque poete cite quelque poete.

On a M |= x(P x ' y(P y ' Cxy)), car Picasso exemplie la formule

(P x ' y(P y ' Cxy)), c-`a-d Picasso exemplie la formule P x et Picasso exemplie la formule y(P y ' Cxy). Et pourquoi

est-ce quon a M, x 7 Picasso |= y(P y ' Cxy) ? Puisque le couple (Picasso,

Russell) exemplie la formule (P y ' Cxy), plus pr ecisement parce que las-

signation x 7 Picasso, y 7 Russell exemplie cette formule : eectivement

Russell I(P ) et (Picasso, Russell) I(C).

(vi) x(P x y(P y ' Cxy)) :

Tout poete cite quelque poete.

On a M 6|= x(P x y(P y ' Cxy)), puisque Russell nexemplie pas la

formule (P x y(P y ' Cxy)). Pourquoi ? Parce que Russell exemplie la

formule P x dans M mais il nexemplie pas la formule y(P y ' Cxy)) dans

M. Et pourquoi on a M, x 7 Russell 6|= y(P y ' Cxy)) ? Puisque pour toute

individu Z D, on a

8

M, x 7 Russell y 7 Z 6|= (P y ' Cxy))

Si Z = Russell lui-m eme, on na pas (Z, Z) I(C) [(Russell, Russell) / I(C)] ;

si Z = Woolf, Z / I(P ) ; et si Z = Picasso, on na pas

(Russell, Z) I(C) [(Russell, Picasso) / I(C)]. Donc peu importe quel in-

dividu Z on assigne `a y, lassignation x 7 Russell, y 7 Z nexemplie pas

toutes les deux formules P y et Cxy.

Exercice 37

(1) D eterminez les valeurs de v erit e des enonc es suivantes dans le mod`ele M sp eci e

dans Exercice 36 :

Solution :

(i) x x = x. Vrai : Par ex. lindividu Woolf exemplie la formule x = x ; plus

sp eciquement M, x 7 Woolf |= x = x.

(ii) xy x = y. Vrai : On a :

" M, x 7 Woolf |= y x = y, et

" M, x 7 Russell |= y x = y et

" M, x 7 Picasso |= y x = y,

puisquon a :

" M, x 7 Woolf, y 7 Woolf |= x = y, et

" M, x 7 Russell, y 7 Russell |= x = y, et

" M, x 7 Picasso, y 7 Picasso |= x = y.

(2) En utilisant la cl e de traduction

" M x : x est un roi,

" Cx : x est chauve,

repr esentez les enonc es suivants en termes de la logique des pr edicats :5

Solution :

(i) Il existe un roi : xM x

(ii) Un roi est chauve : x(M x ' Cx)

5Pour (iii) et (iv) on a besoin du pr edicat didentit e.

9

(iii) Il existe exactement un roi : x(M x ' y(M y y = x))

Une autre r eponse possible ( equivalente) : (xM x ' xy(M y y = x)).

(Ici le terme gauche de la conjonction dit il existe au moins un roi et le

terme droit dit il existe au plus un roi .)

(iv) Il existe exactement un roi et il est chauve :6

x(M x ' y(M y y = x) ' Cx)

Une autre r eponse possible ( equivalente) :

x(M x ' y(M y y = x)) ' z(M z Cz).

( Il existe un et un seul roi et tous les rois sont chauves .)

6Notez que cela est une paraphrase `a la Russell de l enonc e Le roi est chauve qui utilise une

description d enie, `a savoir le roi .