On the Subtle Nature of a Simple Logic of the Hide and Seek Game


本文用一个简洁的模态语言描述了我们小时候都爱玩的捉迷藏游戏。为了刻画玩家的获胜条件，文中的逻辑语言很自然地包含了一个用以描述位置相同的命题常项。论文展示了这个看似简单的等词常项如何突然提升了逻辑的计算复杂度：文中给出的逻辑因为等词的扩充由可判定变得不可判定。类似的情形也存在：一阶逻辑中也有一些可判定片段在扩充等词后变得不可判定，如哥德尔类（Goldfarb，1984）和带函数符号的函数依赖性逻辑（Baltag & van Benthem, 2021）。本文的研究工作为该类片段添加了一个新的模态变体。此外，通过与标准模态逻辑进行比较，论文还讨论了逻辑表达力等其他问题。本文所讨论的捉迷藏游戏是警察和强盗博弈(games of cops and robbers)的一个基本情况，后者在算法和组合角度得到了很好的研究，本文的工作从逻辑学的角度开启了对这类博弈进行研究的一个可能性。





作者简介






李大柱：河南焦作人，自2021年11月起为中国科学院哲学研究所讲师。清华大学、阿姆斯特丹大学联授哲学博士，北京大学哲学硕士，郑州大学哲学学士，主要研究领域为逻辑学，特别是模态逻辑及其在哲学、博弈、依赖性和社交网络等中的应用。论文发表于Journal of Logic and Computation, Journal of Logic, Language and Information, LORI, WoLLIC等著名期刊和会议。