Cours de Logique - Logique des propositions et logique des prédicats

8/8/2019 Cours de Logique - Logique des propositions et logique des prdicats

1/22

Logique des propositions et logique des prdicats

Notes de cours

Jrme Champavre

Version du 7 mars 2007

Table des matires

Introduction 1

1 Logique des propositions 21.1 Syntaxe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Smantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.3 Consistance, inconsistance et validit . . . . . . . . . . . . . . 51.4 Consquence logique . . . . . . . . . . . . . . . . . . . . . . . 71.5 Principe de rsolution . . . . . . . . . . . . . . . . . . . . . . 91.6 Chanage avant et chanage arrire . . . . . . . . . . . . . . . 15

1.7 Axiomatisation . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2 Logique des prdicats 182.1 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.2 Logique et thorie des ensembles . . . . . . . . . . . . . . . . 21

Rfrences 21

Introduction

La logique classique sert exprimer des noncs auxquels on attribue

une valeur dite de vrit : un nonc est soit vrai soit faux et il ny a pasdautre valeur possible. Par exemple quand je dis que la Terre est plate ,on peut sans problme attribuer la valeur faux cet nonc.

En logique classique, cest--dire la logique propositionnelle et la logiquedu premier ordre, on ne sintresse pas la dimension temporelle ou spatiale,ni lincertitude dun nonc. En dautres temps, affirmer la Terre estplate tait vrai ! On parle de la vrit compte tenu dun monde possible.Par exemple, il fait beau est vrai (ou faux?) ici et maintenant, cest--dire dans le monde que je suis en train de considrer, mais dans un autre

1


2/22

monde (un autre lieu et/ou un autre moment), cet nonc peut avoir une

valeur contraire.

1 Logique des propositions

Dans la logique propositionnelle, on tudie les relations entre des non-cs, que lon va appeler propositions ou encore des formules. Ces relationspeuvent tre exprimes par lintermdiaire de connecteurs logiques quipermettent, par composition, de construire des formules syntaxiquement cor-rectes. On trouve principalement : la conjonction, la disjonction (inclusive),limplication, lquivalence et la ngation.

1.1 Syntaxe

Sintresser la syntaxe de la logique propositionnelle, cest considrerles formules qui sont bien crites. Pour cela, on se donne un alphabet, i.e.un ensemble de symboles, avec :

un ensemble V = {p,q,r,...} dnombrable de lettres appeles va-riables propositionnelles. Il sagit des propositions atomiques tellesque par exemple 6 est divisible par 2 .

les constantes vrai et faux. un ensemble (fini) de connecteurs logiques : , , , , les parenthses (, )

Parmi les mots que lon peut crire avec cet alphabet, on va regarder ceuxqui correspondent des expressions logiques bien formes, autrementdit les formules que lon a voques en introduction, et que lon dfinit(inductivement) ainsi :

1. toutes les propositions atomiques, i.e. p , q , r , . . . , sont des expressionsbien formes ;

2. si A est une expression bien forme, alors A est une expression bienforme;

3. si A et B sont deux expressions bien formes, alors (A B), (A B),(A B) et (A B) sont des expressions bien formes ;

4. il ny a pas dautres expressions bien formes que celles des rglesprcdentes.

Par exemple (((p q) (r s)) q) est une expression bien forme,tandis que pqr t( ne lest pas. Dans la suite, on ne considre que desexpressions bien formes.

1.2 Smantique

Sintresser la smantique de la logique propositionnelle, cest dtermi-ner la valeur de vrit dun nonc, cest--dire dune formule, dans le cadre

2


3/22

dun de ses mondes possibles. On parle de linterprtation dune formule :

il sagit plus concrtement daffecter une valeur vrai ou faux chacune desvariables propositionnelles qui la compose. Pour une formule n variables,il y a 2n mondes possibles.

1.2.1 Tables de vrit

On utilise ce quon appelle des tables de vrit pour raliser cetteinterprtation. Si p et q sont des propositions, on a :

Ngationp p

vrai faux

faux vrai

Conjonctionp q (p q)

vrai vrai vrai

vrai faux faux

faux vrai faux

faux faux faux

Prenons par exemple pour p la proposition 6 est divisible par deux et pour q la proposition 4 est un nombre premier . Dans notre monde la

premire affirmation est vraie, la seconde est fausse. Linterprtation I(p)vaudra donc vrai et I(q) vaudra faux. Si lon regarde linterprtation dela conjonction de ces deux propositions I(p q), cela revient considrerI(p) I(q), soit vrai faux. La table de vrit nous indique que le rsultatest faux.

Disjonction inclusive

p q (p q)vrai vrai vrai

vrai faux vrai

faux vrai vrai

faux faux faux

La disjonction inclusive correspond au et/ou de la langue. Il suffitque lune des deux propositions soit vraie pour que les deux ensembles lesoient.

3


4/22


5/22

implique C soit faux est lorsque H est vrai et C est faux. Dans tous les

autres cas, la rgle est que lnonc est vrai.

1.3 Consistance, inconsistance et validit

1.3.1 Dfinitions

Modle On appelle modle une interprtation pour laquelle une formuleest vraie. Par exemple p = faux, r = vrai, s = faux est un modle de(p (r s)).

Consistance On dit quune formule A est consistante, ou satisfiable,sil existe une interprtation de ses variables propositionnelles qui la rendevraie. Autrement dit A est consistante si et seulement si A a un modle.(p (r s)) est une formule consistante.

Inconsistance Une formule pour laquelle il nexiste pas dinterprtationqui la rende vraie est dite inconsistante, ou encore insatisfiable, ou plussimplement fausse. (p p) est inconsistante :

p p (p p)

vrai faux faux

faux vrai faux

Validit Si une formule A est vraie pour nimporte quelle interprtationde ses variables propositionnelles, on dit quelle est valide. On dit encoreque A est une tautologie et on le note |= A. (p p) est une tautologie :

p p (p p)vrai faux vrai

faux vrai vrai

Il sagit ici du principe du tiers-exclu dont on se sert implicitement enmathmatiques pour faire un raisonnement par labsurde. Il existe dautrestautologies dont on se sert frquemment :

|= (A A) et |= (A A) identit|= (A A) tiers-exclu|= (A A) non contradiction|= (A A) double ngation

En logique classique, toutes les tautologies sont quivalentes. Ce nestpas forcment le cas dans des logiques non classiques o ces principes nesont pas ncessairement admis.

En rsum :

5


6/22

Valides

Consistantes

Inconsistantes

Formules

1.3.2 quivalences logiquesIl existe un certain nombre de tautologies utilises en calcul proposition-

nel qui sont parfois qualifies dquivalences logiques standards. Ellessont prsentes ci-dessous.

|= [(A B) (B A)] commutativit|= [(A B) (B A)] . . .|= [(A B) (B A)] . . .|= [((A B) C) ((A (B C))] associativit|= [((A B) C) (A (B C))] . . .|= [((A B) C) (A (B C))] . . .

|= [((A B) C) ((A C) (B C))] distributivit|= [((A B) C) ((A C) (B C))] . . .|= [(A (A B)) A] absorption|= [(A (A B)) A] . . .|= [(A A) A] idempotence|= [(A A) A] . . .

|= [(A B) (A B)] lois de Morgan|= [(A B) (A B)] . . .|= [(A B) (A B)] implication*|= [(A B) (A B)] . . .|= [(A B) ((A B) (B A))] quivalence|= [(A B) ((A B) (A B))] . . .

* Table de vrit prouvant cette quivalence logique :

A B (A B) A (A B)vrai vrai vrai faux vrai

vrai faux faux faux faux

faux vrai vrai vrai vrai

faux faux vrai vrai vrai

6


7/22

|= [(A B) (B A)] contraposition

|= [(A (B C)) ((A B) (A C))] autodistributivit|= [(A (B C)) (B (A C))] import-export|= [((A B) (B C)) (A C)] transitivit

1.4 Consquence logique

Jusqu prsent, nous nous sommes concentrs sur laspect de reprsen-tation des connaissances en terme de logique propositionnelle. En logique,et plus spcifiquement en Intelligence Artificielle, on est intress par desprocdures de raisonnement. La question centrale est : partir dun certainnombre de connaissances, que peut-on dduire ? Et comment peut-on le d-duire? Des questions importantes sensuivent : le principe selon lequel jeraisonne est-il correct ce que jai dduit est vraiment vrai et est-ilcomplet suis-je sr de pouvoir tout dduire?

Le principe du raisonnement logique est la relation de consquence lo-gique entre les noncs, lide quun nonc dcoule logiquement dun autrenonc. Par exemple vous savez qu la dernire sance du cours vous aurezun contrle. Vous savez galement quen gnral un contrle aboutit unenote. Vous en dduisez logiquement que vous aurez une note la fin ducours.

Contrle, Contrle NoteNote

1.4.1 Dfinition

Soit {F1, . . . , F n} un ensemble de formules. On dit quune formule Cest une consquence logique de lensemble {F1, . . . , F n}, que lon crit{F1, . . . , F n} |= C, si toute interprtation rendant vraies les formules F1,. . . , F n simultanment, rend vraie la formule C. Autrement dit, tout modlede {F1, . . . , F n} est un modle de C. Dans le petit exemple prcdent, nousavions {Contrle, Contrle Note} |= Note.

Contrle Contrle Note Notevrai vrai vrai

vrai faux faux

faux vrai vrai

faux vrai faux

1.4.2 Proprits

La notion de consquence logique est intimement lie celle de tauto-logie. En fait si par exemple une formule A est une tautologie cest parce

7


8/22


9/22

La table de vrit est donc un moyen sr pour contrler la validit dune

dduction logique. Nanmoins, comme nous lavons dj signal, son prin-cipale inconvnient rside dans le fait que cest une mthode inefficace enpratique car pour trouver un modle nous pouvons numrer jusqu 2n

interprtations, n tant le nombres de variables propositionnelles prsentsdans lensemble de formules considr.

1.5 Principe de rsolution

La consquence logique telle que nous lavons vue jusquici t prsentede manire smantique. En effet, nous avons utilis les tables de vrit pourinterprter un ensemble de formules logiques et vrifier quon pouvait en

dduire une autre dont la valeur est vraie dans les modles o chacun desprmisses est consistant.La dduction logique peut en ralit trs bien seffectuer sans connatre

les valeurs de vrit associes aux variables propositionnelles que lon mani-pule. Pour cela, on utilise des mthodes purement syntaxiques, cest--diremanipulant directement les symboles de la logique au moyen dun systme base de rgles. Les objets drivs par lapplication de ces rgles sont appelsthormes, not A (A est un thorme). On montre que dans un telsystme correct et complet, les thormes sont exactement les tautologies :

Si A alors |= A correctionSi |= A alors A compltude

Pour rsoudre un problme de logique, on peut appliquer diffrents sch-mas de raisonnement, ou rgles dinfrence. Dans lexemple {Contrle,Contrle Note} |= Note, le schma utilis sappelle modus ponens.

Nous aurions pu raisonner diffrement, en partant de la ngation de laconclusion, cest--dire Note, associe notre connaissance Contrle Note. En utilisant la rgle dite du modus tollens, nous avons {Contrle Note, Note |= Contrle}. Cela tant contradictoire avec le fait que noussavons Contrle, nous en dduisons ncessairement Note.

Contrle Note, NoteContrle

Parmi les divers schmas de raisonnement existants, nous allons nousconcentrer sur la rgle de rsolution, dont le modus ponens et le modustollens sont en fait des cas particuliers. Cette rgle dinfrence sexprimeainsi :

X A, X B

A B

9


10/22

Pour illustrer ce schma, considrons lensemble suivant de propositions :

{ Julien est la Maison ou il est au Cinma , Julien nest pas la Maisonou il est au Travail }. Si Julien est la maison, il est au Travail estncessairement vrai ; de mme sil nest pas la maison, il est au Cinma est ncessairement vrai. Donc il est ncessairement au cinma ou au travail.

1.5.1 Forme clausale

Le principe de rsolution sapplique plus gnralement un ensemble declauses.

Dfinitions

Un littral est une variable propositionnelle (par ex. p) ou la ngationdune variable propositionnelle (par ex. p). Une clause est une disjonction de littraux (par ex. p q r). On

note la clause vide. Un ensemble de clauses est la conjonction de toutes les clauses

quil contient (par ex. {p q r, p q, p r} est le conjonction dedisjonctions (p q r) (p q) (p r)).

La rsolvante de deux clauses correspond la clause rsultant delapplication de la rgle de rsolution sur ces deux clauses. Dans notreexemple prcdent, Cinma Travail est la rsolvante de Maison Cinma et Maison Travail. Dans le cas gnral, on aura :

x1 xi xn, y1 yj ym

x1 xi1 xi+1 xn y1 yj1 yj+1 ym

o xi et yj sont des littraux complmentaires (par exemple p et p).La calcul de la rsolvante est lunique rgle dinfrence pour le principe de

rsolution. Nous constatons que cette rgle ne sapplique que sur une formebien particulire de formules, la clause, qui correspond une disjonctionde littraux. Nous avons observs en TD que toutes les formules logiquespeuvent scrire en utilisant uniquement un nombre restreint de connecteurs.

Proprit Pour rsoudre un problme de logique avec le principe de rso-lution, nous allons donc devoir transformer les noncs et les mettre sous laforme de conjonctions de clauses, qui ne sont composes que de la ngation(), de la disjonction () et de la conjonction (). Cest ce que lon appellela mise sous forme normale conjonctive dune formule logique, renduepossible par la proprit ci-dessous.

Toute formule admet une forme clausale qui lui est quivalente.

Par exemple, si lon reprend lnonc Si Didier est lauteur de ce bruit,il est stupide ou dpourvu de principes , exprim par la formule (D

10


11/22

(S P)), sa forme normale conjonctive sera lunique clause D S P. On

utilise simplement le fait que (A B) (A B).

1.5.2 Mthode de transformation

Pour mettre une formule sous forme clausale, on sappuie sur les quiva-lences logiques standards que nous avons dj vues, en suivant les tapes delalgorithme suivant.

1. limination de : remplacement de (X Y) par (X Y)(Y X).

2. limination de : remplacement de (X Y) par (X Y).

3. La forme normale conjonctive exige que la ngation napparaissent

que dans les littraux. On utilise donc lannulation de la double nga-tion ainsi que les rgles de rcriture drives des lois de Morgan : remplacement de X par X; remplacement de (X Y) par (X Y) ; remplacement de (X Y) par (X Y).

4. Des trois tapes prcdentes, on obtient une expression ne contenantplus que des et des imbriqus. On applique auntant de fois quencessaire les lois de distribution (X (Y Z)) ((X Y) (X Z))et (X (Y Z)) ((X Y) (X Z)).

Lexpression obtenue la fin de cette procdure est une forme clausalequivalente la formule de dpart.

Remarques Les clauses comportant deux littraux opposs sont valides (tiers-

exclu) et peuvent donc tre supprimes (par ex. p q r q). On peut aussi supprimer les rptitions dun littral au sein dune

mme clause (par ex. p q r p quivaut p q r). Si dans une formule clausale une clause Ci est incluse dans une clause

Cj alors la clause Cj peut tre supprime (la valeur de la conjonctiondes deux clauses ne dpend que de la valeur de Ci). Par exempleCi = p q r et Cj = p s t q r.

Exemple Rsolution dune nigme par la logique des propositions.

Vous tes perdus sur une piste dans le dsert. Vous arrivez unebifurcation. Chacune des deux pistes est garde par un sphynxque vous pouvez interroger. Les pistes peuvent soit conduire une oasis, soit se perdre dans le dsert profond (au mieux, elleconduisent toutes une oasis, au pire elles se perdent toutes lesdeux).A. Le sphynx de droite vous rpond : Une au moins des deux

pistes conduit une oasis.

11


12/22

B. Le sphynx de gauche vous rpond : La piste de droite se

perd dans le dsert. C. Vous savez que les sphynx disent tous les deux la vrit, ou

bien mentent tous les deux.

On pose :D : Il y a une oasis au bout de la route de droite. G : Il y a une oasis au bout de la route de gauche.

On a :

1. A = D G

2. B = D

3. A B (formule F quon cherche vrifier)

Mise sous forme normale conjonctive :F = A B

= (A B) (B A)

= ((D G) D) (D (D G))

= ((D G) D) (D (D G))

= ((D G) D) (D (D G))

= (D D) (G D) (D D G)

= (D) (D G) (D G)

= (D) (D G)

On aboutit lensemble de clauses C = {D, D G}. Lapplication de largle de rsolution nous indique que la route de gauche conduit effectivement une oasis :

D, D G

G

1.5.3 Rsolution par rfutation

Pour rsoudre un problme de logique par la mthode de rsolution, onsappuie sur le thorme de rfutation que nous avons prsent plus haut, savoir :

Une formule C est la consquence logique dun ensemble de formulesF = {H1, . . . , H n} si et seulement si F {C} est inconsistant.

La stratgie de rsolution est donc la suivante : si ce nest pas daj fait,on met sous forme normale conjonctive lensemble des prmisses, ainsi que langation de la consquence logique que lon cherche prouver. Puis, laidede lunique rgle dinfrence de la rsolution, on cherche mettre en videnceune contradiction dans la formule H1 Hn f nc(C). Chaque pas decalcul va enrichir lensemble des clauses qui constitue en fait notre base deconnaissances. On peut rsumer lapproche dans lalgorithme suivant.

12


13/22

1. Choisir deux clauses dont on peut calculer la rsolvante et la calculer

effectivement.2. Si aucune des deux conditions ci-dessous nest remplie, rpter ltape

1. Aucune nouvelle clause ne peut-tre ajoute la base de connais-

sances : dans ce cas, C nest pas une consquence logique de F. La rsolvante produite est la clause vide : dans ce cas, F a pour

consquence logique C.

La clause vide rsulte de lapplication de la rgle de rsolution au casparticulier o les deux clauses constituent des littraux contraires :

X, X

Exemple Considrons lexemple de Didier. On dispose des connaissancessuivantes : D (S P), S et P. Ramen sous forme clausale, on a{D S P, S, P}. On cherche dduire D. On en prend donc langation, soit D, et on vrifie la consistance de {D S P, S, P, D}.

D

D P

D S P S

P

D

Exercice Montrons {p q r, p q r, q r} |= r laide de la mthodede rsolution par rfutation.

Ensemble de dpart {p q r, p q r, q r, r}Premier pas {p q r, p q r, q r, r, q}

Deuxime pas {p q r, p q r, q r, r, q, q r}Troisime pas {p q r, p q r, q r, r, q,q r, r}Quatrime pas {p q r, p q r, q r, r, q, q r,r, }

1.5.4 Correction et compltude

Validit de la rsolution

13


14/22


15/22

La clotre C(E) est un ensemble fini : on ne peut construire quun nombre

fini de clauses distinctes avec un nombre fini de littraux. La taille duneclause est limite par le nombre de variables propositionnelles considresdans lensemble E car les copies multiples de littraux sont supprimes. Uneconsquence immdiate de cette remarque est que lalgorithme termine.

Remarque La rgle de rsolution est complte dans un sens spcialise.Cela signifie que lon ne peut pas gnrer de nouvelles connaissances. Parexemple si lon connat simplement A, on ne peut pas dduire la consquenceA B, ce qui serait pourtant correct. En effet, on a {A} |= A B !

A B (A B) (A (A B))

faux faux faux vraifaux vrai vrai vrai

vrai faux vrai vrai

vrai vrai vrai vrai

En revanche, grce au thorme de rfutation, on peut rpondre toutequestion, en particulier : {A} |= A B ? On doit montrer que lensemble{A, (A B)} est soit inconsitant (la clause vide est produite), soit clos parrsolution (toutes les clauses sont produites et on ne peut plus en produiredautre). Dans notre exemple, lensemble volue ainsi :

{A, A B} (calcul prliminaire) {A, A, B} (forme clausale) {A, A, B, } (rsolution)

Lensemble est inconsistant donc on a montr {A} |= A B.

1.6 Chanage avant et chanage arrire

1.6.1 Clauses de Horn

Une clause de Horn est une disjonction de littraux, cest--dire enfait une clause dont un seul au maximum de ses littraux est positif. Parexemple, p q r, s r ou encore simplement le littral t sont desclauses de Horn, tandis que p q r nen est pas une.

Lide davoir ce genre de clauses est quon peut les crire comme uneconjonction de littraux positifs impliquant un littral positif unique. Parexemple p q r est logiquement quivalent (p q) r. La partiese situant gauche de limplication sappelle la prmisse, et la partie sesituant sa droite la conclusion. Une autre faon de nommer prmisse etconclusion est la suivante : on appelle corps lensemble des littraux ngatifsde la clause, et tte son unique littral positif lorsquil existe.

Corps

(p q)

Tte

r

15


16/22

On appelle clauses dfinies celles ayant exactement un littral positif.

Par exemple, p q r ou bien t sont dfinies, alors que s r ne lestpas.Un fait est une clause de Horn dfinie dpourvue de littraux ngatifs.

Par exemple r est un fait, et p q r et s r nen sont pas.Lintrt de mettre une formule sous la forme dune clause de Horn est es-

sentiellement pratique. En effet, un grand nombre dnoncs peuvent scrireuniquement en employant ce type de clauses, comme par exemple lnoncci-dessous.

Les gens qui ont la rougeole doivent prendre le mdicament X(r x).

Les gens qui ont de la fivre et des points rouges au fond de lagorge ont la rougeole ((f g) r).

Ceux pour qui la temprature est au-dessus de 38sont consi-drs comme ayant de la fivre (s f).

Armand a des points rouges au fond de la gorge et a une tem-prature de 395 (g s).

Il existe essentiellement deux algorithmes dinfrence pour raliser desdductions sur des clauses de Horn. Ils sappellent chanage avant et cha-nage arrire, et sont tout fait naturels pour les humains. Ils prsententen outre lavantage deffectuer un calcul de rsolution en temps linaire parrapport la taille de lensemble des connaissances.

Les clauses de Horn constituent donc une restriction3

efficace dans denombreux cas pratiques de problmes de raisonnement en logique.

1.6.2 Chanage avant

Le chanage avant consiste combiner des faits connus pour en dduirede nouveaux. Par exemple, de lnonc pos prcdemment, peut-on dduirele fait x ? Nous aurons la chane dinfrences suivante :

s, s f

f,g, (f g) r

r, r x

xde r on dduit x

de f et g on dduit r

de s on dduit f

Le principe du chanage avant est simple : si toutes les prmisses duneimplication sont connues, on ajoute la conclusion la base de connaissances.On peut rpter ce processus jusqu tant que :

soit la requte recherche est produite (par exemple x) ; soit on ne peut rien dduire de plus.

3Il nest pas possible de mettre toutes les propositions sous la forme de clauses de Horn.

16


17/22

Lalgorithme est donc identique lalgorithme de rsolution, en utilisant

simplement la rgle du modus ponens, qui nest en fait rien dautre quuncas particulier de la rgle de rsolution, comme nous lavions dj mentionn.Dans le cadre du chanage avant, le raisonnement est guid par les

connaissances dj acquises. On peut dduire des connaissances jusquun point fixe, cest--dire un tat partir duquel on ne peut plus rieninfr de nouveau en appliquant le modus ponens.

1.6.3 Chanage arrire

Dans le chanage arrire, on part du but que lon veut atteindre, autre-ment dit un fait que lon cherche dduire de nos connaissances. Exemple

de raisonnement :x est-il un fait connu ? Non. On considre alors les rgles dans lesquellesx est une consquence, cest--dire celles o x est la tte. Nous avons r x.Il faut dsormais prouver r par chanage arrire.

r ? f g r f? s f s ? oui, donc f g ? oui, donc r

Nous avons satisfait toutes les dpendances en amont pour x par chanagearrire, de ce fait on dduit x.

Le raisonnement dans le chanage arrire est guid par le but. Le

moteur dinfrence de PROLOG fonctionne essentiellement sur ce principe.

1.7 Axiomatisation

La logique propositionnelle est une thorie. Cela signifie qu partir dequelques axiomes et rgles de dduction, on peut dduire toutes les formulesvalides, autrement dit les thormes. On considre les expressions bien for-mes utilisant une ensemble fini de variables propositionnelles, les oprateurs et , ainsi que les parenthses, et on pose les trois axiomes suivants :

1. (p (q p)) (consquence de lhypothse)

2. ((p (q r)) ((p q) (p r))) (autodistributivit)

3. ((p q) (q p)) (contraposition partielle)On se donne comme rgles de dduction la rgle de substitution et le modusponens.

On peut obtenir le thorme (p p) en appliquant la dmonstrationci-dessous.

(1) (p (q p)) axiome 1(2) (p ((q p) p)) substitution de q parq p (axiome 1)(3) ((p ((q p) p)) ((p (q p)) (p p))) substitution

de q par(q p) et de r parp (axiome2)

17


18/22

(4) ((p (q p)) (p p)) modus ponens sur les lignes (2) et (3)

(5) (p p) modus ponens sur les lignes (1) et (4)

2 Logique des prdicats

La logique propositionnelle ne permet de dcrire que des constructionssimples du langages, consistant essentiellement en des oprations boolennessur les propositions. On peut, grce elle, tudier dans un cadre formel lavaleur de vrit de formules relativement peu expressives. Insuffisante pourreprsenter des procds de langage effectivement utiliss en informatique,linguistique ou en mathmatiques, elle sert nanmoins de base la construc-tion de systmes formels plus expressifs. La formalisation du raisonnementsuivant lui chappe :

Certains tudiants assistent tous les cours. Aucun tudiant nassiste un cours inintressant.Peut-on conclure que tous les cours sont intressants ?

En logique propositionnelle, on peut raliser la dduction suivante :

Le cours dIA est intressant,Un cours intressant attire de nombreux tudiants

Le cours dIA attire de nombreux tudiants

On peut facilement effectuer le mme raisonnement avec une autre pro-

position : le cours de sociologie est intressant . On pourrait envisagerdes choses intressantes dans un autre contexte. Par exemple en remplaant cours de quelque chose par muse de quelque chose et tudiants par touriste , cela fait toujours du sens. Mais cela ncessite dcrire unenouvelle proposition chaque fois.

En fait, on aimerait dissocier intressant de cours ou muse ,de telle sorte que ce soit une proprit du cours qui na pas ncessairementla mme valeur selon que le cours soit de lIA ou de la sociologie. On vou-drait aussi pouvoir exprimer des relations entre plusieurs objets, par exempleque la salle du cours de sociologie est en face de la salle de TD dIA. En-fin, on souhaiterait exprimer que des proprits sont vraies pour certains

tudiant ou pour tous les cours .Le logique des prdicats, ou logique du premier ordre est par na-

ture plus expressive que la logique des propositions, et permet de reprsenterces types de connaissances relatifs des environnements complexes. Elle estconstruite partir de la logique propositionnelle et sinspire du langage na-turel pour dfinir :

des objets, par exemple IA , sociologie , Julien des fonctions sur ces objets, TD dIA , cours de sociologie des relations entre ces objets, Julien assiste au cours dIA

18


19/22

Tout comme en logique propositionnelle, on sintresse la validit des re-

lations existant entre les objets.

2.1 Structure

Pour crire un nonc en logique du premier ordre, nous allons utiliserun ensemble de symboles plus riche quen logique des propositions. On sedonne :

un ensemble (dnombrable) de constantes {a , b , c , . . .} ; un ensemble (dnombrable) de variables {x , y , z , . . .} ; un ensemble (dnombrable) de fonctions {f , g , h , . . .} ; un ensemble (dnombrable) de prdicats, ou relations {P , Q , . . .} ;

des connecteurs logiques, {, , , , . . .}, ainsi que les parenthses( et ) ; les quantificateurs universel et existentiel (voir plus loin).

2.1.1 Termes

Un terme est une expression logique qui renvoie un objet. Les cons-tantes, comme Julien ou sociologie , ainsi que les variables, sontdes termes. Un terme compos est construit laide dune fonction, parexemple pre(Julien) ou cours(IA) .

2.1.2 Formules

Une formule en logique des prdicats se construit similairement uneformule en logique des propositions. En fait un prdicat va jouer un rleanalogue une proposition. On doit en plus prendre en compte les quanti-fications :

1. P(x1, . . . , xn) est une formule atomique ;

2. t1 = t2 est une formule atomique4 ;

3. si F est une formule, alors F est une formule;

4. si F et G sont des formules, alors (F G), (F G), (F G), etc. sontdes formules;

5. si F est une formule et x une variable, alors x.F et x.F sont desformules.

2.1.3 Quantificateurs

Le quantificateur universel exprime le fait que tous les lments dunensemble dobjets sur lequel sexprime un prdicat vrifient ce prdicat, cest-

4Loprateur dgalit permet de comparer deux termes.

19


20/22

-dire x.P(x) est vrai revient considrer que P(a1) P(an) est vrai,

si {a1, . . . , an} est le domaine de x5.De la mme faon, le quantificateur existentiel exprime le fait quaumoins un des lments dun ensemble dobjets sur lequel sexprime un pr-dicat vrifie ce prdicat, cest--dire x.P(x) est vrai revient considrerque P(a1) P(an) est vrai, si {a1, . . . , an} est le domaine de x.

Quantificateurs imbriqus Notons que lordre des quantificateurs nestpas anodin. En effet, tout le monde aime quelquun scrirait x . (y. Aime(x, y)), qui na pas exactement le mme sens que il y a quelquunqui est aim par tout le monde qui scrirait y . (x . Aime(x, y)).

Liens entre et On a les lois de Morgan pour les quantificateurs :

x.F x.F

x.F x.F

x.F x.F

x.F x.F

Illustrations : Tout le monde dteste les brocolis revient au mme que Il nexiste

personne qui aime les brocolis :

x.Aime(x, brocolis) x.Aime(x, brocolis)

Tout le monde aime les glaces et Il ny a personne qui naimepas les glaces sont quivalents :

x.Aime(x, glaces) x.Aime(x, glaces)

2.1.4 Exemples

Les noncs que nous voquions au dbut de cette section peuvent sex-primer avec des formules de la logique du premier ordre.

1. Certains tudiants assistent tous les cours. x.(Etudiant(x) (y.Assiste(x, y)))

2. Aucun tudiant nassiste un cours inintressant.

x.(Etudiant(x) (Assiste(x, y) Interessant(y)))

Dans la seconde formule, on constate que la variable y nest pas quanti-fie : un telle variable est dite libre. Une variable quantifie est dite lie.

5Lensemble des valeurs que peut prendre x.

20


21/22

Exercice Exprimer les noncs suivants en logique du premier ordre.

Tous les lions sont froces. x.(Lion(x) Feroce(x))

Quelques lions ne boivent pas de caf.

x.(Lion(x) Cafe(x))

Aucun singe nest soldat.

x.(Singe(x) Soldat(x))

Tous les singes sont malicieux.

x.(Singe(x) Malicieux(x))

Remarque On traduit couramment certaines expressions en logique dupremier ordre :

Tous les A sont B. : x.(A(x) B(x)) Seuls les A sont B. : x.(B(x) A(x)) Aucun A nest B. : x.(A(x) B(x)) Quelques A sont B. : x.(A(x) B(x))

2.2 Logique et thorie des ensembles

La logique du premier ordre entretient un rapport trs troit avec lathorie des ensembles. On peut en effet voir un ensemble comme une col-lection dobjets satisfaisant une certaine proprit. Ainsi, on pourra expri-mer les caractristiques dun individu par une formule de la logique desprdicats. Par exemple, x.(Femme(x) Documentaliste(x)) correspon-dra lintersection des ensembles Femme et Documentaliste. Le formulex.(Enceinte(x) Femme(x)) exprimera le fait que lensemble Enceinteest inclus dans lensemble Femme. Et ainsi de suite.

Femme

Documentaliste

Enceinte

21


22/22

Rfrences

[1] R. Lassaigne et M. de Rougemont. Logique et fondements de linfor-matique. Hermes, 1993.

[2] M.-D. Popelard et D. Vernant. lments de logique. Mmo Seuil,1998.

[3] S. Russel et P. Norvig. Intelligence artificielle (2e dition). PearsonEducation, 2006.

22

Documents

Cours de Logique - Logique des propositions et logique des prédicats