Skip to main content

About this book

This book provides an introduction to logic and mathematical induction which are the basis of any deductive computational framework. A strong mathematical foundation of the logical engines available in modern proof assistants, such as the PVS verification system, is essential for computer scientists, mathematicians and engineers to increment their capabilities to provide formal proofs of theorems and to certify the robustness of software and hardware systems.

The authors present a concise overview of the necessary computational and mathematical aspects of ‘logic’, placing emphasis on both natural deduction and sequent calculus. Differences between constructive and classical logic are highlighted through several examples and exercises. Without neglecting classical aspects of computational logic, the authors also highlight the connections between logical deduction rules and proof commands in proof assistants, presenting simple examples of formalizations of the correctness of algebraic functions and algorithms in PVS.

Applied Logic for Computer Scientists will not only benefit students of computer science and mathematics but also software, hardware, automation, electrical and mechatronic engineers who are interested in the application of formal methods and the related computational tools to provide mathematical certificates of the quality and accuracy of their products and technologies.

Table of Contents

Chapter 1. Derivation and Proofs in the Propositional Logic

The most elementary logical system of some practical interest is the propositional logic. In this system is it possible to express logical consequences, conjunction, disjunction, and negation of propositions.
Mauricio Ayala-Rincón, Flávio L. C. de Moura

Chapter 2. Derivations and Proofs in the Predicate Logic

The propositional logic has several limitations for expressing ideas; mainly, it is not possible to quantify over sets of individuals and reason about them.
Mauricio Ayala-Rincón, Flávio L. C. de Moura

Chapter 3. Deductions in the Style of Gentzen’s Sequent Calculus

In this chapter, we present a style of deduction known as Gentzen’s sequent calculus that is different from the one of natural deduction (both invented by Gerhard Gentzen) and has relevant computational interest and applications.
Mauricio Ayala-Rincón, Flávio L. C. de Moura

Chapter 4. Derivations and Formalizations

The deductive rules studied in the previous chapters have been implemented in several computational environments such as theorem provers and proof assistants.
Mauricio Ayala-Rincón, Flávio L. C. de Moura

Chapter 5. Algebraic and Computational Examples

In this chapter, we present simple cases of study in order to illustrate the application of PVS for formalizing algebraic and algorithmic properties.
Mauricio Ayala-Rincón, Flávio L. C. de Moura

Chapter 6. Suggested Readings

Proof theory is a subarea of mathematical logic that deals with proofs as mathematical objects.
Mauricio Ayala-Rincón, Flávio L. C. de Moura
Additional information