Bonnes démonstrations en déduction modulo - Accueil fileBonnes démonstrations en déduction modulo Soutenance de thèse Guillaume Burel Université Henri Poincaré – Loria 23

Bonnes démonstrations endéduction modulo

Soutenance de thèseGuillaume Burel

Université Henri Poincaré – Loria

23 mars 2009

Introduction Automating reasoning

Motivation

How to be sure of a complex mathematical proof?(for instance: 4-color theorem)

How to certify complex software?

formalizing and automating proofs

2


Pure logic: well-studied (Frege, Hilbert, Gentzen, etc.)

But proofs are generally done within a theoryI first-order arithmeticI pointer arithmeticI etc.

How to present these theories to get better mechanized proofsystem?

Standard way of dealing with theories: axiomatizationI For instance, Peano’s axioms for first-order arithmeticI Not adapted for proof search!

3


Pure logic: well-studied (Frege, Hilbert, Gentzen, etc.)

But proofs are generally done within a theoryI first-order arithmeticI pointer arithmeticI etc.

How to present these theories to get better mechanized proofsystem?

Standard way of dealing with theories: axiomatizationI For instance, Peano’s axioms for first-order arithmeticI Not adapted for proof search!

3


1+1=2In Γ:

∀x , x + O = x∀x y , x + s(y) = s(x + y)

∀x y , x = y ⇒ X (x )⇒ X (y)

_−

Γ, 1 + O = 1 − 1 + O = 1, 1 + 1 = 2∀−

Γ − 1 + O = 1, 1 + 1 = 2

_−

Γ, 1 + 1 = s(1 + O) − 1 + 1 = s(1 + O), 1 + 1 = 2∀−

Γ − 1 + 1 = s(1 + O), 1 + 1 = 2_−

Γ, 1 + 1 = 2 − 1 + 1 = 2⇒−

Γ, 1 + 1 = s(1 + O)⇒ 1 + 1 = 2 − 1 + 1 = 2

...⇒−

Γ, 1 + O = 1⇒ 1 + 1 = s(1 + O)⇒ 1 + 1 = 2 − 1 + 1 = 2∀−

Γ − 1 + 1 = 2

4


1+1=2In Γ:

∀x , x + O = x∀x y , x + s(y) = s(x + y)

∀x y , x = y ⇒ X (x )⇒ X (y)

_−

Γ, 1 + O = 1 − 1 + O = 1, 1 + 1 = 2∀−

Γ − 1 + O = 1, 1 + 1 = 2

_−

Γ, 1 + 1 = s(1 + O) − 1 + 1 = s(1 + O), 1 + 1 = 2∀−

Γ − 1 + 1 = s(1 + O), 1 + 1 = 2_−

Γ, 1 + 1 = 2 − 1 + 1 = 2⇒−

Γ, 1 + 1 = s(1 + O)⇒ 1 + 1 = 2 − 1 + 1 = 2

...⇒−

Γ, 1 + O = 1⇒ 1 + 1 = s(1 + O)⇒ 1 + 1 = 2 − 1 + 1 = 2∀−

Γ − 1 + 1 = 2

4


Other approaches

I Satisfiability Modulo Theory: efficient proof searchmethods, not genericDPLL(T ) [Ganzinger, Hagen, Nieuwenhuis, Oliveras and Tinelli,2004]

I Dependent and Inductive Types: universal, hard toautomatizeCoq, Isabelle, etc.

I Deduction Modulo and Superdeduction[Dowek, Hardin and Kirchner, 2003, Wack, 2005]

5


Other approaches




5


Other approaches




5

Introduction Deduction modulo

Poincaré’s principle

In a proof, distinguish deduction from computation to bettercombine them

Deduction modulo: inference rules (deduction) are appliedmodulo a congruence (computation)

Universal model for computation: rewriting congruencebased on a rewrite system over terms and formulæ

6

Introduction Deduction modulo

Example

x + O→ xx + s(y)→ s(x + y)

O = O→ >s(x ) = s(y)→ x = y

1 + 1 = 2−→ s(1 + O) = 2−→ s(1) = 2 +−→O = O−→>

−> − 1 + 1 = 2

7

Introduction Superdeduction

Compiling theoriesMax (x , a)→ x ∈ a ∧ ∀y , y ∈ a ⇒ y ≤ x

...Γ − t ∈ b

...Γ, y ∈ b − y ≤ t

−⇒Γ − y ∈ b ⇒ y ≤ t

−∀Γ − ∀y , y ∈ b ⇒ y ≤ t

−∧Γ − t ∈ b ∧ ∀y , y ∈ b ⇒ y ≤ t

− ∗←→Γ − Max (t , b)

...

Γ − x ∈ a Γ, y ∈ a − y ≤ x−Maxdef

Γ − Max (x , a)

8


Compiling theoriesMax (x , a)→ x ∈ a ∧ ∀y , y ∈ a ⇒ y ≤ x

...Γ − t ∈ b

...Γ, y ∈ b − y ≤ t

−⇒Γ − y ∈ b ⇒ y ≤ t

−∀Γ − ∀y , y ∈ b ⇒ y ≤ t

−∧Γ − t ∈ b ∧ ∀y , y ∈ b ⇒ y ≤ t

− ∗←→Γ − Max (t , b)

...

Γ − x ∈ a Γ, y ∈ a − y ≤ x−Maxdef

Γ − Max (x , a)

8


Superdeduction

New rules (superrules) from a proposition rewrite system

I Natural deduction supernatural deduction[Wack, 2005]Introduction and elimination superrules

I Sequent calculus extensible sequent calculus[Brauner, Houtmann and Kirchner, 2007]Left and right supperrules

Term rewrite rules are still applied modulo

9


Goal

How do deduction modulo and superdeduction help producebetter proofs from the mechanised-theorem-proving viewpoint?

1 more direct

: Cut admissibility

2 shorter

: Proof length

3 universal

: Logical framework

10


Goal


1 more direct: Cut admissibility

2 shorter

: Proof length

3 universal

: Logical framework

10


Goal



2 shorter: Proof length

3 universal

: Logical framework

10


Goal



2 shorter: Proof length

3 universal: Logical framework

10

Outline

1 Cut admissibilityExampleUndecidabilityA completion procedureImplementation

2 Proof length

3 Logical framework

Cut admissibility Example

The cut rule

Γ, P − ∆ Γ − P , ∆−Γ − ∆

Proof search procedures complete iff cut admissible

Without modulo, cut admissible (Gentzen’s Hauptsatz)

11


Inadmissibility in deduction modulo

A→ A⇒ B

Let us search a “minimal” counter-example:

_−

A, B − B

_− A − A

, B

⇒−A⇒ B , A −

B

↑−A −

B

_− A − A, B−⇒

− A, A⇒ B

, B

−↑− A

, B

−−

B

12



A→ A⇒ B


_−

A, B − B

_− A − A

, B

⇒−A⇒ B , A −

B

↑−A −

B

_− A − A, B−⇒

− A, A⇒ B

, B

−↑− A

, B

−−

B

12



A→ A⇒ B


_− A, B −

B

_− A − A

, B

⇒−A⇒ B , A −

B

↑−A −

B

_− A − A, B−⇒

− A, A⇒ B

, B

−↑− A

, B

−−

B

12



A→ A⇒ B


_− A, B − B_− A − A, B

⇒−A⇒ B , A − B

↑−A − B

_− A − A, B−⇒

− A, A⇒ B , B−↑− A, B−

− B

12

Cut admissibility Undecidability

Undecidability of cut admissibility

Theorem 1 ([LFCS07]).The problem:

Given a rewrite system R, does the sequent calculusmodulo R admits cut?

is undecidable

Sketch of proof: P valid iff the sequent calculus moduloA→ A⇒ P admits cut

13

Cut admissibility A completion procedure

Completion

Recover confluence using standard completion[Knuth and Bendix, 1970]

Complete A→ A⇒ B with B → >: cut admissibilityrecovered

If only terms are rewritten: cut admissibility = confluence[Dowek, 2003]

If propositions are rewritten: need for a generalization ofstandard completion

14


Basic mechanism of completion (w/osimplification)

add s → t

R

Confluent?yes

Return R

no

critical pairs←−R−→R

t

15


Basic mechanism of completion (w/osimplification)

smaller than p

R

Good property?yes

Return R

no

critical proofp

add rules forbuilding a proof

15


Abstract canonical systems[Dershowitz and Kirchner, 2006, Bonacina and Dershowitz, 2007]

Order on proofs critical proofs (minimal counter-examples) completion procedure

Instances: ground completion, standard completion, Moorefamilies, Horn theories, . . .

16


Deduction modulo as an ACS

Polarized unfolding sequent calculus:

Γ, A, P − ∆↑− A→− P

Γ, A − ∆Γ − P , A, ∆

−↑ A→+ PΓ − A, ∆

Equivalent to the sequent calculus modulo, especially w.r.t.cuts

Order on proofs: RPO with precedence − > _− > r and− (A⇒ B) > − (A)

Well adapted to the cut elimination procedure

If the completion terminates, the limit admits cut

17


Critical proofs

πΓ, A, P − ∆

↑− A−→PΓ, A − ∆

π′

Γ − Q , A, ∆↑− A−→Q

Γ − A, ∆−Γ − ∆

whereI π and π′ without cutI π and π′ without useless application of rulesI π and π′ apply _− an atomic formulæ onlyI Γ contains only atomic or universally quantified formulæ6= A

I Dual for ∆I All formulæ in Γ, ∆ are used somewhere

18


Completing formulæ

Find a proof smaller than a critical proof of Γ − ∆ Find a rewrite system R s.t. Γ `R ∆ w/o cut

An algorithm Rew from sequents to rewrite systems

Theorem 2.Θ ` P iff `Rew({−H : H∈Θ}) P

Transforms axiomatic presentations of a theory into rewritesystems

19

Cut admissibility Implementation

Search for critical proofs

πΓ, A, P − ∆

↑− A−→PΓ, A − ∆

π′

Γ − Q , A, ∆↑− A−→Q

Γ − A, ∆−Γ − ∆

Search for a cut-free proof, complete branch respectingconditions of critical proofs to find Γ, ∆

Implementation of the tableaux method TaMed[Bonichon and Hermant, 2006]

20



πΓ, A, P − ∆

↑− A−→PΓ, A − ∆

π′

Γ − Q , A, ∆↑− A−→Q

Γ − A, ∆−Γ − ∆



20



π

Γ,

A, P −

∆

↑− A−→PΓ, A − ∆

π′

Γ

− Q , A

, ∆

↑− A−→QΓ − A, ∆−

Γ − ∆



20



π

Γ,

A, P −

∆

↑− A−→PΓ, A − ∆

π′

Γ

− Q , A

, ∆

↑− A−→QΓ − A, ∆−

Γ − ∆



20


Contributions [LFCS07]

I Undecidability of cut admissibility in deduction moduloI Completion procedure to recover itI Algorithm to transform axiomatic presentations into

rewrite systems used moduloI Implementation in TOM/OCaml

21

Outline

1 Cut admissibility

2 Proof lengthMotivationFirst resultsApplication to higher-order arithmetic

3 Logical framework

Proof length Motivation

Speed-ups in higher-order arithmetic

Second-order arithmetic proves more than first-orderarithmetic, but also more quickly:

Theorem 3 ([Gödel, 1936, Buss, 1994]).There exists a family (Pj )j∈N such that

I for all j , A1 Pj

I there exists k such that for all j , A2 k Pj

I there exists no k such that for all j , A1 k Pj

True for all orders i over i − 1

22

Proof length Motivation

Higher-order logic in deduction modulo

[Dowek, Hardin and Kirchner, 2001] HOLλσ encodes thehigher-order logic based on simple type theory

Same proof length in HOL-λ and in the sequent calculusmodulo HOLλσ

Possibility to encode higher-order arithmetic withoutincreasing proof length?

23

Proof length First results

No restrictions on the rewrite system?

R: rewrite system such that P ∗←→R> for all first-order

tautology P

All proofs can be abridged to −> − PAre those really proofs?

Proof checking is not decidable

24


A formal framework

If interested with links with complexity theory, proof checkingmust be performed in polynomial time[Cook and Reckhow, 1979]

In deduction modulo: the congruence should be decidable inpolynomial time

25


Simple example

Add def=

{Add(O, y , y)→ >

Add(s(x ), y , s(z ))→ Add(x , y , z )

Proposition 4.I 1 Add Add(i , i , 2i)I Θ O(i) Add(i , i , 2i) for all finite compatible

presentations Θ

∗←→Add

is decidable in polynomial time

26

Proof length Application to higher-order arithmetic

Encoding higher order in deduction modulo

Higher-order arithmetic

↙ ↘

Higher order: HOi Remaining axioms: fA=

comprehension schema +rules encoding formulæ by terms

[Kirchner, 2006]

Theorem 5.

Ai k P fA O(k) HOiP

27


“0th order” 1st order . . . i − 1st order ith order

Ai−1 `

speed-up

""EEEE

EEEE

EEEE

E

speed-up (Buss)

��333

3333

3333

3333

3333

333

shorterproofs

��

fA,Θi `

speed-up

��`HHAmod

ifA `HOi Ai `

linear

kklinearoo

28


Contributions [CSL07]

I Simple speed-ups in deduction moduloI Even when counting rewrite steps

(using deep inference [Bruscoli and Guglielmi, 2008])I Length-preserving simulation of higher-order arithmetic in

first order moduloI Purely computational presentation of higher-order

arithmetic

29

Outline

1 Cut admissibility

2 Proof length

3 Logical frameworkMotivationsApplication to the functional pure type systems

Logical framework Motivations

Encoding higher-order systems in first ordermodulo?

I well studiedI existing efficient proof search proceduresI near to implementationI universal (tool cooperation)

30


Encoding higher-order systems in first ordermodulo?

I well studiedI existing efficient proof search proceduresI near to implementationI universal (tool cooperation)

30


Logical framework

[Pfenning, 1996]:“a meta-language for the specification of deductivesystems”

most famous: ELF (based on λΠ)

HOLλσ = specification of HOL-λDeduction modulo as a logical framework?

A methodology to specify a deductive system

Application to functional pure type systems

31


Logical framework



HOLλσ = specification of HOL-λSuperdeduction as a logical framework?

A methodology to specify a deductive system


31


Logical framework



HOLλσ = specification of HOL-λSuperdeduction as a logical framework?A methodology to specify a deductive system


31

Logical framework Application to the functional pure type systems

Pure type systems [Geuvers and Nederhof, 1991]

T ::= x | λx : T , T | T T | Πx : T , T

A pure type system is given byI sorts SI axioms A ⊆ S × SI rules R ⊆ S × S × S

Functional if A and R are graphs defining functions

32


Typing system

Empty[] well-formed

Γ well-formed Γ − A : sDeclaration s ∈ S and x not in ΓΓ, x : A well-formed

Γ well-formedSort (s1, s2) ∈ AΓ − s1 : s2

Γ well-formedVariable x : A ∈ ΓΓ − x : A

33


Typing system (cont.)

Γ − A : s1 Γ, x : A − B : s2Product (s1, s2, s3) ∈ RΓ − Πx : A, B : s3

Γ − T : Πx : A, B Γ − U : AApplication

Γ − (T U ) : {U /x}B

Γ − Πx : A, B : s Γ, x : A − T : BAbstraction

Γ − λx : A, T : Πx : A, B

Γ − T : A Γ − B : sConversion s ∈ S and A ∗←→βBΓ − T : B

34


Encoding the λ-terms

Binary predicate ε(t , u) to encode T : U (shallow encoding)

λ-calculus with explicit substitutions [Kesner, 2000]+ constants s for all sorts s ∈ S+ binary function π〈s1,s2,s3〉 for all rules (s1, s2, s3) ∈ R

additional term rewrite rules:

s [t ]→ sπ〈s1,s2,s3〉 (a, b) [s ]→ π〈s1,s2,s3〉 (a [s ] , b [lift(s)])

35


Encoding the inference rules through superrulesFind a rewrite rule of which one superrule correspond to theinference rule

Γ − A : s1 Γ, x : A − B : s2Product (s1, s2, s3) ∈ RΓ − Πx : A, B : s3

ε(π〈s1,s2,s3〉 (a, b) , s3

)→ ε (a, s1)∧∀z . ε (z , a)⇒ ε (b [cons(z )] , s2)

(2)

Γ − ε (a, s1) Γ, ε (z , a) − ε (b [cons(z )] , s2)−(2) z 6∈ FV (Γ, a, b)

Γ − ε(π〈s1,s2,s3〉 (a, b) , s3

)36


CorrectnessPT S(S ,A,R): explicit substitutions +

ε (s1, s2)→ > (s1, s2) ∈ A (1)ε(π〈s1,s2,s3〉 (a, b) , s3

)→ ε (a, s1) ∧ ∀z . ε (z , a)⇒ ε (b [cons(z )] , s2)

(2)

ε(t , π〈s1,s2,s3〉 (a, b)

)→

ε(π〈s1,s2,s3〉 (a, b) , s3

)∧

∀z . ε (z , a)⇒ ε (t z , b [cons(z )]) (3)

Theorem 6.

If Γ(S ,A,R) T : A then |Γ| `+PT S(S,A,R) ε

(|T |Γ , |A|Γ

)37


Extra rules

(2)1−

Variable

Sort

Product

ApplicationConversion

(S , A, R) SND(PT S(S ,A,R))

−(1)

−(2)

_−

−⇒

∀−

∧1−

. . .ND

(2)2−

(3)2−

Abstraction−(3)

(3)1−

modulo λW

38


Extra rules

. . .

Variable

Sort

Product



−(1)

−(2)

_−

ND

(2)2−

(3)2−

Abstraction−(3)

(3)1−

modulo λW

(2)1−

−⇒ ∧1

−

∀−

38


Extra rules

(2)2−

Variable

Sort

Product



−(1)

−(2)

_−

ND

(3)2−

Abstraction−(3)

modulo λW

−⇒ ∧1

−

∀−

. . .

(3)1−

(2)1−

38


ConservativenessExtra rules:

Γ − ε(π〈s1,s2,s3〉 (a, b) , s3

)(2)1−

Γ − ε (a, s1)

By correctness of the translation, if|Πx : A, B | = π〈s1,s2,s3〉 (a, b) then A : s1

Theorem 7.

If Γ well formed and |Γ| `+PT S(S,A,R) ε (a, b)there exists A and B such thata ∗−→PT S(S,A,R)

|A| b ∗−→PT S(S,A,R)

|B | Γ(S ,A,R) A : B

39


Contributions [LICS08]

I Methodology to encode deductive systems insuperdeduction

I Correct and conservative encoding of functional pure typesystems

I Proof search in PTS via the extensible sequent calculusI New insight on normalization in PTS

40

Outline

0 Introduction

1 Cut admissibility

2 Proof length

3 Logical framework

4 ConclusionFurther work

Conclusion Further work

Other simplicity criteria

I NormalizationI new instance of abstract canonical system?I simplification rules?

A→ A⇒ B ; B → > A→ > ; B → >

I Decidability of the congruenceI decidable proof checkingI decidability in polynomial time

I Proof lengthI A formal framework for proof complexityI Link deduction modulo – Tseytin’s extensions

41


Automating the logical frameworkI From axiomatic presentations to rewrite systems:

I automateI ensure the good propertiesI not always possible in intuitionistic logic

I Automated theorem provingI term rewrite rule strategies for the moduloI superrules application strategiesI automated or user specified?

I A universal proof environmentI share proof developments from different toolsI modular deduction moduloI inductive types, subtyping, . . .

42


Lemuridæ Intuitionistic Super Sequent Calculus

Supernatural deduction

Europa λΠ-calculus modulo

λHOLPVSCCCoq

Fellowship FO sequent calculus

· · ·

43


Lemuridæ Intuitionistic Super Sequent Calculus

Supernatural deduction

Europa λΠ-calculus modulo[Gentzen, 1934]

+[Wack, 2006]

λHOLPVSCCCoq

[Cousineau and Dowek, 2007]

[Sacerdoti Coen and Kirchner, 2006]

Fellowship FO sequent calculus

· · ·

43


Bonacina, M. and Dershowitz, N. (2007).Abstract canonical inference.ACM Transactions on Computational Logic, 8(1).

Bonichon, R. and Hermant, O. (2006).A semantic completeness proof for TaMed.In Hermann, M. and Voronkov, A., editors, LPAR, volume4246 of LNCS, pages 167–181. Springer.

Brauner, P., Houtmann, C., and Kirchner, C. (2007).Principle of superdeduction.In Ong, L., editor, Proceedings of LICS, pages 41–50.

Bruscoli, P. and Guglielmi, A. (2008).On the proof complexity of deep inference.ACM Transactions on Computational Logic.To appear.

43


Buss, S. R. (1994).On Gödel’s theorems on lengths of proofs I: Number oflines and speedup for arithmetics.The Journal of Symbolic Logic, 59(3):737–756.

Cook, S. A. and Reckhow, R. A. (1979).The relative efficiency of propositional proof systems.The Journal of Symbolic Logic, 44(1):36–50.

Cousineau, D. and Dowek, G. (2007).Embedding pure type systems in the lambda-pi-calculusmodulo.In Ronchi Della Rocca, S., editor, TLCA, volume 4583 ofLNCS, pages 102–117. Springer.

Dershowitz, N. and Kirchner, C. (2006).Abstract canonical presentations.

43


Theoretical Computer Science, 357:53–69.

Dowek, G. (2003).Confluence as a cut elimination property.In Nieuwenhuis, R., editor, RTA, volume 2706 of LNCS,pages 2–13. Springer.

Dowek, G., Hardin, T., and Kirchner, C. (2001).HOL-λσ an intentional first-order expression ofhigher-order logic.Mathematical Structures in Computer Science,11(1):1–25.

Dowek, G., Hardin, T., and Kirchner, C. (2003).Theorem proving modulo.Journal of Automated Reasoning, 31(1):33–72.

Gentzen, G. (1934).

43


Untersuchungen über das logische Schliessen.Mathematische Zeitschrift, 39:176–210, 405–431.Translated in Szabo, editor., The Collected Papers ofGerhard Gentzen as “Investigations into LogicalDeduction”.Gödel, K. (1936).Über die Länge von Beweisen.Ergebnisse eines Mathematischen Kolloquiums, 7:23–24.English translation in [Gödel, 1986].

Gödel, K. (1986).On the length of proofs.In Feferman, S. et al., editors, Kurt Gödel: CollectedWorks, volume 1, pages 396–399. Oxford University Press,Oxford.Kesner, D. (2000).

43


Confluence of extensional and non-extensional λ-calculiwith explicit substitutions.Theoretical Computer Science, 238(1–2):183–220.

Kirchner, F. (2006).A finite first-order theory of classes.In Altenkirch, T. and McBride, C., editors, TYPES,volume 4502 of LNCS, pages 188–202. Springer.

Knuth, D. E. and Bendix, P. B. (1970).Simple word problems in universal algebras.In Leech, J., editor, Computational Problems in AbstractAlgebra, pages 263–297. Pergamon Press, Oxford.

Pfenning, F. (1996).The practice of logical frameworks.In CAAP, volume 1059 of LNCS, pages 119–134. Springer.

43


Sacerdoti Coen, C. and Kirchner, F. (2006).Fellowship.http://www.lix.polytechnique.fr/Labo/Florent.Kirchner/fellowship/.

Wack, B. (2005).Typage et Déduction dans le Calcul de Réécriture.PhD thesis, Université Henri Poincaré – Nancy 1.

Wack, B. (2006).Supernatural deduction.Manuscript, available at http://www.loria.fr/~wack/papers/supernatural.ps.gz.

43

http://www.lix.polytechnique.fr/Labo/Florent.Kirchner/fellowship/

http://www.lix.polytechnique.fr/Labo/Florent.Kirchner/fellowship/

http://www.loria.fr/~wack/papers/supernatural.ps.gz

http://www.loria.fr/~wack/papers/supernatural.ps.gz

Documents

Bonnes démonstrations en déduction modulo - Accueil fileBonnes démonstrations en déduction modulo Soutenance de thèse Guillaume Burel Université Henri Poincaré – Loria 23