4月9日,Søren Knudstorp博士作了题为《Features of (Un)decidable Logics》的报告。
Søren首先引入了可判定性的概念,通过解答“什么是判定问题”“什么是判定问题的可判定性”“什么是逻辑的可判定性”以及“我们为什么要研究可判定性”等基础问题,说明了可判定问题的研究对逻辑学内部的领域划分及整体的学科发展具有十分重要的意义。
随后,Søren介绍了propositional team logics的语言及语义,并说明所有propositional team logics都是可判定的。通过将propositional team logics转换为一种含有二元模态算子的命题模态逻辑,Søren给出了其关系语义定义,并说明了该命题模态逻辑关于幂集框架类(只考虑principal valuations)的可靠性及完全性。
Søren进一步取消对赋值的限制,并通过将取消限制后的逻辑的可满足问题转换成对应的tiling problem,证明了该逻辑是不可判定的,解决了Goranko和Vakarelov于1999年提出的开问题,并得出关于可判定特征的第一个结论——逻辑的赋值会影响逻辑的可判定性。
通过对三种包含(P(N), ∪)的半格类逻辑的比较研究,Søren得出了关于可判定特征的第二、三个结论——关系是否满足结合律(associativity)、语言是否包含否定联结词都会影响逻辑的可判定性。
通过上述三个特征,Søren给出了一个关于Relevant logic S的初步结论——S是不可判定的,并通过证明S不具有有穷模型性,展示了S的不可判定性证明的主要思路。
——洪博