La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Partagez cette publication

Programmation par Answer Set
1
Cours
Programmation
Pre´liminaires
par
Answer
Set
1
Nousd´enironsdanscettesectionlesdi´erentse´le´mentsdulangagelogiquequenousutiliserons, etintroduironslanotiondeprogrammelogique.Cettesectiondonnedonclasyntaxeutilise´een programmation par Answer Set.
1.1 Langage Onconside´reunlangagedelogiquedupremierordreL, sans fonctions, muni de deux types de n´egations: lane´gationclassique,ouexplicite(¬).¬psignifie explicitement quepest faux. lan´egationparle´chec,negation as failureouNAFen anglais (not).not psignifie que l’on a pas ”punucaaonequvreepeuai,vr`tdacseeulriqepsoit vrai. Cesdeuxn´egationspeuventsecombiner.Ainsinot¬psignifie que l’on a aucune preuve quepsoit faux. Nousrappelonsiciquelquesde´nitions: Terme.Un termetest une constante ou une variable du langageL. Atome.Un atomeadteunetsemlen´´eermfolaP(t1, . . . , tnu`o)t1, . . . , tnsontntermes, etPest un pr´edicatd’ar´eitn. ´ Lite´ral.tnEatn.ioategn´delebomysnude´de´ce´ranotemuonutamopelestusuellementuUtilnare´ donne´quenousconsid´eronsdeuxtypesden´egations,nousdistingueronsleslite´rauxclassiques desNAF-lit´eraux: Lite´ralclassique.lalciqssitnlra´eUeuLest un atome (aec´eepr´atomouunitnoe´aglena´dde) explicite (¬a). On note¬.Lleemtniaere´lpmocdnuil´teralclassique:siL=a,¬.L=¬a et siL=¬a,¬.L=a. Dans ce qui suit, sauf mention explicite du contraire, lorsque nous parleronsdelit´eral,ilsagiradelite´ralclassique. 0 NAF-lit´eral.´trelanUAN-FilL(euqisslalcra´eitnltuesLtilnuuo)eddee´e´´cueprssiqlcla´era lan´egationparle´chec(not L).
1.2R`egles Danssaformelaplusg´en´eraleunere`glerest une formule de la forme suivante : L1;. . .;LkLk+1, . . . , Lm, not Lm+1L, . . . , not no`u0kmn L1, . . . , Ln:lesieurspainguepluusen`rgetreidsnaxcauert´liestdontsidnO.seuqissals Tˆete.{L1, . . . , Lk}leppale´atseeˆttedlelgeerae`´etnotH(r). Corps.{Lk+1, . . . , Ln}´eelpptaselecorpslerae`lg,eteon´tedB(r). Dans ce corps, on distingue : + Corps positif.{Lk+1, . . . , Lm}elpptaesele´corps positife´tnotle,er`egdelaB(r). Corpsne´gatif.{Lm+1, . . . , Ln}´lepeleepatsatifcorpsn´egnttoe´`rgeele,delaB(r). On note not B(rseenl)NAdelemb´tre-Filuax{not Lm+1L, . . . , not n}. Onpeutdonce´crireplusconcis´ementrnte:dlefa¸aocsniuav +r:H(r)B(r)B, not (r)
+ Intuitivement,cetter`eglesigniequesichacundeslite´rauxdeB(ruaucqteuil´tdnse)eai,estvrxauer deB(rmentsdedes´el´eiosnlnularoasmuuorpe´te,iarve´va´n)H(r) est vrai. Nous verrons plus en de´taildansquelleconditionuner`egleestsatisfaitedanslasections´emantique. +Selon les ensemblesH(r),B(r) etB(rgl`eersd:es),ondistinugpeulisuesrytep
Universite´Paris-Dauphine
M2 - 2008/2009
G.Bourgne
2
Cours
Programmation par Answer Set
R`egledisjonctive.SiH(rnadiarecteictrlsdtse)1(emtnus´preeirua`k >1),onditquele`raeelgts disjonctive. R`eglenormale.SiH(r) est un singleton (ketditleesr`egal,)1=normale. Contraintedint´egrit´e.SiH(r) =(kgleestunquelar`eo,)0tidne=e´tirge´tndeitncnortia. Elle nepeuteˆtresatisfaitequesisoncorpsnestpassatisfait. Re`glepositive.SiB(r) =(m=nrae`lgeetsidet,l)positive, ou´ngetaoipnrale´checlibrede (NAF-freeen anglais). Fait.Enfin, siB(r) =(k=m=n), on parle defaittiodeteˆeme´crofevtrˆentira.l´emUn´eelatentd pourquelar´eglesoitsatisfaite. Certains types peuvent se combiner. Ainsi uneeposrmallenor`egetivimeorafelede`lgnureets L1L2, . . . , Ln.
1.3 Programmes Maintenantquenousavonsvucequestunere`gle,ilestfacileded´enirunprogrammelogique:
D´enition1(Programme)Unprogrammeesnsemtuneesgl.edbl`eer
Selonletypeder`eglesautoris´eesdansleprogramme,onauradie´rentesclassesdeprogrammes: Programme normal positif.Un programme normal positif ne comporte, comme son nom l’indique, quedesr`eglesnormalespositives.Onnytrouvepasdene´gationparle´chec,ettouteslestˆetes desr`eglesontunetunseule´l´ement. Programme normal.mmargorpnUstconstienormaleeuemtnedute´nuqimaors,leegr`snle-seca`-t direquetoutessesre`glesontunetunseullite´ralpourteˆte. Programmedisjonctife´tendu.enbiypetepedgrromeamCltsequiautoriseaussiellpsu´gnee´ar,l lane´gationparle´checquelesr`eglesdisjonctivesetlescontraintesdint´egrit´e.
1.4 Instanciation d’un programme Danslecasge´n´eral,unprogrammepeutcontenirdesvariablesaussibienquedesconstantesdans leslite´rauxpr´esentsdanssesr`egles.Unlite´ralinstancie´estunlit´eraldonttouslestermessontdes constantes.Unere`gleinstancie´eestalorsuner`eglequinefaitintervenirquedeslit´erauxinstancie´s, etunprogrammeinstancie´estunprogrammequinecontientquedesr`eglesinstancie´es. Ilestparfoisne´cessairedetransformerunprogrammePversensaniiotansi´nceeGround(P). Nous de´taillonsicilemoyendelefaire.Ondonnedaborddeuxd´enitions: Univers de Herbrand.L’univers de Herbrand d’un programmePn,to´eUPest l’ensemble de toutes 1 les constantes apparaissant dans le programmeP. Base de Herbrand.La base de Herbrand d’un programmePt´ee,noBPest l’ensemble de tous les lite´rauxforme´sa`partirdesymbolesdepr´edicatsapparaissantdansPet de termes deUP. Linstanciationdunere`glere´ton,Ground(rrslotaes)seunneobteglessr`eesleottueledesbmlne remplac¸antlesvariablesderpar des termes deUP. On obtient finalement l’instanciation d’un programmePet:fa¸cdelaivanonsu [ Ground(P) =Ground(r) rP
1 Danslecasplusge´ne´raldunlangageautorisantlesfonctions,luniversdeHerbrandestlensembledetouslestermes form´esa`partirdefonctionsetdeconstantesapparaissantdansP.
Universite´Paris-Dauphine
M2 - 2008/2009
G.Bourgne