A Guide to the Modal Logics of Knowledge and Belief: Preliminary Draft

Abstract

We review and re-examine possible-worlds semantics for propositional logics of knowledge and belief with four particular points of emphasis: (1) we show how general techniques for finding decision procedures and complete axiomatizations apply to models for knowledge and belief, (2) we show how sensitive the difficulty of the decision procedure is to such issues as the choice of modal operators and the axiom system, (3) we discuss how notions of common knowledge and implicit knowledge among a group of agents fit into the possible-worlds framework, and (4) we consider to what extent the possible-worlds approach is a viable one for modelling knowledge and belief. As far as complexity is concerned, we show among other results that while the problem of deciding satisfiability of an S5 formula with one knower is NP-complete, the problem for many knowers is PSPAO.&complete. Adding an implicit knowledge operator does not change the complexity substantially, but once a common knowledge operator is added to the language, the problem becomes complete for exponential time.