Cours-ASP

Publié par

Programmation par Answer Set Cours 1Programmation par Answer Set1 PreliminairesNous de nirons dans cette section les di erents elements du langage logique que nous utiliserons,et introduirons la notion de programme logique. Cette section donne donc la syntaxe utilisee enprogrammation par Answer Set.1.1 LangageOn considere un langage de logique du premier ordreL, sans fonctions, muni de deux types denegations :{ la negation classique, ou explicite (:).:p signi e explicitement que p est faux.{ la n par l’echec, negation as failure ou NAF en anglais (not). not p signi e que l’on apas "p vrai", c’est a dire que l’on a aucune preuve que p soit vrai.Ces deux negations peuvent se combiner. Ainsi not:p signi e que l’on a aucune preuve que p soitfaux.Nous rappelons ici quelques de nitions :Terme. Un terme t est une constante ou une variable du langageL.Atome. Un atome a est un element de la forme P (t ;:::;t ) ou t ;:::;t sont n termes, et P est un1 n 1 npredicat d’arite n.Literal. Un literal est usuellement un atome ou un atome precede d’un symbole de negation. Etantdonne que nous considerons deux types de negations, nous distinguerons les literaux classiquesdes NAF-literaux :Literal classique. Un literal classique L est un atome (a) ou un atome precede de la negationexplicite (:a). On note::L le complementaire d’un literal classique : si L = a,::L =:aet si L =:a,::L = a. Dans ce qui suit, sauf mention explicite du ...
Publié le : samedi 24 septembre 2011
Lecture(s) : 26
Nombre de pages : 10
Voir plus Voir moins
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
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.