论文部分内容阅读
这篇硕士论文集中了作者在攻读硕士学位期间的主要研究成果.
第一章绪论中,主要对数理逻辑、λ-演算和组合逻辑作一个概述并阐明本文的研究背景.
在第二章中,我们主要讨论有关逻辑联结词的完全集的问题,着眼于4个一元逻辑联结词和16个二元逻辑联结词,深入分析和讨论了这20个逻辑联结词之间的相互关系,定义了有关联结词集的表出、表出等价、表出相关、表出无关以及表出封闭等概念,并且给出与此相关的几条引理.以这几条引理为工具,我们考察这20个联结词的所有组合,从中得到46个联结词的极小完全集,其中单元素联结词极小完全集2个,双元素联结词极小完全集34个,三元素联结词极小完全集10个,无其它的组合构成联结词的极小完全集.
在第三章,考虑到在纯λ-演算中的Bǒhm-VanderMey定理对不动点组合算子的结构有一个简单而明晰的刻划,且此定理在CLw系统中不真,因此我们的主要目标是在CLw中对不动点组合算子作一结构刻划.我们证明了在CLw中不动点组合算子是一个形如SPQ的函数项.并且,我们进一步指出,通过添加适当的外延规则或公理可以使CLw成为一个Bǒhm-VanderMey定理在其中成立的形式系统.本章的最后部分我们讨论关于不动点组合算子的范式相关问题,比较不动点组合算子的范式在CLw系统和λβ系统中的不同情况,给出了一个CLw中不动点组合算子范式的不可判定定理.
在第四章,我们考虑组合逻辑形式系统CLζw的外延性问题,由于在标准转换的意义下形式系统CLζw弱于形式系统λβ和λβη,我们采用三种方式对形式系统CLζw进行外延,前两种使之与形式系统λβ等价,后一种与形式系统λβη等价.作为推论,我们亦证明了前两种外延系统是定理等价的.
在第五章,我们给出了λ-模型D∞的一个基本投射不等式,它在文献[17]中证明D∞是一个λ-模型时的地位是重要的,但文献[17]将它误认为是一个等式的多次运用.