“要从完备性走向可判定性,还需过滤法或其他有限模型构造。典范模型保证反模型存在,过滤法只保留目标公式的有限观察类型;有限模型性质由后一步而非真值引理单独推出。”
形式陈述 ​
设
等价地,每个
FMP 是见证大小的存在性陈述,不自带统一上界。若还能从输入公式有效算出有限见证的大小界,称为有效有限模型性质;若要求有限公式集同时具有有限模型,则是更强的有限可满足性版本。使用术语时应说明逻辑、语义类与采用的强度。
Kripke 模型过滤法是证明 FMP 的主要方法之一。对 K,取公式
直觉
有限模型性质说,无限结构不会隐藏某个只能在无限远处暴露的逻辑错误。只要公式不是定理,就能在一张有限世界图上看到失败。它把抽象的“存在反模型”变成原则上可穷举的有限证书,但证书可能很大,寻找它也可能计算昂贵。
FMP 关心的是逻辑能否由有限结构完全测试,不是所有模型本来都有限。一个公式可以同时拥有有限与无限模型;性质只要求至少有一个有限见证,不要求把每个无限模型整体等价地压成某个固定有限模型。
例子与边界
公式
要求观察世界拥有一个
K 的非定理
有限模型性质不等于有限公理化。前者限制反模型的大小类型,后者限制生成全部定理所需的公理数目;二者可以分离。FMP 也不单独推出可判定性:要把有限见证变成终止算法,还需能有效识别候选框架、枚举证明或给出可计算大小界。对 K,这些有效条件都可满足,故可判定。
它也不同于紧致性。紧致性把每个有限子理论可满足提升为整个理论可满足,可能产生无限模型;FMP 则为单个非定理或有限目标寻找有限见证。一个结论不能用另一个词直接替代。
推论与应用
K 的过滤上界给出一种有限搜索决策思路,并进一步成为复杂度分析的起点。实际 PSPACE 上界使用按需深度搜索等更精细技术,不会真的枚举所有
对加入框架公理的逻辑,证明任务分成两步:保持目标公式真值,并保持框架类。例如 S4 需要传递、自反的有限过滤,不能直接拿 K 的任意商关系结束证明。某些正规模态逻辑没有 FMP,即非定理可能需要无限框架才能反驳;因此“模态逻辑通常画有限世界图”不是一般证明。
有限模型还支持自动模型生成与反例展示。工具返回的有限 Kripke 图可逐世界核对真值条款,比一份纯句法失败日志更直观;但它证明的只是当前公式在指定逻辑中不可导,不能自动概括成对所有扩展逻辑都成立的反例。
参考资料
- Patrick Blackburn, Maarten de Rijke, and Yde Venema, Modal Logic, Cambridge University Press, 2001, Chapter 2, filtration and finite models。
- Alexander Chagrov and Michael Zakharyaschev, Modal Logic, Oxford University Press, 1997, Chapters 5 and 11, filtration and finite approximability。
- Robert Goldblatt, Logics of Time and Computation, 2nd ed., CSLI Publications, 1992, Chapter 3, finite model techniques。