Modal logics between propositional and first-order

Prof Melvin Fitting
Department of Mathematics and Computer Science,
Lehman College, New York.

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 non-rigid, 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 first-order logic, but it is not exactly propositional either. I will show that for propositional logics such as K, T and D, adding such machinery produces a decidable logic, but adding it to logics between K4 and S5 produces an undecidable one. (Transitivity is the villain here.) The proof of undecidability consists of showing that classical first-order logic can be embedded.

ASTEC seminar
January 12, 2001, 10.30

Place: Information technology, Uppsala University
Room: 1510
Time: 10.30

Room 1510 is in Building 1, Floor 5, room 10 (in the southern part of the building).

Help on how to find ASTEC seminars.

Updated 08-Jan-2001 15:16 by Roland Grönroos
e-mail: info -at-    Location: