特定类有穷结构上的逻辑的表达能力

有穷模型论是受数据库理论和计算复杂性理论推动而发展起来的数理逻辑的一个研究领域。有穷模型论的主题之一就是探讨逻辑在有穷结构上的表达能力，本文围绕这一主题取得如下结果： 1. 使用Ehrenfeucht-Fraïssé博弈的方法，我们证明了在有穷纯算术结构类BFR上，Δ0≠Δ1，从而解决了Atserias博士论文中提出的一个开放问题 ； 2．提出一个新的在双射博弈中使用警察和强盗博弈的策略构造，利用这一策略构造，我们给出Dawar和Richerby的文章中的关键定理的正确证明，同时还对Atserias, Bultov和Dawar的文章中的一个关键结果作出改进 ； 3. 使用变型的Cai-Fürer-Immerman构造和Dawar和Richerby的条件，我们证明了在平衡图上，IFP+C不能刻画PTIME ，从而在“有无逻辑在完美图相关的图类上刻画PTIME”这一问题的研究上取得进展 ； 4. 利用所谓的扭结图和变异的扭结图，我们证明了可比较图，区间图以及AT-free图在FO(TC)中可定义，从而在“完美图相关的图类的逻辑可定义性”这一问题的研究上取得进展。