| 摘要 | 第6-8页 |
| Abstract | 第8-9页 |
| 第一章 绪论 | 第12-24页 |
| 1.1 引言 | 第12-17页 |
| 1.2 数理逻辑基本知识简介 | 第17-22页 |
| 1.3 本文主要研究内容和结构安排 | 第22-24页 |
| 第二章 逻辑语言在线性规划问题上的不可表达性 | 第24-35页 |
| 2.1 线性规划的逻辑定义 | 第24-32页 |
| 2.1.1 定义LP问题的结构 | 第24-27页 |
| 2.1.2 LP不能被逻辑语句IFP+C,LFP+C和C_(∞ω)~ω在结构层级上刻画 | 第27-30页 |
| 2.1.3 使用含非常数个变元和量词的逻辑表达LP | 第30-32页 |
| 2.2 LP和IP逻辑表达式相等 | 第32-33页 |
| 2.3 次规划问题的逻辑不可表达性 | 第33-35页 |
| 第三章 L_(∞ω)~ω,LFP和PFP在完美匹配问题上的不可表达性 | 第35-42页 |
| 3.1 有限个变量和着色鹅卵石博弈 | 第36-39页 |
| 3.1.1 着色鹅卵石博弈 | 第36-39页 |
| 3.2 着色卵石博奕方法证明L_(∞ω)~ω的表达能力 | 第39-42页 |
| 3.2.1 利用着色鹅卵石博弈证明完美匹配问题的逻辑不可表达性 | 第39-42页 |
| 第四章 一阶归约保持NP-完全性 | 第42-48页 |
| 4.1 逻辑归约和一阶投射 | 第43-44页 |
| 4.1.1 一阶投射 | 第43-44页 |
| 4.2 通过一阶投射证明NP问题的完全性 | 第44-48页 |
| 第五章 结论和将来的研究 | 第48-49页 |
| 参考文献 | 第49-55页 |
| 作者在攻读硕士学位期间公开发表的论文 | 第55-56页 |
| 致谢 | 第56页 |
