Étude et instances de systèmes de preuves ordonnées - École Jeunes Chercheurs en Programmation

Guillaume Burel

Description

Étude et instances de systèmes de preuves ordonnéesÉcole Jeunes Chercheurs en ProgrammationGuillaume BurelLORIA – Université Henri PoincaréEncadrant : Claude Kirchnerjuin 2006Guillaume Burel (LORIA/UHP) Systèmes de preuves ordonnées juin 2006 1 / 7Différentes représentations des preuves mais une notion commune : certainespreuves sont «meilleures» que d’autres : preuves sans coupures, preuves parréécriture, preuves qui appliquent la résolution sur les grands atomes enpremierCadre des systèmes canoniques abstraits (SCA) introduit par N.Dershowitz etC. Kirchner : la notion de bonne preuve est traduite par un ordre sur lespreuvesNotion de complétion abstraite qui permet de retrouver un système ayant lesbonnes propriétés; ici on va l’appliquer à la déduction modulo pour recouvrerl’élimination des coupuresIntroductionDémonstration automatique et interactive : de nombreux formalismeslogiques : séquents, preuves équationnelles, formes clausales...Guillaume Burel (LORIA/UHP) Systèmes de preuves ordonnées juin 2006 2 / 7preuves sans coupures, preuves parréécriture, preuves qui appliquent la résolution sur les grands atomes enpremierCadre des systèmes canoniques abstraits (SCA) introduit par N.Dershowitz etC. Kirchner : la notion de bonne preuve est traduite par un ordre sur lespreuvesNotion de complétion abstraite qui permet de retrouver un système ayant lesbonnes propriétés; ici on va l’appliquer à la déduction modulo pour recouvrerl’élimination des ...

Informations

• Publié par: Chiem
• Nombre de lectures: 39
• Langue: Français

Extrait

GuilL(leAIROmualruBemetèepsdHP/Uys)Seéjsodnnseroervu

LORIA – Université Henri Poincaré Encadrant : Claude Kirchner

juin 2006

Guillaume Burel

/7

Étude et instances de systèmes de preuves ordonnées École Jeunes Chercheurs en Programmation

0061uin2

éferDfiveeuaismsdonpresneséitatsetnrpernes preuv e:certainoocmmnuusenonit prs:reut’aedqus»eruelliem«tnosse rééc spareuves,prupercsuossnaueev nsioutolrasgleuremotasdn imerp nesre,prituesqureuviluqaipprasénelt itraSCs(inA)odtrptiu.NrasreDiwoh er Cadredessystèmseaconinuqsebats petiudarttseevues p leuresdrorunarrel:crnh.CiK ztte nepreboniondanot edterteriuqemreptèysaymeveounsruitnoedoc ervuse oNabstraitmplétion mndotcoiuorrlupoiqueappldéduràlai;sétéir’lavnoicbo estlan oppresnn ROAIU/PHS)syètemGuillaumeBurel(L oitasednpuocseru ouecervr éll’inim

Démonstration automatique et interactive : de nombreux formalismes logiques : séquents, preuves équationnelles, formes clausales. . .

Introduction

/76200n2uisjéennodrosevuerpeds

qsiuueevqieupalprésontlaonsulutinargselrsemotasd ieempr en deread r C preuvessanspuocseruerp,sevur r pa crééuritpre, rttseevuerpennobdeontinolar:nech N s to ueev se rp uslrrdrerunotepaadui stiaACS(aseurtsbansciqonysssmetèez C t K.ri rehswotiitparN.D)introdu ’aalnvioerqulipprporpsenci;sétéiurreloporer l couvdéculàdaomuditno trbsteaiipqumeerdnoimocetélpanoistèmeayantles bon dtreteorvurenuys esjuin20sordonné

Différentes représentations des preuves mais une notion commune : certaines preuves sont « meilleures » que d’autres :

60/27

Démonstration automatique et interactive : de nombreux formalismes logiques : séquents, preuves équationnelles, formes clausales. . .

Introduction

P)UHA/RILOl(reBuevuerpedsemètsyS desctionmina’éli uaemiull er G suoup

ppliquerionval’aéiét;scienpsorrpuvcor l repoloreurnoitudomdalàcudé aumeuill res G oupuedcsitnoimané’il veeuprdeesèmstSy)PHU/AIROL(leruB obnnpeervueetsrtchner:lanotiondelrus rp se evue toN s uiadpatenorurerd iaetsbrtreemuqpiecomiondionaplétayaemèts nob seltnroetertdsyuneruv rdsonéonjues20in/260

Démonstration automatique et interactive : de nombreux formalismes logiques :séquents, preuves équationnelles, formes clausales. . .

Introduction

7

Différentes représentations des preuves mais une notion commune : certaines preuves sont « meilleures » que d’autres : preuves sans coupures

tiru,erp ap r r éérc ,preuves ershowitzet C.Kir i)tnorudtiapNrD.sauetrbstsaiCA(Ssyssemètnacsqino emie en pr rede r Cad rgnalrsemosesdtasorélantsuontiluiuqsevueeuqilppa

artpuiodtrinA)SC(stiartsbaseuqincanoèmessystedesaCrd imrepneremes areporunrattitduuerpseevbednenno:lanotioKirchner iwztte .C .NeDsroh rusngseldnar ota senquartlolésioutp,ervuseuqaippil lial se uG puruseoc IA/U(LORurelumeB rvuocerruopoludo ndioatiniméll’ er

Introduction

Différentes représentations des preuves mais une notion commune : certaines preuves sont « meilleures » que d’autres : preuves sans coupures, preuves par réécriture (en « vallée »)

Démonstration automatique et interactive : de nombreux formalismes logiques : séquents,preuves équationnelles, formes clausales. . .

2n00267/dsemerpeS)PHètsyéennuisjesuvdoor straonabuipeiteqedermrteevurrtuo leuresdr esuvre s p ednoitoNitélpmoc ;icionval’appliqeuàralédudtcoimn ysnsmetèanayestl nnobrpseirposété

nurapetiruserdro uvre s p le ontiNo es pméledocbatsitnoequiraitetdeperm dortptiu.NrasreDwihoettz KiC.hnrcrel:natooidnbenonepreuveesttradu yssederdaCquesnoniescastèm)Ani(sCSartibats

Démonstration automatique et interactive : de nombreux formalismes logiques : séquents, preuves équationnelles,formes clausales. . .

Différentes représentations des preuves mais une notion commune : certaines preuves sont « meilleures » que d’autres : preuves sans coupures, preuves par réécriture, preuves qui appliquent la résolution sur les grands atomes en premier

Introduction

/7jseénnod26002niusdeptèmeesorreuvROAIleL(S)syU/PHmualruBe seru liuG esndupcoinimioat rvre ’llé uorrceuonmodulopdéductioalàreuqilppa’lavonci;iésétriopprnnse se ob naltemyaystèrunsouveretr

inationdescoupur rrceuorvre ’llémi ctdunmioulodouoppa’lqilpàreuédal sjuinnée62/7n200peeremdsroodvuse/UIAOR(Ltèys)SHPalliuG se leruBemu

Démonstration automatique et interactive : de nombreux formalismes logiques : séquents, preuves équationnelles, formes clausales. . . Différentes représentations des preuves mais une notion commune : certaines preuves sont « meilleures » que d’autres : preuves sans coupures, preuves par réécriture, preuves qui appliquent la résolution sur les grands atomes en premier

Cadre des systèmes canoniques abstraits (SCA) introduit par N.Dershowitz et C. Kirchner : la notion de bonne preuve est traduite par unordre sur les preuves

tiNodeonbanoartspmocitél presnnbo estlanay avnoici;sétéirpo derermetuipeiteqètemsnsyevurrtuo itcunoIntrod

0260ujniénsedrno

Notion de complétion abstraite qui permet de retrouver un système ayant les bonnes propriétés ; ici on va l’appliquer à la déduction modulo pour recouvrer l’élimination des coupures

Introduction

Démonstration automatique et interactive : de nombreux formalismes logiques : séquents, preuves équationnelles, formes clausales. . .

Différentes représentations des preuves mais une notion commune : certaines preuves sont « meilleures » que d’autres : preuves sans coupures, preuves par réécriture, preuves qui appliquent la résolution sur les grands atomes en premier

Cadre des systèmes canoniques abstraits (SCA) introduit par N.Dershowitz et C. Kirchner : la notion de bonne preuve est traduite par un ordre sur les preuves

2/7HU/AyS)P(lerIROLeuprsoveèmstdeesllaumeBuGui

<

<

Pf()

<

µPf()

P

<

7/36

[∙] Pm [∙] Cl

A

+ 5 postulats Th A= ! [Pf(A)] Cl

iujs002n)SHP/UIAsdmetèyssevuerpeeénnodroGumuBelialL(ROrule éDnfitioisn

cnulseocdsseisnosteàonsiterlajoumocaLcnoitélp tiqieuis:estditecr ecttpeorimet ∞ A edtcomplètcédurees A(fPµ∩) ∞ hT :e [⊆ 0 A l G ] C llui (TPf 0 )hA uqseiritevcsrpue p cri ] Cl : ∪{[p : A❀A (1 EMÈROÉH T } euqit liLa ). DETULÉMP C O BureaumeRIA/l(LOyStsHU)Pedrpmèserdsoveeujuesnéon/46002ni

∀q✁p.q∈µPf(Th A)

p6∈µPf(ThA)

p∈µPf(A)

Définition 1 (Preuves Critiques).

Complétion

7

:qitiiseuidtsrcete .) ED ilaLetimed ∞ A RÈÉO 1( MEMP C OTULÉ ctmolptè:e hT 0 A[⊆ cetteprocédurees H T esèmprdeveeurdsoOL(l/AIR)PHUtsyS ] Cl GuillaumeBure fPA() ∞ µ∩fPT(Ah) 0

p∈µPf(A) p6∈µPf(ThA) ∀q✁p.q∈µPf(Th A)

La complétion consiste à ajouter les conclusions des preuves critiques :

A❀A∪ {[p] Cl : p critique }

7

Complétion

Définition 1 (Preuves Critiques).

seujnoén60/4ni02