OUP > Journals > Computing/Engineer. & Mathematics/Stats. > Journal of Logic and Computation
Journal of Logic and Computation
Volume 12, Issue 6, December 2002: pp. 10171026
Modal Logics Between Propositional and Firstorder
Melvin Fitting^{1}
^{1}Lehman College, Department of Mathematics and Computer Science, 250 Bedford Park Boulevard West, Bronx, NY 104681589, USA. Email: fitting@lehman.cuny.edu
One can add the machinery of relation symbols and terms to a propositional modal logic without adding quantifiers. Ordinarily this is no extension beyond the propositional. But if terms are allowed to be nonrigid, a scoping mechanism (usually written using lambda abstraction) must also be introduced to avoid ambiguity. Since quantifiers are not present, this is not really a firstorder logic, but it is not exactly propositional either. For propositional logics such as K, T and D, adding such machinery produces a decidable logic, but adding it to S5 produces an undecidable one. Further, if an equality symbol is in the language, and interpreted by the equality relation, logics from K4 to S5 yield undecidable versions. (Thus transitivity is the villain here.) The proof of undecidability consists in showing that classical firstorder logic can be embedded.
Keywords: Modal; propositional; decidable; nonrigid; abstraction
Table of Contents
FullText PDF (102 KB)
