Cours-ASP

Description

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 ...

Informations

• Publié par: Uproi
• Nombre de lectures: 27
• Langue: Français

Extrait

Programmation par Answer Set

1

Cours

Programmation

Pre´liminaires

par

Answer

Set

1

Nousd´efinironsdanscettesectionlesdiff´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´egationparl’e´chec,negation as failureouNAFen anglais (not).not psignifie que l’on a pas ”punucaaonequvreepeuai”,vr`tda’cseeu’lriqepsoit vrai. Cesdeuxn´egationspeuventsecombiner.Ainsinot¬psignifie que l’on a aucune preuve quepsoit faux. Nousrappelonsiciquelquesde´finitions: Terme.Un termetest une constante ou une variable du langageL. Atome.Un atomeadteunetsemlen´´eermfolaP(t 1 , . . . , t n u`o)t 1 , . . . , t n sontntermes, etPest un pr´edicatd’ar´eitn. ´ Lite´ral.tnEatn.ioategn´delebomysnu’de´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´lpmoc’dnuil´teralclassique:siL=a,¬.L=¬a et siL=¬a,¬.L=a. Dans ce qui suit, sauf mention explicite du contraire, lorsque nous parleronsdelit´eral,ils’agiradelite´ralclassique. 0 NAF-lit´eral.´trelanUAN-FilL(euqisslalcra´eitnltuesLtilnuuo)eddee´e´´cueprssiqlcla´era lan´egationparl’e´chec(not L).

1.2R`egles Danssaformelaplusg´en´eraleunere`glerest une formule de la forme suivante : L 1 ;. . .;L k ←L k+1 , . . . , L m , not L m+1 L, . . . , not n o`u0≤k≤m≤n L 1 , . . . , L n :lesieurspainguepluusen`rgetreidsnaxcauert´liestdontsidnO.seuqissals Tˆete.{L 1 , . . . , L k }leppale´atseeˆttedlelgeerae`´etnotH(r). Corps.{L k+1 , . . . , L n }´eelpptaselecorpslerae`lg,eteon´tedB(r). Dans ce corps, on distingue : + Corps positif.{L k+1 , . . . , L m }elpptaesele´corps positife´tnotle,er`egdelaB(r). − Corpsne´gatif.{L m+1 , . . . , L n }´lepeleepatsatifcorpsn´egnttoe´`rgeele,delaB(r). On note − not B(rseenl’)NAdelemb´tre-Filuax{not L m+1 L, . . . , not n }. Onpeutdonce´crireplusconcis´ementrnte:dlefa¸aocsniuav +− r:H(r)←B(r)B, not (r)

+ Intuitivement,cetter`eglesignifiequesichacundeslite´rauxdeB(ruaucqteuil´tdnse)eai,estvrxauer − deB(rmentsdedes´el´eiosn’lnularoasmuuorpe´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. Contrainted’int´egrit´e.SiH(r) =∅(kgleestunquelar`eo,)0tidne=e´tirge´tndei’tncnortia. Elle nepeuteˆtresatisfaitequesisoncorpsn’estpassatisfait. − Re`glepositive.SiB(r) =∅(m=nrae`lgeetsidet,l)positive, ou´ngetaoipnra’le´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 L 1 ←L 2 , . . . , L n .

1.3 Programmes Maintenantquenousavonsvucequ’estunere`gle,ilestfacileded´efinirunprogrammelogique:

D´efinition1(Programme)Unprogrammeesnsemtuneesgl.edbl`eer

Selonletypeder`eglesautoris´eesdansleprogramme,onauradiffe´rentesclassesdeprogrammes: Programme normal positif.Un programme normal positif ne comporte, comme son nom l’indique, quedesr`eglesnormalespositives.Onn’ytrouvepasdene´gationparl’e´chec,ettouteslestˆetes desr`eglesontunetunseule´l´ement. Programme normal.mmargorpnUstconstienormaleeuemtnedute´nuqimaors,leegr`snle-se’ca`-t direquetoutessesre`glesontunetunseullite´ralpourteˆte. Programmedisjonctife´tendu.enbiypetepedgrromeam’Cltsequiautoriseaussiellpsu´gnee´ar,l lane´gationparl’e´checquelesr`eglesdisjonctivesetlescontraintesd’int´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.Ondonned’aborddeuxd´efinitions: Univers de Herbrand.L’univers de Herbrand d’un programmePn,to´eU P est l’ensemble de toutes 1 les constantes apparaissant dans le programmeP. Base de Herbrand.La base de Herbrand d’un programmePt´ee,noB P est l’ensemble de tous les lite´rauxforme´sa`partirdesymbolesdepr´edicatsapparaissantdansPet de termes deU P . L’instanciationd’unere`glere´ton,Ground(rrslotaes)seunneobteglessr`eesleottueledesbm’lne remplac¸antlesvariablesderpar des termes deU P . On obtient finalement l’instanciation d’un programmePet:fa¸cdelaivanonsu [ Ground(P) =Ground(r) r∈P

1 Danslecasplusge´ne´rald’unlangageautorisantlesfonctions,l’universdeHerbrandestl’ensembledetouslestermes form´esa`partirdefonctionsetdeconstantesapparaissantdansP.

Universite´Paris-Dauphine

M2 - 2008/2009

G.Bourgne