Prime Implicates and Prime Implicants in Modal Logic

摘要

The purpose of this paper is to extend the notions of prime implicates and prime implicants to the basic modal logic κ. We consider a number of different potential definitions of clauses and terms for κ, which we evaluate with respect to their syntactic, semantic, and complexity-theoretic properties. We then continue our analysis by comparing the definitions with respect to the properties of the notions of prime implicates and prime implicants that they induce. We provide algorithms and complexity results for the prime implicate generation and recognition tasks for the two most satisfactory definitions.