### Ircs report 95--27modal logic over finite structures (1995).Ircs report 95--27modal logic over finite structures (1995).

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