Thumbnail
Access Restriction
Open

Author Rosen, Eric ♦ Eric Rosen, Y.
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract In this paper, we discuss the nite model theory of propositional modal logic, PM. Modal logic has been studied extensively in connection with philosophical logic. More recently, connections have emerged between modal logic and computational linguistics and certain areas of computer science. Below wewillbeinterested in the `classical model theory' of modal logic, an approach taken by van Benthem and others. For example, PM satis es certain preservation theorems that are analogous to classical theorems for rst-order logic, FO. We show that, in contrast to more expressive logics, PM remains well-behaved over the class F of nite structures, as various classical results remain true over this class. In order to make this paper self-contained, we brie y describe the syntax and semantics of PM. Most of this material is well-known, and more detailed descriptions can be found in many places (e.g. see [?]). The syntax of PM is obtained from that of simple sentential logic by adding the two modal operators 2', necessarily ', and3', possibly '. Over a signature of proposition symbols, = fp 1�:::�pkg, the class of sentences of PM ( ) is the smallest class containing each atomicsentence pi and closed under negation, conjunction, disjunction, and the operators 2 and 3. We will always assume that the signature is and non-empty. A (Kripke) model of PM ( ) is a directed graph A with additional unary Iwould like to thank Prof. Johan van Benthem for introducing me to this subject and to his work, and for many helpful suggestions. I am also extremely grateful to Scott Weinstein for his insight, encouragement, and guidance, and to Marco Hollenberg and Steven Lindell for detailed comments on an earlier draft of this
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 1995-01-01