Proof Nets and the Identity of Proofs

Lutz Straßburger 1, 2
1 PARSIFAL - Proof search and reasoning with logic specifications
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : These are the notes for a 5-lecture-course given at ESSLLI 2006 in Malaga, Spain. The URL of the school is http://esslli2006.lcc.uma.es/ . This version slightly differs from the one which has been distributed at the school because typos have been removed and comments and suggestions by students have been worked in. The course is intended to be introductory. That means no prior knowledge of proof nets is required. However, the student should be familiar with the basics of propositional logic, and should have seen formal proofs in some formal deductive system (e.g., sequent calculus, natural deduction, resolution, tableaux, calculus of structures, Frege-Hilbert-systems, ...). It is probably helpful if the student knows already what cut elimination is, but this is not strictly necessary. In these notes, I will introduce the concept of ``proof nets'' from the viewpoint of the problem of the identity of proofs. I will proceed in a rather informal way. The focus will be more on presenting ideas than on presenting technical details. The goal of the course is to give the student an overview of the theory of proof nets and make the vast amount of literature on the topic easier accessible to the beginner. For introducing the basic concepts of the theory, I will in the first part of the course stick to the unit-free multiplicative fragment of linear logic because of its rather simple notion of proof nets. In the second part of the course we will see proof nets for more sophisticated logics. This is a basic introduction into proof nets from the perspective of the identity of proofs. We discuss how deductive proofs can be translated into proof nets and what a correctness criterion is.
Type de document :
Rapport
[Research Report] RR-6013, INRIA. 2006
Liste complète des métadonnées

Littérature citée [87 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00107260
Contributeur : Lutz Straßburger <>
Soumis le : jeudi 16 novembre 2006 - 12:05:59
Dernière modification le : jeudi 9 février 2017 - 15:12:00
Document(s) archivé(s) le : jeudi 23 septembre 2010 - 16:31:02

Fichiers

Identifiants

Collections

Citation

Lutz Straßburger. Proof Nets and the Identity of Proofs. [Research Report] RR-6013, INRIA. 2006. 〈inria-00107260v3〉

Partager

Métriques

Consultations de
la notice

268

Téléchargements du document

263