Resolution is a Decision Procedure for Many Propositional Modal Logics

Schmidt, R. A. (Jan. 1997)

Research Report MPI-I-97-2-002, Max-Planck-Institut für Informatik, Saarbrücken, Germany. PostScript, BiBTeX

The paper shows satisfiability in many propositional modal systems can be decided by ordinary resolution procedures. This follows from a general result that resolution and condensing is a decision procedure for the satisfiability problem of formulae in so-called path logics. Path logics arise from propositional and normal uni- and multi-modal logics by the optimised functional translation method. The decision result provides an alternative decision proof for the relevant modal logics (including K, KD, KT and KB, their combinations as well as their multi-modal versions), and related systems in artificial intelligence. This alone is not interesting. A more far-reaching consequence of the result has practical value, namely, any standard first-order theorem prover that is based on resolution can serve as a reasonable and efficient inference tool for modal reasoning.

The short version is published in Kracht, M., de Rijke, M., Wansing, H. and Zakharyaschev, M. (eds) (1998), Advances in Modal Logic, Volume 1, Lecture Notes 87, CSLI Publications, Stanford, 189-208. Abstract, BiBTeX.
Renate A. Schmidt
Home | Publications | FM Group | School | Man Univ

Last modified: 24 Jan 2000
Copyright © 1996,7,8 Renate A. Schmidt, School of Computer Science, Man Univ, schmidt@cs.man.ac.uk