Mathematical Logic for Computer Science

The following sections are included:

• PREFACE

• CONTENTS

Mathematical logic is the study of reasoning, especially the reasoning used in mathematics…

The only prerequisite for reading this book is familiarity with the basic notions of sets, inductive definitions, and inductive proofs. Here a brief summary of these will be given. The reader may omit this chapter at first reading and refer to it when necessary.

Compound propositions are formed by connectives. Simple propositions are those which are not compound. In propositional logic only the logical forms of compound propositions are analysed. Propositional logic studies the deducibility relations between premises and conclusions which are compound or unanalysed simple propositions.

In prepositional logic only the logical forms of compound propositions are analysed. A simple proposition is an unanalysed whole which is either true or false. For instance, in the following inference…

We shall develop in this chapter another type of formal deducibility, which is essentially based upon formally provable formulas. It is denoted by the notation…

The following sections are included:

• SATISFIABILITY AND VALIDITY

• SOUNDNESS

• COMPLETENESS OF PROPOSITIONAL LOGIC

• COMPLETENESS OF FIRST-ORDER LOGIC

• COMPLETENESS OF FIRST-ORDER LOGIC WITH EQUALITY

• INDEPENDENCE

Many important results can be obtained by applying the Soundness and Completeness Theorems, among which are Compactness, Lowenheim-Skolem's, and Herbrand's Theorems. Some related basic notions of model theory will also be introduced in this chapter.

Constructive logic is the logic for constructive reasoning. Statements in constructive reasoning are interpreted in a constructive way. This chapter is a brief introduction to constructive logic, and the resulting system will be compared with the non-constructive system developed in Chapters 2-5.

Modal logic is the logic of modal notions. Given any proposition A, we can form the propositions " A is necessary" and " A is possible". Necessity and possibility are modal notions. Propositions with and without modal notions are of different kinds, hence modal and non-modal logics are different as well. We shall study modal propositional logic in the present chapter and modal first-order logic in the next one.

The following sections are included:

• MODAL FIRST-ORDER LANGUAGE

• SEMANTICS

• FORMAL DEDUCIBILITY

• COMPLETENESS

• EQUALITY

The following sections are included:

• APPENDIX

• BIBLIOGRAPHY

• LIST OF SYMBOLS

• INDEX