Глава
On Kripke completeness of some modal predicate logics with the density axiom
We give a sufficient condition for Kripke completeness of the extension of a modal logic with the transitive closure modality. More precisely, we show that if a logic is canonical and admits what we call definable filtration (ADF), then such an extension is complete (and again ADF).
Доказан локальный аналог теоремы Гольдблатта-Томасона о характеризации модально определимых классов шкал Крипке с выделенной точкой; результат также обобщен на случай шкал с несколькими выделенными точками. Дается сравнение результатов с подобными результатами для гибридной модальной логики; формулируются открытые вопросы.
We extend the language of the modal logic K4 of transitive frames with two sorts of modalities. In addition to the usual possibility modality (which means that a formula holds in some successor of a given point), we consider graded modalities (a formula holds in at least n successors) and converse graded modalities (aformula holds in at least n predecessors). We show that the resulting logic, GrIK4, is both locally and globally undecidable. The same result is obtained for all logics between GrIK4 and its reflexive companion GrIS4 and for some other modal logics. As a consequence, for the “unrestricted version” of the description logic SIQ, the problem of concept satisfiability (even with respect to the empty terminology) is undecidable. We also give a survey of results on the local and global decidability, complexity, and the finite model property for fragments of GrIK4.
Фильтрация является стандартным средством для установления финитной аппроксимируемости модальных логик. В работе изучаются логики и классы шкал, допускающие фильтрацию (фильтруемые), и указываются операции на них, сохраняющие фильтруемость. В частности, показано, что операции добавления обратного отношения и транзитивного замыкания отношения сохраняет фильтруемость. Используя данные результаты, установлено, что всякая регулярная грамматическая модальная логика (возможно с обратными модальностями) допускает фильтрацию. Наконец, доказано, что некоторые простые грамматические модальные логики неразрешимы, а значит, не являются фильтруемыми.