一句话:系统研究逻辑句子模型类的同态闭包问题,并刻画一阶与二阶逻辑多片段的计算性质。
谓词逻辑是刻画关系结构类的首选形式,而同态用于描述关系结构间的对应。本文研究逻辑句子模型类的同态闭包(homclosure)所引发的若干基本问题:给定结构是否属于某句子的同态闭包、句子本身是否同态封闭、同态闭包能否在某一逻辑中被刻画,以及同态封闭句子在某些逻辑中是否有规范形式。作者针对一阶与二阶谓词逻辑的多种片段,系统澄清这些问题的可计算性质,给出相应的可判定性、复杂度或不可判定性结论,从而揭示逻辑表达力与同态闭包之间的相互依赖关系。
Predicate logic is the premier choice for specifying classes of relational structures. Homomorphisms are key to describing correspondences between relational structures. Questions concerning the interdependencies between these two means of characterizing (classes of) structures are of fundamental interest and can be highly non-trivial to answer. We investigate several problems regarding the homomorphism closure (homclosure) of the class of all (finite or arbitrary) models of logical sentences: membership of structures in a sentence's homclosure; sentence homclosedness; homclosure characterizability in a logic; normal forms for homclosed sentences in certain logics. For a wide variety of fragments of first- and second-order predicate logic, we clarify these problems' computational properties.