Disjunctive Normal Form for Multi-Agent Modal Logics Based on Logical Separability

摘要

Modal logics are primary formalisms for multi-agent systems but major reasoning tasks in such logics are intractable, which impedes applications of multi-agent modal logics such as automatic planning. One technique of tackling the intractability is to identify a fragment called a normal form of multi-agent logics such that it is expressive but tractable for reasoning tasks such as entailment checking, bounded conjunction transformation and forgetting. For instance, DNF of propositional logic is tractable for these reasoning tasks. In this paper, we first introduce a notion of logical separability and then define a novel disjunctive normal form SDNF for the multi-agent logic K_n, which overcomes some shortcomings of existing approaches. In particular, we show that every modal formula in K_n, can be equivalently casted as a formula in SDNF, major reasoning tasks tractable in propositional D N F are also tractable in SDNF, and moreover, formulas in SDNF enjoy the property of logical separability. To demonstrate the usefulness of our approach, we apply SDNF in multi-agent epistemic planning. Finally, we extend these results to three more complex multi-agent logics D_n, K45_n and KD45_n.