《数理逻辑》第七章-4.pdf

马琦 2010.12.18 maqi08@ 考察形式系统及其扩张的递归可判定性考察形式系统及其扩张的递归可判定性。。 考察形式系统及其扩张的递归可判定性考察形式系统及其扩张的递归可判定性。。 可对任何形式系统提出可判定性和不可判定性问题， 因为哥德尔编码对它们都适用。而这个问题正是D 中 N 一个特殊的子集的递归性或非递归性的问题。 命题命题2.24 命题命题 L 是是可判定可判定的，的，即有一种能行的方法即有一种能行的方法，， 是是可判定可判定的的，，即有一种能行的方法即有一种能行的方法，， 用它可判定用它可判定，，L 的任意给出的的任意给出的wf. wf. 是否是是否是 用它可判定用它可判定，， 的任意给出的的任意给出的wf. wf. 是否是是否是 L L 的定理的定理的定理的定理。。。。 的定理的定理的定理的定理。。。。 第二章的命题2.24说明命题演算的形 式系统L是可判定的。可以证明 命题命题7.41 命题命题 L的定理的哥德尔数的集合是一个递归集的定理的哥德尔数的集合是一个递归集。。 的定理的哥德尔数的集合是一个递归集的定理的哥德尔数的集合是一个递归集。。 谓词演算系统K 是否为递归不可判定的，这 L 依赖于语言L 。 取一个特殊情形，设L 是不含函数字母，不 1 含个体常项，而只有一个谓词字母的一阶语言。 命题命题命题命题77..4242 命题命题命题命题 K 是递归可判定的是递归可判定的。。 LL1 是递归可判定的是递归可判定的。。