Modal Logic

by Patrick Blackburn , Maarten de Rijke , Yde Venema

• ISBN13: 9780521527149
• ISBN10: 0521527147
• Format: Paperback
• Copyright: 2002-09-30
• Publisher: Cambridge University Press

Summary

Now available in paperback, this is a modern, advanced textbook on modal logic, a field which caught the attention of computer scientists in the late 1970s. Researchers in areas ranging from economics to computational linguistics have since realised its worth. The book is for novices and for more experienced readers, with two distinct tracks clearly signposted at the start of each chapter. The development is mathematical; prior acquaintance with first-order logic and its semantics is assumed, and familiarity with the basic mathematical notions of set theory is required. The authors focus on the use of modal languages as tools to analyze the properties of relational structures, including their algorithmic and algebraic aspects, and applications to issues in logic and computer science such as completeness, computability and complexity are considered. Three appendices supply basic background information and numerous exercises are provided. Ideal for anyone wanting to learn modern modal logic.

Table of Contents

Preface	xi
Basic Concepts	1	(49)
Relational Structures	2	(7)
Modal Languages	9	(7)
Models and Frames	16	(12)
General Frames	28	(3)
Modal Consequence Relations	31	(2)
Normal Modal Logics	33	(4)
Historical Overview	37	(11)
Summary of Chapter 1	48	(2)
Models	50	(73)
Invariance Results	51	(13)
Bisimulations	64	(9)
Finite Models	73	(10)
The Standard Translation	83	(8)
Modal Saturation via Ultrafilter Extensions	91	(9)
Characterization and Definability	100	(10)
Simulation and Safety	110	(7)
Summary of Chapter 2	117	(6)
Notes	118	(5)
Frames	123	(65)
Frame Definability	124	(6)
Frame Definability and Second-Order Logic	130	(8)
Definable and Undefinable Properties	138	(5)
Finite Frames	143	(5)
Automatic First-Order Correspondence	148	(8)
Sahlqvist Formulas	156	(11)
More about Sahlqvist Formulas	167	(11)
Advanced Frame Theory	178	(5)
Summary of Chapter 3	183	(5)
Notes	185	(3)
Completeness	188	(73)
Preliminaries	189	(7)
Canonical Models	196	(5)
Applications	201	(10)
Limitative Results	211	(6)
Transforming the Canonical Model	217	(6)
Step by Step	223	(6)
Rules for the Undefinable	229	(10)
Finitary Methods I	239	(8)
Finitary Methods II	247	(9)
Summary of Chapter 4	256	(5)
Notes	258	(3)
Algebras and General Frames	261	(71)
Logic as Algebra	262	(13)
Algebraizing Modal Logic	275	(8)
The Jonsson-Tarski Theorem	283	(11)
Duality Theory	294	(9)
General Frames	303	(15)
Persistence	318	(8)
Summary of Chapter 5	326	(6)
Notes	327	(5)
Computability and Complexity	332	(81)
Computing Satisfiability	333	(5)
Decidability via Finite Models	338	(9)
Decidability via Interpretations	347	(9)
Decidability via Quasi-models and Mosaics	356	(8)
Undecidability via Tiling	364	(9)
NP	373	(8)
PSPACE	381	(12)
EXPTIME	393	(13)
Summary of Chapter 6	406	(7)
Notes	407	(6)
Extended Modal Logic	413	(72)
Logical Modalities	414	(12)
Since and Until	426	(8)
Hybrid Logic	434	(12)
The Guarded Fragment	446	(12)
Multi-Dimensional Modal Logic	458	(12)
A Lindstrom Theorem for Modal Logic	470	(6)
Summary of Chapter 7	476	(9)
Notes	477	(8)
Appendix A A Logical Toolkit	485	(12)
Appendix B An Algebraic Toolkit	497	(7)
Appendix C A Computational Toolkit	504	(12)
Appendix D A Guide to the Literature	516	(8)
Bibliography	524	(20)
List of Notation	544	(3)
Index	547