Focusing is a proof-theoretic device to structure proof search in the sequent calculus: it provides a normal form to cut-free proofs in which the application of invertible and non-invertible inference rules is structured in two separate and disjoint phases. Although stemming from proofsearch considerations, focusing has not been thoroughly investigated in actual theorem proving, in particular w.r.t. termination. We present a contraction-free (and hence terminating) focused multisuccedent sequent calculus for propositional intuitionistic logic, which refines the G4ip calculus in the tradition of Vorob’ev, Hudelmeier and Dyckhoff. We prove completeness of the calculus semantically and argue that this offers a viable alternative to other more syntactical means.

A Semantical Analysis of Focusing and Contraction in Intuitionistic Logic / A. Avellone, C. Fiorentini, A. Momigliano. - In: FUNDAMENTA INFORMATICAE. - ISSN 0169-2968. - 140:3-4(2015 Sep 14), pp. 247-262. [10.3233/FI-2015-1253]

A Semantical Analysis of Focusing and Contraction in Intuitionistic Logic

C. Fiorentini;A. Momigliano
2015

Abstract

Focusing is a proof-theoretic device to structure proof search in the sequent calculus: it provides a normal form to cut-free proofs in which the application of invertible and non-invertible inference rules is structured in two separate and disjoint phases. Although stemming from proofsearch considerations, focusing has not been thoroughly investigated in actual theorem proving, in particular w.r.t. termination. We present a contraction-free (and hence terminating) focused multisuccedent sequent calculus for propositional intuitionistic logic, which refines the G4ip calculus in the tradition of Vorob’ev, Hudelmeier and Dyckhoff. We prove completeness of the calculus semantically and argue that this offers a viable alternative to other more syntactical means.
Settore INF/01 - Informatica
Settore MAT/01 - Logica Matematica
14-set-2015
Article (author)
File in questo prodotto:
File Dimensione Formato  
2015_fi.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 128.77 kB
Formato Adobe PDF
128.77 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/320190
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact