Lectures on Linear Logic

Linear logic is an example of a "resource-sensitive" logic, keeping track of the number of times data of given types are used. Formulas in linear logic represent either the data themselves or data types, whereas in ordinary logic a formula is a proposition. If ordinary logic is a logic of truth, linear logic is a logic of actions.

Linear logic and its implications are explored in depth in this volume. Particular attention has been given to the various formalisms for linear logic, embeddings of classical and intuitionistic logic into linear logic, the connection with certain types of categories, the "formulas-as-types" paradigm for linear logic and associated computational interpretations, and Girard's proof nets for classical linear logic as an analogue of natural deduction. It is also shown that linear logic is undecidable. A final section, contributed by D. Roorda, presents a proof of strong normalization for cut elimination in linear logic.

Linear logic is of interest to logicians and computer scientists, and shows links with many other topics, such as coherence theorems in category theory, the theory of Petri nets, and abstract computing machines without garbage collection.

A.S. Troelstra is professor emeritus of pure mathematics and foundations of mathematics at the Institute of Logic, Language, and Information (ILLC) of the University of Amsterdam.

Contents

1/1/1992